Harold Serrano

View Original

Traversing containers the smart way in C++

For a while I tried to avoid using iterators in my engine. If I had to traverse the elements of a vector, I would normally do it like this:

for(int i=0;i<v.size();i++){
        std::cout<<v.at(i);
    }

However, I realized that the above method is not efficient. When you start developing a game engine you need to start thinking about efficiency.

So what are Iterators? Iterators are an efficient method provided by C++ to traverse the elements of any type of container such as: Vectors, Deques, Lists, etc. An iterator represents a certain position in a container.

Each type of container has their own Iterators implementation. Thus before you use Iterators you need to declare them with the type of container they will operate on. For example:

//To use iterators in a vector
std::vector<int>::iterator pos;

//To use iterators in a list
std::list<char>::iterator pos;

Every container defines two types of iterators:

  • container::iterator - Iterate over elements in read/write mode.
  • container::const_iterator - Iterate over elements in read-mode only.

Every Iterator have the following methods:

  • begin(): returns an iterator that represents the beginning of the elements in the container.
  • end(): returns an iterator that represents the end of the elements in the container. Note that this position is the position behind the last element.

So to iterate over a vector-container you do the following:

//Fill a vector with data
std::vector<int> v = { 0, 1, 5, 3, 4, 5, 6, 7, 5, 9 };

//Declare the iterator
std::vector<int>::iterator pos;

//Loop through the vector with an iterator and get the value of vector in the current iterator position
for (pos=v.begin(); pos!=v.end(); ++pos) {
    std::cout<<*pos;
}

If you don't want to modify the values of the vector, then you can declare your iterator as const_iterator. This means that from the iterator point of view, all elements in the container are constants.

So, should you use iterators instead? Definitely!! I think they are safer and way more efficient. Give them a try :)