A very useful STL container: vector

Author: Razvan MIHAIU
razvan_rem@rem_mihaiu.name (please remove '_rem' and 'rem_')
From: www.mihaiu.name
Date: 15/01/2002




Most experimented C/C++ programmers agree that the use of array is difficult and prone to errors; it is always easy to reference elements past the end of array. This kind of bug is especially hard to track since it will not occur all the time, and what is worse is that it has a tendency of appearing when the program is under heavy stress. Also, counting the actual number of elements from an array is not an easy task.

The STL has a very good replacement for arrays: the vector container. What is so wonderful about this container is that you can use it much like an array, thus the learning curve is very smooth.

Unlike an array a vector is automatically managing its size. While there is still memory you can always insert elements into it. The programmer is not forced to guess the maximum number of required elements and to allocate that number right from the start.

Vector operations:

  1. Initialization:
  2. Inserting elements at the end of the vector:

    The function that will perform this operation is push_back; thus, to insert an element in our vector we will do:

    temp_area.push_back(obj);

    Note A1:

    The [ ] operator is NOT inserting elements in a vector. The [ ] operator should only be used to access elements.

    The following code is not correct:

    vector <CAtom> temp_area; temp_area.reserve(100); temp_area[10];

    After the above code the size() member function will return 0.

    Note A2:

    On all the platforms that I know the above code will not crash the application. Even so, its behavior is undefined. It is illegal to call the [ ] operator for an index out of the range 0..size-1.

    Note B:

    When inserting elements in a vector reallocation will occur if the vector is too small to contain all the required elements. When reallocation occurs the vector's size will be doubled and all iterators (for now think to an iterator like to a special kind of pointer) and references will become invalid.

    Practically you can think of it this way: an STL vector is just an array. When reallocation occurs all the vector's elements are copied to a new location, thus any pointers to the old vector will become invalid.

  3. Inserting elements anywhere in the vector:

    Warning:

    This is an expensive operation; if you need this functionality often then consider using a list instead.

    If reallocation occurs, the vector's size will double and all iterators and references will become invalid. If the reallocation will not occur then the iterators will become invalid from the point of the insertion to the end of the vector.

    Note:

    For a vector only the methods push_back() and pop_back() are implemented. Their logical pair: push_front() and pop_front() are not implemented because they cannot be implemented in constant time.

  4. Deleting elements

    Warning:

    This is an expensive operation; if you need this functionality often then consider using a list instead.

    // erase the element with the index 1 v.erase(& v[1]); // erase all elements between index 4(inclusive) and 7(exclusive) //v.erase(& v[4],& v[7]); // erase the first element using iterators v.erase(v.begin());

    The last operation will assign all elements to the previous one and it will destruct the last element. Because the vector will actually shrink no reallocation will occur but all the iterators will be invalidated.

    Note:

    Before deleting elements from a vector make sure that the vector is not empty.

  5. How to use vectors with iterators
    int jj = 0; vector <int>::iterator it; it = v.begin(); while (it != v.end()) { // derefence the iterator and do some stuff with it *it = jj; // increment the iterator it++; }
  6. How to sort a vector

    The vector is sorted with a template function called sort. Before sorting a vector the developer must define the "<" operator for the contained object.

    Sample code:

    // first we define some class: struct CAtom { int age; string name; public: CAtom():age(0){name = "";} CAtom(int age, string name) { this->age = age; this->name = name; } }; // second, we define the "<" operator for the preceeding class; bool operator < (const CAtom& left, const CAtom& right) { if (left.age < right.age) return true; return false; } vector <CAtom> my_vector; /* SKIP CODE... */ // we can sort using iterators: sort(my_vector.begin(), my_vector.end()); // we can sort using simple pointers: // some portion of the vector sort(&my_vector[4], &my_vector[10]); // the whole vector sort(&my_vector[0], &my_vector[my_vector.size()]);
  7. How to count the number of times a certain object appears in a vector
    vector <int> v; for (int ii=0; ii<10; ii++) v.push_back(ii); cout << "Vector initialised to:" << endl; for (ii=0; ii<10; ii++) cout << v[ii] << ' ' ; cout << endl; int nn = 0; int searched_value = 4; n = count (v.begin(), v.end(), searched_value); cout << "The value " << searched_value << " is found " << nn << " times inside the vector!" << endl;










Best regards,
Razvan MIHAIU
15/01/2002 - Paris, France



Razvan Mihaiu � 2000 - 2024