C++ STL: Iterators and Containers

This article was contributed by Eric Sanchez

Environment: ANSI C++

As one explores further into the standard template library, there must be a basic understanding of a few trivial terms. Perhaps the two most important are containers and iterators.

Container Classes

As the name implies, instances of container classes are objects that “contain” other objects. C++ STL comes with a rich set of such components that aid in storing collection of values. Although not all, it includes a vast majority of the main non-primitive and significant data structures.

List of STL’s containers:

Iterators

As most data structures, containers would be rendered useless if there were no methods to retrieve or cycle through the elements. Here’s where iterators come in handy. As the name suggests, iterators are used to iterate through the objects and thus provide an opportunity to have access to the elements stored in a container.

Each container class permits the use of certain types of iterators depending on the mechanism used to store the items. Among these are the widely known Random Access Iterator. Just as arrays, it allows quick access to a given element by simply providing the index. However, if you are familiar with linked lists and a few other types of strucutres, you will know that it is not possibe to have access to a specific element without sequentially scrolling though the list. For this, given a base location, we can move through by using the Forward Iterator. There are a few additional types, such as Trivial Iter and Bidirectional.

With that in mind, as later we go through the different container classes, you will begin grasping the concept of iterators in more details. However, there are still few basics worth knowing for now.

When dealing with containers that permit random access, such as vectors and deques, one can simply access the elements in a similar way as arrays.
For example, if My_vecs is a vector that will hold integers, we could access the value in the 8th position by treating it as if it was an array:

int val = My_vec[7];

* Do not forget that the indexes begin at 0.
Non random access operators and even those that permit rand access contain two basic functions: begin() and end(). The first one returns an iterator pointing to the first element while the latter signals the end. It is what is known as the past-the-end value, meaning it will point to the position right after the last element, and not to the last element.
The way to declare an iterator object is by:

container<types> :: iterator name;

For example to get the first position of My_vec, we would:

vector<int>::iterator pos = My_vec.begin();

Although with vectors it is not necessary, suppose it was a list instead. To obtain the pointer to the next item, we could use the advance function, found in #include <iterator>.

advance(pos,1);

Where 1 is the amount of positions to move the iterator through. Now pos would point to the second element. Most of the time, we could alternatively use pos++ rather than advance.
Finally, as in pointers, to get the actual value of the iterator, we use *. For example, if My_vec was a vector and advance was performed, int r = *pos, would assign the value 1 to r.

More about iterators will be discussed as needed.

Vectors

A vector is a container used to store a series of related data values. Abstractly, it can thought of as an advanced and more useful array of the same object. Imagine an array of integers:

int demo[]={1,2,3};

What would happen if you had to increase or decrease the size of the array, insert or remove elements, assign one array to another, etc. You might have to deal with messy operations such as new and delete. A vector helps in many these issues. A vector could be created to hold the same elements, it can be copied, elements added to it, resized, and so on very easily. A vector stores the data in a sequential order and thus it permits random access.

There are various ways to create a vector.
As usual, you have to include the header, in this case #include <vector>. You proceed by adding using namespace std or specifying std:: before the container.
The constructur I most frequently use is:

vector<T> name;

Where T represents the name of an object and name the variable name. E.g.:

vector<int> cool;
vector<string> cool1;

Initially, the vector would be emptry. To add elements to the back of the vector, one generally uses the member function push_back(value). To add 1,2,3 to the vector:

vector<int> abc; //abc = .

abc.push_back(1); //abc = 1.
abc.push_back(2); //abc = 1,2.
abc.push_back(3); //abc = 1,2,3.

Notice how push_back automatically resizes the vector by one. Push_back is usually O(1) if no reallocation of the buffer is necessary. However, if we know the number of elements the vector will have, by specifying the size of the vector initially, we would avoid the resizing done by push_back and thus slightly increase its efficiency. To do this, we may use the constructor vector<T> name (int); where int represents the number of elements it will have.

vector<int>BOTW(3);
BOTW.push_back(1);
BOTW.push_back(2);
BOTW.push_back(3);

Since it was resized initially, not additionally resizing is done by using push_back. It is random access and the size is already established, and thus we could use subscripts to add the values:

vector<int> VMC(3);
for (int i=1;i<4; i++)VMC [i] = i;

Equally, to get the element of a given index, we can use subscripts.

int num = VMC[0];

You might have wondered if there was an easier way to initialize the values so that if we have tons of item, we don’t have a million a push_backs or []. There a few ways to this. Obviously, you could create an array with the values and use a loop to insert it into the vector. However, an alternative way exists:

string programmers[] = {”Hussainweb”, “BOTW”, “VMC”, “Ziggy^3″, “Ray45512″,
“Mallowman”, “PRTSoft”, “MaxK”,”Pelican”, “Moonie”, “Ruudje”, “And Many More”};
//To add all these elements to a vector, we can simply to do it as:
vector <string> prog (programmers, programmers + sizeof(programmers)/sizeof(string));

As you know, we can use indexes to get and set values. However, that will not prevent you from accessing memory outsize the boundaries of the vector. To display a message if this happens, we can use .at(index);

string name = prog.at(12);
prog.at(12) = name;

Suppose 12 is outside the vector, the program would come to a halt.

Finally to delete the last element, we use pop_back().

prog.pop_back();

Some other useful member functions:

That’s only a few of the many other functions of vectors, not to mention algorithms that can be performed.

Tags: STL, vector