C++
std :: vector

Introduction

Remarques

Initialisation d'un std :: vector

Un std::vector peut être initialisé de plusieurs façons en le déclarant:

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}

Un vecteur peut être initialisé à partir d'un autre conteneur de plusieurs manières:

Copier la construction (à partir d'un autre vecteur uniquement), qui copie les données de 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 (range) copy-construction, qui copie des éléments dans 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()));

A l'aide de la fonction membre assign() , un std::vector peut être réinitialisé après sa construction:

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}

Insertion d'éléments

Ajout d'un élément à la fin d'un vecteur (par copie / déplacement):

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.

Notez que std::vector n'a pas de fonction membre push_front() pour des raisons de performances. L'ajout d'un élément au début entraîne le déplacement de tous les éléments existants dans le vecteur. Si vous souhaitez insérer fréquemment des éléments au début de votre conteneur, vous pouvez utiliser plutôt std::list ou std::deque .

Insertion d'un élément à n'importe quelle position d'un vecteur:

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}

Insertion d'un autre vecteur à n'importe quelle position du vecteur:

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

Insérer un tableau à n'importe quelle position d'un vecteur:

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

Utilisez reserve() avant d'insérer plusieurs éléments si la taille de vecteur résultante est connue à l'avance pour éviter les réallocations multiples (voir taille et capacité du vecteur ):

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

Veillez à ne pas commettre l'erreur d'appeler resize() dans ce cas, ou vous créez par inadvertance un vecteur avec 200 éléments, dont seuls les cent derniers auront la valeur souhaitée.

Itération sur std :: vector

Vous pouvez parcourir un std::vector de plusieurs manières. Pour chacune des sections suivantes, v est défini comme suit:

std::vector<int> v;

Itération dans la direction avant

// 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";
}

Itération dans le sens inverse

// 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";
}

Bien qu'il n'y ait pas de moyen intégré d'utiliser la plage pour renverser l'itération; il est relativement simple de résoudre ce problème. La plage basée sur les utilisations begin() et end() pour obtenir des itérateurs et simuler cela avec un objet wrapper peut atteindre les résultats requis.

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";
    }
}

Application d'éléments const

Depuis C ++ 11, les cbegin() et cend() vous permettent d'obtenir un itérateur constant pour un vecteur, même si le vecteur est non-const. Un itérateur constant vous permet de lire mais pas de modifier le contenu du vecteur, ce qui est utile pour appliquer la correction const:

// 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';
}

Ceci est facile à implémenter dans les versions antérieures de C ++:

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

Une note sur l'efficacité

Puisque la classe std::vector est essentiellement une classe qui gère un tableau contigu alloué dynamiquement, le même principe expliqué ici s'applique aux vecteurs C ++. L'accès au contenu du vecteur par index est beaucoup plus efficace lorsque l'on suit le principe de l'ordre des lignes principales. Bien entendu, chaque accès au vecteur met également son contenu de gestion dans le cache, mais comme cela a été débattu plusieurs fois (notamment ici et ici ), la différence de performances pour itérer sur un std::vector par rapport à un tableau brut est négligeable. Ainsi , le même principe d'efficacité pour les tableaux bruts en C applique également pour l 'C ++ std::vector .

Accéder aux éléments

Il y a deux manières principales d'accéder aux éléments dans un std::vector

• accès par index
• itérateurs

Accès par index:

Cela peut être fait soit avec l’opérateur subscript [] , soit avec la fonction membre at() .

Les deux renvoient une référence à l'élément à la position respective dans le std::vector (à moins que ce ne soit un vector<bool> ), de sorte qu'il puisse être lu et modifié (si le vecteur n'est pas const ).

[] et at() diffèrent par le fait que [] ne garantit aucune vérification des limites, alors que at() fait. L'accès aux éléments où index < 0 ou index >= size est un comportement indéfini pour [] , alors que at() génère une exception std::out_of_range .

Remarque: Les exemples ci-dessous utilisent l'initialisation de style C ++ 11 pour plus de clarté, mais les opérateurs peuvent être utilisés avec toutes les versions (sauf si marqué 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

Comme la méthode at() effectue la vérification des limites et peut générer des exceptions, elle est plus lente que [] . Cela rend [] code préféré où la sémantique de l'opération garantit que l'index est dans les limites. Dans tous les cas, les accès aux éléments des vecteurs se font à temps constant. Cela signifie que l'accès au premier élément du vecteur a le même coût (en temps) d'accès au deuxième élément, au troisième élément, etc.

Par exemple, considérez cette boucle

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

Ici, nous savons que la variable d'index i est toujours dans les limites, donc ce serait un gaspillage de cycles CPU pour vérifier que i dans les limites pour chaque appel à l' operator[] .

Les fonctions membres front() et back() permettent respectivement un accès de référence au premier et au dernier élément du vecteur. Ces positions sont fréquemment utilisées et les accesseurs spéciaux peuvent être plus lisibles que leurs alternatives en utilisant [] :

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}

Note : C'est un comportement indéfini pour appeler front() ou back() sur un vecteur vide. Vous devez vérifier que le conteneur n'est pas vide à l'aide de la fonction membre empty() qui vérifie si le conteneur est vide avant d'appeler front() ou back() . Voici un exemple simple d'utilisation de 'empty ()' pour tester un vecteur vide:

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;
}

L'exemple ci-dessus crée un vecteur avec une séquence de nombres de 1 à 10. Puis il extrait les éléments du vecteur jusqu'à ce que le vecteur soit vide (en utilisant 'empty ()') pour empêcher un comportement indéfini. Ensuite, la somme des nombres dans le vecteur est calculée et affichée pour l'utilisateur.

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]

Itérateurs:

Les itérateurs sont expliqués plus en détail dans l'exemple "Itération sur std::vector " et les itérateurs d' article. En bref, ils agissent de manière similaire aux pointeurs vers les éléments du vecteur:

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

Il est cohérent avec le standard que les itérateurs de std::vector<T> soient en réalité des T* , mais la plupart des bibliothèques standard ne le font pas. Ne pas le faire améliore à la fois les messages d'erreur, intercepte le code non portable et peut être utilisé pour instrumenter les itérateurs avec des contrôles de débogage dans les versions sans publication. Ensuite, dans les versions release, la classe qui entoure le pointeur sous-jacent est optimisée.

Vous pouvez conserver une référence ou un pointeur sur un élément d'un vecteur pour un accès indirect. Ces références ou pointeurs vers les éléments du vector restent stables et l'accès reste défini à moins que vous ajoutiez / supprimiez des éléments à ou avant l'élément dans le vector , ou que vous ne modifiiez la capacité du vector . C'est la même chose que la règle pour invalider les itérateurs.

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.

Utiliser std :: vector comme un tableau C

Il existe plusieurs manières d'utiliser un std::vector comme un tableau C (par exemple, pour la compatibilité avec les bibliothèques C). Cela est possible car les éléments d'un vecteur sont stockés de manière contiguë.

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

Avant C ++ 11, vous prendriez l'adresse du premier élément du vecteur pour obtenir un pointeur équivalent, si le vecteur n'est pas vide, ces deux méthodes sont interchangeables:

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

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

Remarque: Si le vecteur est vide, v[0] et v.front() sont pas définis et ne peuvent pas être utilisés.

Lorsque vous stockez l'adresse de base des données du vecteur, notez que de nombreuses opérations (telles que push_back , resize , etc.) peuvent modifier l'emplacement de la mémoire de données du vecteur, ce qui invalide les pointeurs de données précédents . Par exemple:

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

Invalidation de l'itérateur / pointeur

Les itérateurs et les pointeurs pointant dans un std::vector peuvent devenir invalides, mais uniquement lors de l'exécution de certaines opérations. L'utilisation d'itérateurs / pointeurs non valides entraînera un comportement indéfini.

Les opérations qui invalident les itérateurs / pointeurs incluent:

• Toute opération d’insertion modifiant la capacity du vector invalidera tous les itérateurs / pointeurs:

  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.

• Toute opération d'insertion, qui n'augmente pas la capacité, invalidera toujours les itérateurs / pointeurs pointant vers des éléments à la position d'insertion et au-delà. Cela inclut l'itérateur end :

  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.
  

• Toute opération de suppression invalidera les itérateurs / pointeurs pointant vers les éléments supprimés et vers tous les éléments au-delà des éléments supprimés. Cela inclut l'itérateur end :

  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= (copy, move ou else) et clear() invalideront tous les itérateurs / pointeurs pointant dans le vecteur.

Supprimer des éléments

Supprimer le dernier élément:

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

Supprimer tous les éléments:

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

Supprimer un élément par index:

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

Remarque: pour un vector supprimant un élément qui n'est pas le dernier élément, tous les éléments au-delà de l'élément supprimé doivent être copiés ou déplacés pour combler le vide, voir la note ci-dessous et std :: list .

Supprimer tous les éléments d'une plage:

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

Remarque: Les méthodes ci-dessus ne modifient pas la capacité du vecteur, mais uniquement la taille. Voir Taille et capacité du vecteur .

La méthode d' erase , qui supprime une série d'éléments, est souvent utilisée dans le cadre de l'idiome d' effacement-suppression . C'est-à-dire que std::remove déplace d'abord certains éléments à la fin du vecteur, puis les erase . Ceci est une opération relativement inefficace pour tous les indices inférieurs au dernier index du vecteur car tous les éléments après les segments effacés doivent être déplacés vers de nouvelles positions. Pour les applications critiques qui nécessitent une suppression efficace d'éléments arbitraires dans un conteneur, consultez std :: list .

Suppression d'éléments par valeur:

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}

Suppression d'éléments par condition:

// 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}

Supprimer des éléments par lambda, sans créer de fonction de prédicat supplémentaire

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()
);

Suppression d'éléments par condition à partir d'une boucle:

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
}

Bien qu'il soit important de ne pas augmenter , it en cas de suppression, vous devriez envisager d' utiliser une autre méthode lors de l' effacement puis à plusieurs reprises dans une boucle. Considérez remove_if pour une manière plus efficace.

Suppression d'éléments par condition à partir d'une boucle inverse:

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;
}

Notez quelques points pour la boucle précédente:

• Compte tenu d' un itérateur inverse , it en montrant un élément, la méthode de base donne le pointage régulier (non-retour) iterator au même élément.

• vector::erase(iterator) efface l'élément pointé par un itérateur et renvoie un itérateur à l'élément qui suit l'élément donné.

• reverse_iterator::reverse_iterator(iterator) construit un itérateur inverse à partir d'un itérateur.

Mettez tout à fait, la ligne it = rev_itr(v.erase(it.base())) dit: prendre l'itérateur inverse it , ont v d' effacement de l'élément pointé par son iterator régulière; prendre l'itérateur résultant, construire un itérateur inverse de celui - ci, et l' affecter à l'itérateur inverse it .

La suppression de tous les éléments à l'aide de v.clear() ne libère pas de mémoire ( capacity() du vecteur reste inchangé). Pour récupérer de l'espace, utilisez:

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

v.shrink_to_fit();

Le shrink_to_fit ne garantit pas vraiment de récupérer de l'espace, mais la plupart des implémentations actuelles le font.

Recherche d'un élément dans std :: vector

La fonction std::find , définie dans l’en-tête <algorithm> , peut être utilisée pour trouver un élément dans un std::vector .

std::find utilise l' operator== pour comparer les éléments pour l'égalité. Il renvoie un itérateur au premier élément de la plage qui est égal à la valeur.

Si l'élément en question n'est pas trouvé, std::find renvoie std::vector::end (ou std::vector::cend si le vecteur est 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)

Si vous devez effectuer de nombreuses recherches dans un grand vecteur, vous pouvez envisager de trier d'abord le vecteur avant d'utiliser l'algorithme binary_search .

Pour trouver le premier élément dans un vecteur qui remplit une condition, std::find_if peut être utilisé. En plus des deux paramètres donnés à std::find , std::find_if accepte un troisième argument qui est un objet fonction ou un pointeur de fonction vers une fonction de prédicat. Le prédicat doit accepter un élément du conteneur en tant qu'argument et renvoyer une valeur convertible en bool sans modifier le conteneur:

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

Conversion d'un tableau en std :: vector

Un tableau peut facilement être converti en un std::vector en utilisant std::begin et 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);
}

Une liste_initialisation C ++ 11 <> peut également être utilisée pour initialiser le vecteur à la fois

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

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

vecteur : L'exception à tant de règles, tant de règles

La norme (section 23.3.7) spécifie qu’une spécialisation du vector<bool> est fournie, qui optimise l’espace en empaquetant les valeurs bool , de sorte que chacune ne prenne qu’un seul bit. Comme les bits ne sont pas adressables en C ++, cela signifie que plusieurs exigences sur le vector ne sont pas placées sur le vector<bool> :

• Les données stockées ne doivent pas nécessairement être contiguës, donc un vector<bool> ne peut pas être transmis à une API C qui attend un tableau bool .
• at() , operator [] et dereferencing des itérateurs ne renvoient pas de référence à bool . Au lieu de cela, ils renvoient un objet proxy qui simule (imparfaitement) une référence à un bool en surchargeant ses opérateurs d'affectation. Par exemple, le code suivant peut ne pas être valide pour std::vector<bool> , car le déréférencement d'un itérateur ne renvoie pas de référence:

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

De même, les fonctions qui attendent un bool& argument ne peuvent pas être utilisées avec le résultat de l' operator [] ou at() appliqué au vector<bool> , ou avec le résultat du déréférencement de son itérateur:

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

L'implémentation de std::vector<bool> dépend à la fois du compilateur et de l'architecture. La spécialisation est implémentée en plaçant n Booleans dans la section adressable la plus basse. Ici, n est la taille en bits de la mémoire adressable la plus basse. Dans la plupart des systèmes modernes, il s'agit d'un octet ou de 8 bits. Cela signifie qu'un octet peut stocker 8 valeurs booléennes. C'est une amélioration par rapport à l'implémentation traditionnelle où 1 valeur booléenne est stockée dans 1 octet de mémoire.

Remarque: L'exemple ci-dessous montre les valeurs binaires possibles des octets individuels dans un vector<bool> traditionnel vs optimisé vector<bool> . Cela ne sera pas toujours vrai dans toutes les architectures. C'est toutefois un bon moyen de visualiser l'optimisation. Dans les exemples ci-dessous, un octet est représenté par [x, x, x, x, x, x, x, x].

std::vector<char> traditionnel stockant 8 valeurs booléennes:

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

Représentation binaire:

[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]

std::vector<bool> spécialisé stockant 8 valeurs booléennes:

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

Représentation binaire:

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

Notez que dans l'exemple ci-dessus, dans la version traditionnelle de std::vector<bool> , 8 valeurs booléennes occupent 8 octets de mémoire, alors que dans la version optimisée de std::vector<bool> , elles n'utilisent que 1 octet de mémoire. Mémoire. Il s'agit d'une amélioration significative de l'utilisation de la mémoire. Si vous devez transmettre un vector<bool> à une API de style C, vous devrez peut-être copier les valeurs dans un tableau ou trouver un meilleur moyen d'utiliser l'API si la mémoire et les performances sont menacées.

Taille et capacité du vecteur

La taille du vecteur est simplement le nombre d'éléments dans le vecteur:

1. La taille actuelle du vecteur est interrogée par la fonction membre size() . La fonction Convenience empty() renvoie true si la taille est 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. Le vecteur construit par défaut commence par une taille de 0:

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

3. L'ajout de N éléments à vector augmente la taille de N (par exemple, par les fonctions push_back() , insert() ou resize() ).

4. La suppression de N éléments du vecteur diminue la taille de N (par exemple par les fonctions pop_back() , erase() ou clear() ).

5. Vector a une limite supérieure de taille spécifique à l'implémentation, mais vous risquez de manquer de RAM avant de l'atteindre:

   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
   

Erreur commune: la taille n'est pas nécessairement (ou même généralement) 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] );
}

La capacité vectorielle diffère de la taille . Alors que la taille est simplement le nombre d'éléments dont dispose actuellement le vecteur, la capacité correspond au nombre d'éléments alloués / réservés à la mémoire. Cela est utile, car une (ré) attribution trop fréquente de trop grandes tailles peut être coûteuse.

1. La capacité actuelle du vecteur est interrogée par la fonction membre capacity() . La capacité est toujours supérieure ou égale à la taille :

   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. Vous pouvez réserver manuellement la capacité par fonction de reserve( N ) (elle change la capacité vectorielle en 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. Vous pouvez demander que la capacité excédentaire soit libérée par shrink_to_fit() mais l'implémentation n'a pas à vous obéir. Ceci est utile pour conserver la mémoire utilisée:

   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)
   

Vector gère en partie automatiquement la capacité, lorsque vous ajoutez des éléments, elle peut décider de croître. Les implémenteurs aiment utiliser 2 ou 1,5 pour le facteur de croissance (le nombre d'or serait la valeur idéale - mais peu pratique en raison du nombre rationnel). D'un autre côté, le vecteur ne diminue généralement pas automatiquement. Par exemple:

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

Vecteurs concaténants

Un std::vector peut être ajouté à un autre en utilisant la fonction membre 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());

Cependant, cette solution échoue si vous essayez d’ajouter un vecteur à lui-même, car le standard spécifie que les itérateurs donnés à insert() ne doivent pas appartenir à la même plage que les éléments de l’objet récepteur.

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

Si l'ordre des éléments dans le vecteur de réception n'a pas d'importance, compte tenu du nombre d'éléments dans chaque vecteur peut éviter des opérations de copie inutiles:

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

Réduire la capacité d'un vecteur

Un std::vector augmente automatiquement sa capacité au moment de l'insertion, mais ne réduit jamais sa capacité après la suppression de l'élément.

// 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)

Pour réduire sa capacité, nous pouvons copier le contenu d'un vecteur dans un nouveau vecteur temporaire. Le nouveau vecteur aura la capacité minimale nécessaire pour stocker tous les éléments du vecteur d'origine. Si la réduction de taille du vecteur d'origine était significative, la réduction de capacité pour le nouveau vecteur sera probablement significative. Nous pouvons alors échanger le vecteur d'origine avec le vecteur temporaire pour conserver sa capacité minimale:

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

v.shrink_to_fit();

Utilisation d'un vecteur trié pour la recherche rapide d'éléments

L' <algorithm> tête <algorithm> fournit un certain nombre de fonctions utiles pour travailler avec des vecteurs triés.

Une condition préalable importante pour travailler avec des vecteurs triés est que les valeurs stockées sont comparables à < .

Un vecteur non trié peut être trié en utilisant la fonction std::sort() :

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

Les vecteurs std::lower_bound() permettent une recherche efficace des éléments en utilisant la fonction std::lower_bound() . Contrairement à std::find() , cette fonction effectue une recherche binaire efficace sur le vecteur. L'inconvénient est qu'il ne donne que des résultats valides pour les plages d'entrées triées:

// 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!
}

Remarque: Si la valeur demandée ne fait pas partie du vecteur, std::lower_bound() renverra un itérateur au premier élément supérieur à la valeur demandée. Ce comportement nous permet d’insérer un nouvel élément à sa place dans un vecteur déjà trié:

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

Si vous devez insérer beaucoup d'éléments à la fois, il peut être plus efficace d'appeler push_back() pour tous les éléments et d'appeler ensuite std::sort() une fois tous les éléments insérés. Dans ce cas, le coût accru du tri peut compenser le coût réduit de l'insertion de nouveaux éléments à la fin du vecteur et non au milieu.

Si votre vecteur contient plusieurs éléments de la même valeur, std::lower_bound() essaiera de renvoyer un itérateur au premier élément de la valeur recherchée. Cependant, si vous devez insérer un nouvel élément après le dernier élément de la valeur recherchée, vous devez utiliser la fonction std::upper_bound() car cela entraînera moins de décalage des éléments:

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

Si vous avez besoin à la fois des itérateurs de limite supérieure et inférieure, vous pouvez utiliser la fonction std::equal_range() pour les récupérer efficacement avec un seul appel:

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;

Pour tester si un élément existe dans un vecteur trié (bien que non spécifique aux vecteurs), vous pouvez utiliser la fonction std::binary_search() :

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

Fonctions de retour de grands vecteurs

#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;
}

Rechercher max et min Element et index respectif dans un vecteur

Pour trouver le plus grand ou le plus petit élément stocké dans un vecteur, vous pouvez utiliser les méthodes std::max_element et std::min_element , respectivement. Ces méthodes sont définies dans l’ <algorithm> tête <algorithm> . Si plusieurs éléments sont équivalents au plus grand (plus petit) élément, les méthodes renvoient l'itérateur au premier élément de ce type. Renvoie v.end() pour les vecteurs vides.

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';

Sortie:

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';

Matrices utilisant des vecteurs

Les vecteurs peuvent être utilisés comme une matrice 2D en les définissant comme un vecteur de vecteurs.

Une matrice à 3 lignes et 4 colonnes avec chaque cellule initialisée à 0 peut être définie comme suit:

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}
                                         };

Les valeurs dans un tel vecteur peuvent être accédées de la même manière qu'un tableau 2D

int var = matrix[0][2];

Itérer sur toute la matrice est similaire à celui d'un vecteur normal mais avec une dimension supplémentaire.

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;
    }
}

Un vecteur de vecteurs est un moyen pratique de représenter une matrice, mais ce n'est pas le plus efficace: les vecteurs individuels sont dispersés dans la mémoire et la structure de données n'est pas compatible avec le cache.

De plus, dans une matrice appropriée, la longueur de chaque ligne doit être la même (ce n’est pas le cas pour un vecteur de vecteurs). La flexibilité supplémentaire peut être source d'erreurs.