C++
std :: vektor

Introduktion

Anmärkningar

Initiera en std :: vektor

En std::vector kan initialiseras på flera sätt samtidigt som den förklaras:

std::vector<int> v{ 1, 2, 3 };  // v becomes {1, 2, 3}

// Different from std::vector<int> v(3, 6)
std::vector<int> v{ 3, 6 };     // v becomes {3, 6}

// Different from std::vector<int> v{3, 6} in C++11
std::vector<int> v(3, 6);  // v becomes {6, 6, 6}

std::vector<int> v(4);     // v becomes {0, 0, 0, 0}

En vektor kan initialiseras från en annan behållare på flera sätt:

Kopiera konstruktion (endast från en annan vektor), som kopierar data från v2 :

std::vector<int> v(v2);
std::vector<int> v = v2;

std::vector<int> v(std::move(v2));
std::vector<int> v = std::move(v2);

Iterator (serie) kopieringskonstruktion, som kopierar element till v :

// from another vector
std::vector<int> v(v2.begin(), v2.begin() + 3); // v becomes {v2[0], v2[1], v2[2]}

// from an array
int z[] = { 1, 2, 3, 4 };
std::vector<int> v(z, z + 3);                   // v becomes {1, 2, 3}

// from a list
std::list<int> list1{ 1, 2, 3 };
std::vector<int> v(list1.begin(), list1.end()); // v becomes {1, 2, 3}

// from another vector
std::vector<int> v(std::make_move_iterator(v2.begin()),
                   std::make_move_iterator(v2.end());

// from a list
std::list<int> list1{ 1, 2, 3 };
std::vector<int> v(std::make_move_iterator(list1.begin()),
                   std::make_move_iterator(list1.end()));

Med hjälp av assign() -medlem kan en std::vector -vektor initialiseras efter dess konstruktion:

v.assign(4, 100);                      // v becomes {100, 100, 100, 100}

v.assign(v2.begin(), v2.begin() + 3);  // v becomes {v2[0], v2[1], v2[2]}

int z[] = { 1, 2, 3, 4 };
v.assign(z + 1, z + 4);                // v becomes {2, 3, 4}

Infoga element

Lägga till ett element i slutet av en vektor (genom att kopiera / flytta):

struct Point {
  double x, y;
  Point(double x, double y) : x(x), y(y) {}
};
std::vector<Point> v;
Point p(10.0, 2.0);
v.push_back(p);  // p is copied into the vector.

std::vector<Point> v;
v.emplace_back(10.0, 2.0); // The arguments are passed to the constructor of the
                           // given type (here Point). The object is constructed
                           // in the vector, avoiding a copy.

Observera att std::vector inte har en push_front() grund av prestandaskäl. Att lägga till ett element i början gör att alla befintliga element i vektorn flyttas. Om du ofta vill infoga element i början av behållaren, kanske du vill använda std::list eller std::deque istället.

Infoga ett element i valfri position i en vektor:

std::vector<int> v{ 1, 2, 3 };
v.insert(v.begin(), 9);          // v now contains {9, 1, 2, 3}

std::vector<int> v{ 1, 2, 3 };
v.emplace(v.begin()+1, 9);     // v now contains {1, 9, 2, 3}

Infoga en annan vektor vid valfri position på vektorn:

std::vector<int> v(4);      // contains: 0, 0, 0, 0
std::vector<int> v2(2, 10); // contains: 10, 10
v.insert(v.begin()+2, v2.begin(), v2.end()); // contains: 0, 0, 10, 10, 0, 0

Infoga en matris vid valfri position för en vektor:

std::vector<int> v(4); // contains: 0, 0, 0, 0
int a [] = {1, 2, 3}; // contains: 1, 2, 3
v.insert(v.begin()+1, a, a+sizeof(a)/sizeof(a[0])); // contains: 0, 1, 2, 3, 0, 0, 0

Använd reserve() innan du sätter in flera element om resulterande vektorstorlek är känd i förväg för att undvika flera omfördelningar (se vektorstorlek och kapacitet ):

std::vector<int> v;
v.reserve(100);
for(int i = 0; i < 100; ++i)
    v.emplace_back(i);

Var noga med att inte göra misstaget att ringa resize() i det här fallet, så skapar du oavsiktligt en vektor med 200 element där endast de senare hundra kommer att ha det värde du avsåg.

Iterating Over std :: vector

Du kan iterera över en std::vector på flera sätt. För var och en av följande avsnitt definieras v enligt följande:

std::vector<int> v;

Iterating i framåtriktningen

// Range based for
for(const auto& value: v) {
    std::cout << value << "\n";
}

// Using a for loop with iterator
for(auto it = std::begin(v); it != std::end(v); ++it) {
    std::cout << *it << "\n";
}

// Using for_each algorithm, using a function or functor:
void fun(int const& value) {
    std::cout << value << "\n";
}

std::for_each(std::begin(v), std::end(v), fun);

// Using for_each algorithm. Using a lambda:
std::for_each(std::begin(v), std::end(v), [](int const& value) {
    std::cout << value << "\n";
});

// Using a for loop with iterator
for(std::vector<int>::iterator it = std::begin(v); it != std::end(v); ++it) {
    std::cout << *it << "\n";
}

// Using a for loop with index
for(std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << "\n";
}

Iterera i omvänd riktning

// There is no standard way to use range based for for this.
// See below for alternatives.

// Using for_each algorithm
// Note: Using a lambda for clarity. But a function or functor will work
std::for_each(std::rbegin(v), std::rend(v), [](auto const& value) {
    std::cout << value << "\n";
});

// Using a for loop with iterator
for(auto rit = std::rbegin(v); rit != std::rend(v); ++rit) {
    std::cout << *rit << "\n";
}

// Using a for loop with index
for(std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v[v.size() - 1 - i] << "\n";
}

Men det finns inget inbyggt sätt att använda intervallet baserat på för att vända iteration; det är relativt enkelt att fixa detta. Området baserat på användningar begin() och end() att få iteratorer och därmed simulera detta med ett omslagobjekt kan uppnå de resultat vi behöver.

template<class C>
struct ReverseRange {
  C c; // could be a reference or a copy, if the original was a temporary
  ReverseRange(C&& cin): c(std::forward<C>(cin)) {}
  ReverseRange(ReverseRange&&)=default;
  ReverseRange& operator=(ReverseRange&&)=delete;
  auto begin() const {return std::rbegin(c);}
  auto end()   const {return std::rend(c);}
};
// C is meant to be deduced, and perfect forwarded into
template<class C>
ReverseRange<C> make_ReverseRange(C&& c) {return {std::forward<C>(c)};}

int main() {
    std::vector<int> v { 1,2,3,4};
    for(auto const& value: make_ReverseRange(v)) {
        std::cout << value << "\n";
    }
}

Verkställer const-element

Eftersom C ++ 11- cbegin() och cend() tillåter dig att få en konstant iterator för en vektor, även om vektorn är icke-konst. En konstant iterator låter dig läsa men inte ändra innehållet i vektorn som är användbart för att säkerställa const korrekthet:

// forward iteration
for (auto pos = v.cbegin(); pos != v.cend(); ++pos) {
   // type of pos is vector<T>::const_iterator
   // *pos = 5; // Compile error - can't write via const iterator
}

// reverse iteration
for (auto pos = v.crbegin(); pos != v.crend(); ++pos) {
   // type of pos is vector<T>::const_iterator
   // *pos = 5; // Compile error - can't write via const iterator
}

// expects Functor::operand()(T&) 
for_each(v.begin(), v.end(), Functor());

// expects Functor::operand()(const T&)
for_each(v.cbegin(), v.cend(), Functor())

for (auto const& e : std::as_const(v)) {
  std::cout << e << '\n';
}

Detta är lätt att implementera i tidigare versioner av C ++:

template <class T>
constexpr std::add_const_t<T>& as_const(T& t) noexcept {
  return t;
}

En anmärkning om effektivitet

Eftersom klassen std::vector princip är en klass som hanterar en dynamiskt allokerad sammanhängande matris, gäller samma princip som förklaras här för C ++ -vektorer. Att få tillgång till vektorns innehåll med index är mycket effektivare när man följer principen om rad-huvudordning. Naturligtvis sätter varje tillgång till vektorn också sitt hanteringsinnehåll i cachen också, men som har diskuterats många gånger (särskilt här och här ) är skillnaden i prestanda för iterering över en std::vector jämfört med en rå matris är försumbar. Så samma effektivitetsprincip för rå matriser i C gäller också för C ++: s std::vector .

Åtkomst till element

Det finns två huvudsakliga sätt att få tillgång till element i en std::vector

• indexbaserad åtkomst
• iteratorer

Indexbaserad åtkomst:

Detta kan göras antingen med abonnentoperatören [] eller med medlemsfunktionen at() .

Båda returnerar en referens till elementet vid respektive position i std::vector (såvida det inte är en vector<bool> ), så att det kan läsas såväl som modifierat (om vektorn inte är const ).

[] och at() skiljer sig åt att [] inte garanteras att utföra några gränskontroller, medan at() gör det. Åtkomst till element där index < 0 eller index >= size är odefinierat beteende för [] , medan at() kastar ett std::out_of_range undantag.

Obs: Exemplen nedan använder C ++ 11-stil initialisering för tydlighet, men operatörerna kan användas med alla versioner (såvida inte markerat C ++ 11).

std::vector<int> v{ 1, 2, 3 };

// using []
int a = v[1];    // a is 2
v[1] = 4;        // v now contains { 1, 4, 3 }

// using at()
int b = v.at(2); // b is 3
v.at(2) = 5;     // v now contains { 1, 4, 5 }
int c = v.at(3); // throws std::out_of_range exception

Eftersom metoden at() utför gränskontroll och kan kasta undantag är den långsammare än [] . Detta gör [] föredragen kod där operationens semantik garanterar att indexet är i gränser. I alla fall görs åtkomst till element av vektorer konstant. Det betyder att åtkomst till det första elementet i vektorn har samma kostnad (i tid) för åtkomst till det andra elementet, det tredje elementet och så vidare.

Tänk till exempel på den här slingan

for (std::size_t i = 0; i < v.size(); ++i) {
    v[i] = 1;
}

Här vet vi att indexvariabeln i alltid är i gränser, så det skulle vara ett slöseri med CPU-cykler att kontrollera att i är i gränser för varje samtal till operator[] .

De front() och back() delfunktionerna möjliggör enkel referensåtkomst till respektive vektors första och sista element. Dessa positioner används ofta, och de speciala accessorerna kan vara mer läsbara än deras alternativ med [] :

std::vector<int> v{ 4, 5, 6 }; // In pre-C++11 this is more verbose

int a = v.front();   // a is 4, v.front() is equivalent to v[0]
v.front() = 3;       // v now contains {3, 5, 6}
int b = v.back();    // b is 6, v.back() is equivalent to v[v.size() - 1]
v.back() = 7;        // v now contains {3, 5, 7}

Obs : Det är odefinierat beteende att åberopa front() eller back() på en tom vektor. Du måste kontrollera att behållaren inte är tom med hjälp av funktionen empty() medlem (som kontrollerar om behållaren är tom) innan du ringer front() eller back() . Ett enkelt exempel på användningen av 'tom ()' för att testa för en tom vektor följer:

int main ()
{
  std::vector<int> v;
  int sum (0);

  for (int i=1;i<=10;i++) v.push_back(i);//create and initialize the vector

  while (!v.empty())//loop through until the vector tests to be empty
  {
     sum += v.back();//keep a running total
     v.pop_back();//pop out the element which removes it from the vector
  }

  std::cout << "total: " << sum << '\n';//output the total to the user

  return 0;
}

Exemplet ovan skapar en vektor med en sekvens av siffror från 1 till 10. Därefter sprider den elementen i vektorn ut tills vektorn är tom (med 'tom ()') för att förhindra odefinierat beteende. Sedan beräknas summan av siffrorna i vektorn och visas för användaren.

std::vector<int> v{ 1, 2, 3, 4 }; // v contains {1, 2, 3, 4}
int* p = v.data(); // p points to 1
*p = 4;            // v now contains {4, 2, 3, 4}
++p;               // p points to 2
*p = 3;            // v now contains {4, 3, 3, 4}
p[1] = 2;          // v now contains {4, 3, 2, 4}
*(p + 2) = 1;      // v now contains {4, 3, 2, 1}

std::vector<int> v(4);
int* ptr = &(v.front()); // or &v[0]

iteratorer:

Iteratorer förklaras mer detaljerat i exemplet "Iterating over std::vector " och artikeln Iterators . Kort sagt, de agerar på samma sätt som pekare till elementen i vektorn:

std::vector<int> v{ 4, 5, 6 };

auto it = v.begin();
int i = *it;        // i is 4
++it; 
i = *it;            // i is 5
*it = 6;            // v contains { 4, 6, 6 }
auto e = v.end();   // e points to the element after the end of v. It can be 
                    // used to check whether an iterator reached the end of the vector:
++it; 
it == v.end();      // false, it points to the element at position 2 (with value 6)
++it;
it == v.end();      // true

Det överensstämmer med standarden att en std::vector<T> s iteratorer faktiskt är T* , men de flesta standardbibliotek gör inte detta. Om du inte gör detta förbättrar både felmeddelanden, fångar icke-portabel kod och kan användas för att instrumentera iteratorerna med felsökningskontroller i icke-release-build. Sedan, i release-builds, optimeras klassomslaget runt den underliggande pekaren bort.

Du kan fortsätta en referens eller en pekare till ett element i en vektor för indirekt åtkomst. Dessa referenser eller pekare till element i vector förblir stabila och åtkomst förblir definierad om du inte lägger till / tar bort element vid eller före elementet i vector , eller om du får vector att ändras. Detta är samma sak som regeln för ogiltigförklaring av iteratorer.

std::vector<int> v{ 1, 2, 3 };
int* p = v.data() + 1;     // p points to 2
v.insert(v.begin(), 0);    // p is now invalid, accessing *p is a undefined behavior.
p = v.data() + 1;          // p points to 1
v.reserve(10);             // p is now invalid, accessing *p is a undefined behavior.
p = v.data() + 1;          // p points to 1
v.erase(v.begin());        // p is now invalid, accessing *p is a undefined behavior.

Använda std :: vektor som en C-matris

Det finns flera sätt att använda en std::vector som en C-matris (till exempel för kompatibilitet med C-bibliotek). Detta är möjligt eftersom elementen i en vektor lagras sammanhängande.

std::vector<int> v{ 1, 2, 3 };
int* p = v.data();

Innan C ++ 11 skulle du ta adressen till vektorns första element för att få en motsvarande pekare, om vektorn inte är tom är dessa båda metoder utbytbara:

int* p = &v[0];      // combine subscript operator and 0 literal

int* p = &v.front(); // explicitly reference the first element

Obs: Om vektorn är tom är v[0] och v.front() odefinierade och kan inte användas.

När du lagrar basadressen för vektorns data, observera att många operationer (som push_back , resize etc.) kan ändra dataminnesplatsen för vektorn och därmed ogiltiga tidigare datapekare . Till exempel:

std::vector<int> v;
int* p = v.data();
v.resize(42);      // internal memory location changed; value of p is now invalid

Iterator / pekare ogiltigförklaring

Iteratorer och pekare som pekar in på en std::vector kan bli ogiltiga, men endast när vissa operationer utförs. Att använda ogiltiga iteratorer / pekare kommer att leda till odefinierat beteende.

Verksamheter som ogiltiggör iteratorer / pekare inkluderar:

• Varje infogningsoperation som ändrar vector capacity kommer att ogiltiga alla iteratorer / pekare:

  vector<int> v(5); // Vector has a size of 5; capacity is unknown.
  int *p1 = &v[0];
  v.push_back(2);   // p1 may have been invalidated, since the capacity was unknown.
  
  v.reserve(20);    // Capacity is now at least 20.
  int *p2 = &v[0];
  v.push_back(4);   // p2 is *not* invalidated, since the size of `v` is now 7.
  v.insert(v.end(), 30, 9); // Inserts 30 elements at the end. The size exceeds the
                            // requested capacity of 20, so `p2` is (probably) invalidated.
  int *p3 = &v[0];
  v.reserve(v.capacity() + 20); // Capacity exceeded, thus `p3` is invalid.
  

auto old_cap = v.capacity();
v.shrink_to_fit();
if(old_cap != v.capacity())
    // Iterators were invalidated.

• Alla insättningsoperationer, som inte ökar kapaciteten, kommer att fortfarande ogiltiga iteratorer / pekare som pekar på element i insättningspositionen och förbi den. Detta inkluderar end iteratorn:

  vector<int> v(5);
  v.reserve(20);                 // Capacity is at least 20.
  int *p1 = &v[0];
  int *p2 = &v[3];
  v.insert(v.begin() + 2, 5, 0); // `p2` is invalidated, but since the capacity
                                 // did not change, `p1` remains valid.
  int *p3 = &v[v.size() - 1];
  v.push_back(10); // The capacity did not change, so `p3` and `p1` remain valid.
  

• Varje borttagningsoperation ogiltiggör iteratorer / pekare som pekar på de borttagna elementen och till några element förbi de borttagna elementen. Detta inkluderar end iteratorn:

  vector<int> v(10);
  int *p1 = &v[0];
  int *p2 = &v[5];
  v.erase(v.begin() + 3, v.end()); // `p2` is invalid, but `p1` remains valid.
  

• operator= (kopiera, flytta eller på annat sätt) och clear() ogiltigförklarar alla iteratorer / pekare som pekar in i vektorn.

Ta bort element

Radera det sista elementet:

std::vector<int> v{ 1, 2, 3 };
v.pop_back();                           // v becomes {1, 2}

Ta bort alla element:

std::vector<int> v{ 1, 2, 3 };
v.clear();                              // v becomes an empty vector

Radera element efter index:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(v.begin() + 3);                 // v becomes {1, 2, 3, 5, 6}

Obs: För en vector tar bort ett element som inte är det sista elementet måste alla element bortom det borttagna elementet kopieras eller flyttas för att fylla mellanrummet, se noten nedan och std :: listan .

Radera alla element inom ett intervall:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(v.begin() + 1, v.begin() + 5);  // v becomes {1, 6}

Obs: Ovanstående metoder ändrar inte vektorns kapacitet, bara storleken. Se vektorstorlek och kapacitet .

erase , som tar bort en rad element, används ofta som en del av raderingsidentifieringen . Det vill säga, först std::remove flyttar vissa element till slutet av vektorn och erase huggar av dem. Detta är en relativt ineffektiv operation för alla index som är mindre än vektorns senaste index eftersom alla element efter de raderade segmenten måste flyttas till nya positioner. För hastighetskritiska applikationer som kräver effektivt borttagning av godtyckliga element i en behållare, se std :: -listan .

Radera element efter värde:

std::vector<int> v{ 1, 1, 2, 2, 3, 3 };
int value_to_remove = 2;
v.erase(std::remove(v.begin(), v.end(), value_to_remove), v.end()); // v becomes {1, 1, 3, 3}

Radera element efter villkor:

// std::remove_if needs a function, that takes a vector element as argument and returns true, 
// if the element shall be removed
bool _predicate(const int& element) {
    return (element > 3); // This will cause all elements to be deleted that are larger than 3
}
...
std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(std::remove_if(v.begin(), v.end(), _predicate), v.end()); // v becomes {1, 2, 3}

Ta bort element av lambda utan att skapa ytterligare predikatfunktioner

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(std::remove_if(v.begin(), v.end(),
     [](auto& element){return element > 3;} ), v.end()
);

Radera element efter villkor från en slinga:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
std::vector<int>::iterator it = v.begin();
while (it != v.end()) {
    if (condition)
        it = v.erase(it); // after erasing, 'it' will be set to the next element in v
    else
        ++it;             // manually set 'it' to the next element in v
}

Även om det är viktigt att inte öka it vid en radering, bör du överväga att använda en annan metod när du sedan raderar upprepade gånger i en slinga. remove_if för ett mer effektivt sätt.

Radera element efter villkor från en omvänd slinga:

std::vector<int> v{ -1, 0, 1, 2, 3, 4, 5, 6 };
typedef std::vector<int>::reverse_iterator rev_itr;
rev_itr it = v.rbegin();

while (it != v.rend()) { // after the loop only '0' will be in v
    int value = *it;
    if (value) {
        ++it;
        // See explanation below for the following line.
        it = rev_itr(v.erase(it.base()));
    } else
        ++it;
}

Notera några punkter för föregående slinga:

• Ges en omvänd iterator it pekar på ett visst element, varvid förfarandet base ger den vanliga (icke-omvänd) iterator som pekar på samma element.

• vector::erase(iterator) raderar det element som pekas av en iterator och returnerar en iterator till elementet som följde det givna elementet.

• reverse_iterator::reverse_iterator(iterator) konstruerar en omvänd iterator från en iterator.

Sätta helt och hållet, linjen it = rev_itr(v.erase(it.base())) säger: ta omvänd iterator it , har v radera elementet pekade genom dess regelbundna iterator; ta den erhållna iterator, konstruera en omvänd iterator från den, och tilldela den till det omvända iterator it .

Att ta bort alla element med v.clear() frigör inte minnet ( capacity() på vektorn förblir oförändrad). För att återta utrymme använder du:

std::vector<int>().swap(v);

v.shrink_to_fit();

The shrink_to_fit garanterar inte att verkligen återta utrymme, men de flesta nuvarande implementeringar gör det.

Hitta ett element i std :: vektor

Funktionen std::find , definierad i <algorithm> -huvudet, kan användas för att hitta ett element i en std::vector .

std::find använder operator== att jämföra element för jämlikhet. Den returnerar en iterator till det första elementet i intervallet som jämförs lika med värdet.

Om elementet i fråga inte hittas returnerar std::find std::vector::end (eller std::vector::cend om vektorn är const ).

static const int arr[] = {5, 4, 3, 2, 1};
std::vector<int> v (arr, arr + sizeof(arr) / sizeof(arr[0]) );

std::vector<int>::iterator it = std::find(v.begin(), v.end(), 4);
std::vector<int>::difference_type index = std::distance(v.begin(), it);
// `it` points to the second element of the vector, `index` is 1

std::vector<int>::iterator missing = std::find(v.begin(), v.end(), 10);
std::vector<int>::difference_type index_missing = std::distance(v.begin(), missing);
// `missing` is v.end(), `index_missing` is 5 (ie. size of the vector)

std::vector<int> v { 5, 4, 3, 2, 1 };

auto it = std::find(v.begin(), v.end(), 4);
auto index = std::distance(v.begin(), it);
// `it` points to the second element of the vector, `index` is 1

auto missing = std::find(v.begin(), v.end(), 10);
auto index_missing = std::distance(v.begin(), missing);
// `missing` is v.end(), `index_missing` is 5 (ie. size of the vector)

Om du behöver utföra många sökningar i en stor vektor, kanske du vill överväga att sortera vektorn först innan du använder algoritmen binary_search .

För att hitta det första elementet i en vektor som uppfyller ett villkor kan std::find_if användas. Förutom de två parametrarna som ges till std::find , accepterar std::find_if ett tredje argument som är ett funktionsobjekt eller funktionspekare till en predikatfunktion. Predikatet bör acceptera ett element från behållaren som ett argument och returnera ett värde som kan konverteras till bool , utan att ändra behållaren:

bool isEven(int val) {
    return (val % 2 == 0); 
}

struct moreThan {
    moreThan(int limit) : _limit(limit) {}
    
    bool operator()(int val) {
        return val > _limit;
    }
    
    int _limit;
};

static const int arr[] = {1, 3, 7, 8};
std::vector<int> v (arr, arr + sizeof(arr) / sizeof(arr[0]) );
    
std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), isEven);
// `it` points to 8, the first even element

std::vector<int>::iterator missing = std::find_if(v.begin(), v.end(), moreThan(10));
// `missing` is v.end(), as no element is greater than 10

// find the first value that is even
std::vector<int> v = {1, 3, 7, 8};
auto it = std::find_if(v.begin(), v.end(), [](int val){return val % 2 == 0;});
// `it` points to 8, the first even element

auto missing = std::find_if(v.begin(), v.end(), [](int val){return val > 10;});
// `missing` is v.end(), as no element is greater than 10

Konvertera en matris till std :: vector

En matris kan enkelt konverteras till en std::vector med hjälp av std::begin och std::end :

int values[5] = { 1, 2, 3, 4, 5 }; // source array

std::vector<int> v(std::begin(values), std::end(values)); // copy array to new vector

for(auto &x: v)
    std::cout << x << " ";
std::cout << std::endl;

int main(int argc, char* argv[]) {
    // convert main arguments into a vector of strings.
    std::vector<std::string>  args(argv, argv + argc);
}

En C ++ 11 initializer_list <> kan också användas för att initialisera vektorn på en gång

initializer_list<int> arr = { 1,2,3,4,5 };
vector<int> vec1 {arr};

for (auto & i : vec1)
    cout << i << endl;

vektor : Undantaget till så många, så många regler

Standarden (avsnitt 23.3.7) anger att en specialisering av vector<bool> tillhandahålls, som optimerar utrymmet genom att packa bool , så att var och en tar upp bara en bit. Eftersom bitar inte är adresserbara i C ++ betyder det att flera krav på vector inte ställs på vector<bool> :

• Data som lagras behöver inte vara sammanhängande, så en vector<bool> kan inte överföras till ett C API som förväntar sig en bool grupp.
• at() , operator [] , och dereferencing av iteratorer returnerar inte en referens till bool . Snarare returnerar de ett proxyobjekt som (ofullständigt) simulerar en referens till en bool genom att överbelasta dess tilldelningsoperatörer. Som ett exempel kanske följande kod inte är giltig för std::vector<bool> , eftersom du inte ger en referens till en referens:

std::vector<bool> v = {true, false};
for (auto &b: v) { } // error

På liknande sätt kan funktioner som förväntar sig en bool& argument inte användas med resultatet av operator [] eller at() tillämpas på vector<bool> , eller med resultatet att du återinvesterar sin iterator:

  void f(bool& b);
  f(v[0]);             // error
  f(*v.begin());       // error

Implementeringen av std::vector<bool> är beroende av både kompilatorn och arkitekturen. Specialiseringen implementeras genom att packa n Booleans i den lägsta adresserbara delen av minnet. Här är n storleken i bitar av det lägsta adresserbara minnet. I de flesta moderna system är detta 1 byte eller 8 bitar. Detta innebär att en byte kan lagra 8 booleska värden. Detta är en förbättring jämfört med den traditionella implementeringen där 1 booleskt värde lagras i 1 byte minne.

Obs: Exemplet nedan visar möjliga bitvisa värden för enskilda bytes i en traditionell kontra optimerad vector<bool> . Detta gäller inte alltid i alla arkitekturer. Det är dock ett bra sätt att visualisera optimeringen. I exemplen nedan representeras en byte som [x, x, x, x, x, x, x, x].

Traditionell std::vector<char> lagring av 8 booleska värden:

std::vector<char> trad_vect = {true, false, false, false, true, false, true, true};

Bitvis representation:

[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1]

Specialiserad std::vector<bool> lagring av 8 booleska värden:

std::vector<bool> optimized_vect = {true, false, false, false, true, false, true, true};

Bitvis representation:

[1,0,0,0,1,0,1,1]

Observera i exemplet ovan, att i den traditionella versionen av std::vector<bool> 8 booleska värden upp 8 byte minne, medan de i den optimerade versionen av std::vector<bool> bara använder 1 byte av minne. Detta är en betydande förbättring av minnesanvändningen. Om du behöver skicka en vector<bool> till en C-stil API, kan du behöva kopiera värdena till en matris eller hitta ett bättre sätt att använda API: t om minne och prestanda är i riskzonen.

Vektorstorlek och kapacitet

Vektorstorlek är helt enkelt antalet element i vektorn:

1. Strömvektorstorlek avfrågas genom size() medlemsfunktion. Bekvämlighet empty() -funktion returnerar true om storleken är 0:

   vector<int> v = { 1, 2, 3 }; // size is 3
   const vector<int>::size_type size = v.size();
   cout << size << endl; // prints 3
   cout << boolalpha << v.empty() << endl; // prints false
   

2. Standardkonstruerad vektor börjar med storleken 0:

   vector<int> v; // size is 0
   cout << v.size() << endl; // prints 0
   

3. Att lägga till N element till vektorn ökar storleken med N (t.ex. genom push_back() , insert() eller resize() ).

4. Att ta bort N element från vektorn minskar storleken med N (t.ex. genom pop_back() , erase() eller clear() -funktioner).

5. Vector har en implementeringsspecifik övre gräns för sin storlek, men du kommer troligt att få slut på RAM innan du når den:

   vector<int> v;
   const vector<int>::size_type max_size = v.max_size();
   cout << max_size << endl; // prints some large number
   v.resize( max_size ); // probably won't work
   v.push_back( 1 ); // definitely won't work
   

Vanliga misstag: storlek är inte nödvändigtvis (eller till och med vanligtvis) int :

// !!!bad!!!evil!!!
vector<int> v_bad( N, 1 ); // constructs large N size vector
for( int i = 0; i < v_bad.size(); ++i ) { // size is not supposed to be int!
    do_something( v_bad[i] );
}

Vektorkapacitet skiljer sig från storlek . Medan storleken helt enkelt är hur många element vektorn för närvarande har, är kapaciteten för hur många element den allokerade / reserverade minnet för. Det är användbart eftersom alltför ofta (om) tilldelningar av för stora storlekar kan vara dyra.

1. Strömvektorn Kapaciteten frågas av capacity() medlemsfunktion. Kapaciteten är alltid större eller lika stor :

   vector<int> v = { 1, 2, 3 }; // size is 3, capacity is >= 3
   const vector<int>::size_type capacity = v.capacity();
   cout << capacity << endl; // prints number >= 3
   

2. Du kan manuellt reservera kapacitet efter reserve( N ) (den ändrar vektorkapacitet till N ):

   // !!!bad!!!evil!!!
   vector<int> v_bad;
   for( int i = 0; i < 10000; ++i ) {
       v_bad.push_back( i ); // possibly lot of reallocations
   }
   
   // good
   vector<int> v_good;
   v_good.reserve( 10000 ); // good! only one allocation
   for( int i = 0; i < 10000; ++i ) {
       v_good.push_back( i ); // no allocations needed anymore
   }
   

3. Du kan begära att överskottskapaciteten släpps av shrink_to_fit() (men implementeringen behöver inte följa dig). Detta är användbart för att spara använt minne:

   vector<int> v = { 1, 2, 3, 4, 5 }; // size is 5, assume capacity is 6
   v.shrink_to_fit(); // capacity is 5 (or possibly still 6)
   cout << boolalpha << v.capacity() == v.size() << endl; // prints likely true (but possibly false)
   

Vektor hanterar delvis kapacitet automatiskt, när du lägger till element kan den besluta att växa. Implementatorer gillar att använda 2 eller 1,5 för tillväxtfaktorn (gyllene förhållande skulle vara det ideala värdet - men är opraktiskt på grund av att det är ett rationellt antal). Å andra sidan krymper vanligtvis inte automatiskt. Till exempel:

vector<int> v; // capacity is possibly (but not guaranteed) to be 0
v.push_back( 1 ); // capacity is some starter value, likely 1
v.clear(); // size is 0 but capacity is still same as before!

v = { 1, 2, 3, 4 }; // size is 4, and lets assume capacity is 4.
v.push_back( 5 ); // capacity grows - let's assume it grows to 6 (1.5 factor)
v.push_back( 6 ); // no change in capacity
v.push_back( 7 ); // capacity grows - let's assume it grows to 9 (1.5 factor)
// and so on
v.pop_back(); v.pop_back(); v.pop_back(); v.pop_back(); // capacity stays the same

Sammankoppling av vektorer

En std::vector kan bifogas till en annan med hjälp av medlemsfunktionsinsatsen insert() :

std::vector<int> a = {0, 1, 2, 3, 4};
std::vector<int> b = {5, 6, 7, 8, 9};

a.insert(a.end(), b.begin(), b.end());

Denna lösning misslyckas dock om du försöker lägga till en vektor till sig själv, eftersom standarden anger att iteratorer som ges för att insert() inte får vara från samma intervall som mottagarobjektets element.

a.insert(std::end(a), std::begin(b), std::end(b));

Om ordningen på elementen i den mottagande vektorn inte spelar någon roll kan hänsyn till antalet element i varje vektor undvika onödiga kopieringsoperationer:

if (b.size() < a.size())
  a.insert(a.end(), b.begin(), b.end());
else
  b.insert(b.end(), a.begin(), a.end());

Minska kapaciteten hos en vektor

En std::vector ökar automatiskt sin kapacitet vid infogning efter behov, men den minskar aldrig sin kapacitet efter borttagning av element.

// Initialize a vector with 100 elements
std::vector<int> v(100);

// The vector's capacity is always at least as large as its size
auto const old_capacity = v.capacity();
// old_capacity >= 100

// Remove half of the elements
v.erase(v.begin() + 50, v.end());  // Reduces the size from 100 to 50 (v.size() == 50),
                                   // but not the capacity (v.capacity() == old_capacity)

För att minska dess kapacitet kan vi kopiera innehållet i en vektor till en ny tillfällig vektor. Den nya vektorn har den minsta kapacitet som krävs för att lagra alla element i den ursprungliga vektorn. Om storleksminskningen för den ursprungliga vektorn var signifikant, är kapacitetsminskningen för den nya vektorn troligen betydande. Vi kan sedan byta den ursprungliga vektorn med den tillfälliga för att behålla sin minimerade kapacitet:

std::vector<int>(v).swap(v);

v.shrink_to_fit();

Använda en sorterad vektor för snabb elementuppslag

Titeln <algorithm> ger ett antal användbara funktioner för att arbeta med sorterade vektorer.

En viktig förutsättning för att arbeta med sorterade vektorer är att de lagrade värdena är jämförbara med < .

En osorterad vektor kan sorteras med funktionen std::sort() :

std::vector<int> v;
// add some code here to fill v with some elements
std::sort(v.begin(), v.end());

Sorterade vektorer möjliggör effektiv elementuppslagning med funktionen std::lower_bound() . Till skillnad från std::find() utför detta en effektiv binär sökning på vektorn. Nackdelen är att det bara ger giltiga resultat för sorterade ingångsområden:

// search the vector for the first element with value 42
std::vector<int>::iterator it = std::lower_bound(v.begin(), v.end(), 42);
if (it != v.end() && *it == 42) {
    // we found the element!
}

Obs: Om det begärda värdet inte är en del av vektorn kommer std::lower_bound() att returnera en iterator till det första elementet som är större än det begärda värdet. Detta beteende tillåter oss att infoga ett nytt element på sin rätt plats i en redan sorterad vektor:

int const new_element = 33;
v.insert(std::lower_bound(v.begin(), v.end(), new_element), new_element);

Om du behöver infoga många element på en gång kan det vara mer effektivt att ringa push_back() för alla dem först och sedan ringa std::sort() när alla element har satts in. I detta fall kan den ökade kostnaden för sorteringen lönas mot de reducerade kostnaderna för att sätta in nya element i slutet av vektorn och inte i mitten.

Om din vektor innehåller flera element med samma värde, kommer std::lower_bound() att försöka återställa en iterator till det första elementet i det sökta värdet. Men om du behöver infoga ett nytt element efter det sista elementet i det sökta värdet, bör du använda funktionen std::upper_bound() eftersom detta kommer att orsaka mindre förskjutning av element:

v.insert(std::upper_bound(v.begin(), v.end(), new_element), new_element);

Om du behöver både den övre gränsen och den nedre gränsen, kan du använda funktionen std::equal_range() att hämta båda dem effektivt med ett samtal:

std::pair<std::vector<int>::iterator,
          std::vector<int>::iterator> rg = std::equal_range(v.begin(), v.end(), 42);
std::vector<int>::iterator lower_bound = rg.first;
std::vector<int>::iterator upper_bound = rg.second;

För att testa om ett element finns i en sorterad vektor (även om den inte är specifik för vektorer), kan du använda funktionen std::binary_search() :

bool exists = std::binary_search(v.begin(), v.end(), value_to_find);

Funktioner som returnerar stora vektorer

#include <vector>
#include <iostream>

// If the compiler is unable to perform named return value optimization (NRVO)
// and elide the move altogether, it is required to move from v into the return value.
std::vector<int> fillVector(int a, int b) {
    std::vector<int> v;
    v.reserve(b-a+1);
    for (int i = a; i <= b; i++) {
        v.push_back(i);
    }
    return v; // implicit move
}

int main() { // declare and fill vector
    std::vector<int> vec = fillVector(1, 10);

    // print vector
    for (auto value : vec)
        std::cout << value << " "; // this will print "1 2 3 4 5 6 7 8 9 10 "

    std::cout << std::endl;

    return 0;
}

#include <vector>
#include <iostream>

// passing a std::vector by reference
void fillVectorFrom_By_Ref(int a, int b, std::vector<int> &v) {
    assert(v.empty());
    v.reserve(b-a+1);
    for (int i = a; i <= b; i++) {
        v.push_back(i);
    }
}

int main() {// declare vector
    std::vector<int> vec;
    
    // fill vector
    fillVectorFrom_By_Ref(1, 10, vec);
    // print vector
    for (std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it)
        std::cout << *it << " "; // this will print "1 2 3 4 5 6 7 8 9 10 "
    std::cout << std::endl;
    return 0;
}

Hitta max och min Element och respektive index i en vektor

För att hitta det största eller minsta elementet som är lagrat i en vektor kan du använda metoderna std::max_element respektive std::min_element . Dessa metoder definieras i <algorithm> rubriken. Om flera element motsvarar det största (minsta) elementet, returnerar metoderna iteratorn till det första sådana elementet. Returnera v.end() för tomma vektorer.

std::vector<int> v = {5, 2, 8, 10, 9}; 
int maxElementIndex = std::max_element(v.begin(),v.end()) - v.begin();
int maxElement = *std::max_element(v.begin(), v.end());

int minElementIndex = std::min_element(v.begin(),v.end()) - v.begin();
int minElement = *std::min_element(v.begin(), v.end());

std::cout << "maxElementIndex:" << maxElementIndex << ", maxElement:" << maxElement << '\n';
std::cout << "minElementIndex:" << minElementIndex << ", minElement:" << minElement << '\n';

Produktion:

maxElementIndex: 3, maxElement: 10
minElementIndex: 1, minElement: 2

std::vector<int> v = {5, 2, 8, 10, 9}; 
auto minmax = std::minmax_element(v.begin(), v.end());

std::cout << "minimum element: " << *minmax.first << '\n';
std::cout << "maximum element: " << *minmax.second << '\n';

Matriser med hjälp av vektorer

Vektorer kan användas som en 2D-matris genom att definiera dem som en vektor av vektorer.

En matris med 3 rader och 4 kolumner med varje cell initialiserad som 0 kan definieras som:

std::vector<std::vector<int> > matrix(3, std::vector<int>(4));

  std::vector<std::vector<int>> matrix = { {0,1,2,3},
                                           {4,5,6,7}, 
                                           {8,9,10,11}
                                         };

Värden i en sådan vektor kan nås på liknande sätt som en 2D-grupp

int var = matrix[0][2];

Iterering över hela matrisen liknar den för en normal vektor men med en extra dimension.

for(int i = 0; i < 3; ++i)
{
    for(int j = 0; j < 4; ++j)
    {
        std::cout << matrix[i][j] << std::endl;
    }
}

for(auto& row: matrix)
{
    for(auto& col : row)
    { 
        std::cout << col << std::endl;
    }
}

En vektor av vektorer är ett bekvämt sätt att representera en matris men det är inte den mest effektiva: enskilda vektorer är spridda runt minnet och datastrukturen är inte cachevänlig.

I en korrekt matris måste längden på varje rad vara densamma (detta är inte fallet för en vektor av vektorer). Den extra flexibiliteten kan vara en källa till fel.