Working with Standard Library Containers and Iterators in C++

The Standard C++ library offers a host of powerful, template-based components that implements data structure for common containers and iterators. It is vital for C++ programmers to know and use them for many reasons: one being they are time tested and part of the Standard Library and secondly because they are ready-made and can be easily plugged into the existing code. This article focuses on the idea of container and iterators and some of the key concepts related to them.

Overview

The C++ Standard Library offers a set of template-based, reusable components, ideal for a programmer to use in a way that best fits their interest. They typically are an implementation of common data structures and algorithms that work upon those structures. Historically, they are part of a Standard Template Library (STL) because they depend on the idea of C++ templates. The C++ Standard Document refers to them as a part of its standard library features. Over the years and with each new revision of the C++ language, the library has expanded. The container classes are central to the library of generic algorithms. They let us write efficient program without the worry of bookkeeping tasks such as memory management; you can focus more on the problem at hand. Moreover, these library classes are tested and optimized to perform efficiently. Therefore, there is hardly any reason to not use them whenever we can.

Containers

Containers are data structures capable of storing objects of almost any data type, with some restrictions. It is a generic storage that can be used and reused whenever necessary storing objects of any type. This power is derived from to the use of templates in its design. Typically, there are three types of containers: first-class, adapter, and near container. Each of them has its own set of member functions. Some functions are common to more than one container.

Types of Containers

The containers of the Standard Library can be divided into four major categories: sequential, ordered associative, unordered associative, adapters.

Sequence Containers

As the name suggests, the sequence containers follow a linear data structure. Conceptually, this means that the contents are lined up in a row as we typically see in the case of arrays or linked lists data structures. Elements in these containers can be quickly stored; however, retrieving one is not that efficient. The following classes are representative of this type of containers.

  • The array class has a fixed size but provides direct access to its content.
  • The vector offers quick insertion and deletion capability from the end of the container with direct access to any element.
  • The deque, or the double-ended-queue, offers element insertion and deletion at both the end of the container with direct access to its content like the array class.
  • The forward _list is a singly linked list, so no fixed size can grow dynamically with the increasing number of elements and offers rapid insertion and deletion capability.
  • The list is implemented as a doubly linked list as a result iteration to and fro is rapid and fluid.

Associative Containers

The associative containers, on the other hand, follow non-linear data structures. They store elements in the form of key-value pairs. These keys are immutable; that means, once set they cannot be modified. These types of containers are ideal for quickly locating elements in the container but carry an extra baggage of paired (key and value) elements. According to the arrangement of the elements stored in the container, an associative container can be ordered and unordered.

Ordered associative containers store elements in an ordered manner whereas the unordered associative containers store elements in the manner they arrive without imposing any order in them.

  • Like the mathematical set, the set and unordered_set containers do not allow duplicate elements and have a quick lookup capability.
  • The multiset and unordered_multiset have the same capability as the set, except that they allow duplicate elements to be stored in the container.
  • The map and unordered_map containers facilitate one-to-one mapping of elements; therefore, duplicate elements can be stored and have a quick lookup capability.
  • The multimap and unordered_multimap containers facilitate one-to-many mapping. This is the key difference between map and multimap. Other features are the same as map.

The sequence and associative containers together form the genre of first-class containers.

Container Adapters

The container adapters are basically a constrained version of sequential containers, something like the string class, which basically is also a sequence container, but the constraint is that it can store only character data. Much in the same way, the container adapters re implemented by using sequence container, yet they behave in a distinct manner. For example,

  • The stack acts with the elements in last-in, first-out (LIFO) fashion,
  • The queue acts in first-in, first-out fashion,
  • while in a priority_queue, the highest priority elements are retrieved first.

Therefore, these types of containers are termed as adapters to the container or container adapter.

Iterators

The iterators are nothing but pointers in different shapes, typically used to manipulate first-class container elements. By using pointers as iterators, we can manipulate built-in arrays of standard library algorithms. But, it is convenient to use iterators in association with containers and manipulate the elements it contains. The iterators can help in reducing many lines of code in the process of manipulation.

Iterators typically hold state information of the particular container it is associated with. Some of the  iterator operations are common across a container. For example, the dereference operation is signified by the operator (*). Similarly, the ++ operation on the iterator indicates moving to the next element in the container it points. There are common functions, called begin and end, provided by all first-class containers. The invocation of begin always returns an iterator to point to the first element of the container and end sets iterator to point to the last element of the container.

Types of Iterators

There are different types of iterators, each providing specific type of functionality. The complexity of functionality and features of the iterator increases in the order, such as input/output iterator, forward iterator, bidirectional iterator, and random-access iterator.

  • The input iterator can be used read elements from the container. It can move only in a forward direction, one by one element at a time. The output iterator, on the other hand, is used to write elements to the container. It also moves only in a forward direction, one element at a time.
  • The forward iterator combines the functionality of input and output iterators and can be used to pass through in one direction, multiple times.
  • The bidirectional iterators can move in a backward direction, in addition to providing all the functionality of the forward iterator.
  • The random-access iterator improves upon the bidirectional iterator functionality with the direct ability to access container elements by hopping over an arbitrary number of elements.

Note that all containers do not support all types of iterators. For example, vector, array, and deque support the random-access iterator, but list supports only bidirectional, and forward_list only supports forward. All associative containers only support bidirectional iterators. The container adapter, such as stack, queue, and priority_queue do not support any iterators.

A Quick Example

#include <iostream>
#include <iomanip>
#include <array>
#include <iterator>
using namespace std;

int main()
{
   array<int, 7> arr = { 0, 1, 1, 2, 3, 5, 8 };

   array<int, 7>::iterator iter;

   for(iter = arr.begin(); iter < arr.end(); iter++)
      cout<<*iter<<" ";

   cout<<endl;

   iter = arr.begin();

   advance(iter,4);
   cout<<*iter<<endl;

   auto pa = prev(iter,2);
   cout<<*pa<<endl;

   auto pb = next(iter,1);
   cout<<*pb<<endl;

   return 0;
}

Conclusion

There are many algorithm and data structure implementations in the Standard C++ Library. The concept of container and iterator is the first to begin with and is perhaps the most frequently used in C++ programs. Just remember, containers can be sequential, and associative (key-value pairs) and adapters (constrained) and iterators are convenient pointers to manipulate the container elements.

Manoj Debnath
Manoj Debnath
A teacher(Professor), actively involved in publishing, research and programming for almost two decades. Authored several articles for reputed sites like CodeGuru, Developer, DevX, Database Journal etc. Some of his research interest lies in the area of programming languages, database, compiler, web/enterprise development etc.

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read