C++ vector insights

Question

Hi, I am a little bit frustrated of how to use vectors in C++. I use them widely though I am not exactly certain of how I use them. Below are the questions?

1. If I have a vector lets say: std::vector<CString> v_strMyVector, with (int)v_strMyVector.size > i can I access the i member: v_strMyVector[i] == "xxxx"; ? (it works, though why?)

2. Do i always need to define an iterator to acces to go to the beginning of the vector, and lop on its members ?

3. What is the purpose of an iterator if I have access to all members of the vector directly (see 1)?

Thanks in advance, Sun

Answer 1

1. It returns a reference.
2. No,, because vector has random access. However, you do for other types (e.g. list, which is a doubly-linked list)
3. To unify all the collections (along with other types, like arrays). That way you can use algorithms like std::copy on any type that meets the requirements.

Answer 2

1. It works only because there's no bounds checking for operator[], for performance reason. Doing so will result in undefined behavior. If you use the safer v_strMyVector.at(i), it will throw an OutOfRange exception.

   It's because the operator[] returns a reference.

2. Since vectors can be accessed randomly in O(1) time, looping by index or iterator makes no performance difference.

3. The iterator lets you write an algorithm independent of the container. This iterator pattern is used a lot in the <algorithm> library to allow writing generic code easier, e.g. instead of needing N members for each of the M containers (i.e. writing M*N functions)

   std::vector<T>::find(x)
   std::list<T>::find(x)
   std::deque<T>::find(x)
   ...
   std::vector<T>::count(x)
   std::list<T>::count(x)
   std::deque<T>::count(x)
   ...
   

   we just need N templates

   find(iter_begin, iter_end, x);
   count(iter_begin, iter_end, x);
   ...
   

   and each of the M container provide the iterators, reducing the number of function needed to just M+N.

Answer 3

1. Workd because the [] operator is overloaded:

   reference operator[](size_type n)

See http://www.sgi.com/tech/stl/Vector.html

1. Traversing any collection in STL using iterator is a de facto.

2. I think one advantage is if you replace vector by another collection, all of your code would continue to work.

Answer 4

std::vector is a type of sequence that provides constant time random access. You can access a reference to any item by reference in constant time but you pay for it when inserting into and deleting from the vector as these can be very expensive operations. You do not need to use iterators when accessing the contents of the vector, but it does support them.

Answer 5

Regarding your second point, the idiomatic C++ way is not to loop at all, but to use algorithms (if feasible).

Manual looping for output:

for (std::vector<std::string>::iterator it = vec.begin(); it != end(); ++it)
{
    std::cout << *it << "\n";
}

Algorithm:

std::copy(vec.begin(), vec.end(),
          std::ostream_iterator<std::string>(std::cout, "\n"));

Manual looping for calling a member function:

for (std::vector<Drawable*>::iterator it = vec.begin(); it != end(); ++it)
{
    (*it)->draw();
}

Algorithm:

std::for_each(vec.begin(), vec.end(), std::mem_fun(&Drawable::draw));

Hope that helps.

Answer 6

1. That's the idea of vectors, they provide direct access to all items, much as regular arrays. Internally, vectors are represented as dynamically allocated, contiguous memory areas. The operator [] is defined to mimic semantics of the regular array.

2. Having an iterator is not really required, you may as well use an index variable that goes from 0 to v_strMtVector.size()-1, as you would do with regular array:

   for (int i = 0; i < v_strMtVector.size(); ++i) {
       ... 
   }
   

   That said, using an iterator is considered to be a good style by many, because...

3. Using an iterator makes it easier to replace underlying container type, e.g. from std::vector<> to std::list<>. Iterators may also be used with STL algorithms, such as std::sort().