Understanding C++ Containers in the C++ Standard Library

Containers classes are those that provide the means to hold elements and facilitates and have some sort of management and manipulation over it. When we talk about containers, the first thing that comes to mind is of Standard Template Library (STL). STL supplies quite a few sophisticated container implementations. Started as a separate library, STL heavily influenced the derivatives of container classes of the C++ standardized library in its present from. Though the standard library is a collection of many other functionalities apart from providing container classes, here we’ll focus on container classes only.

C++ Standard Library and STL

To allay the confusion, let’s get a terse overview of both the libraries. The C++ standard library provides various common functionalities used in everyday programming. These functionalities are made available to any standard C++ program. The ISO C++ standard provides the list of headers for the entire Standard library along with its core language support here. The library in its present form is quite extensive and many of its implementations are influenced by STL.

STL began as a third-party library prior to C++ being standardized. STL was the result of Alexander Stepanov’s research work on generic programming that opened a new horizon in the software development paradigm. Although STL is abandoned now, it nonetheless greatly influenced the shaping of the C++ standard library in much the same way as the boost library (2011) is influencing now.

Container Classes of the C++ Standard Library

Container classes are generic. That means they behave according to the type defined during declaration. For example, an array container will behave like an array of integers if it is declared as:

 array<int, 5> intarray={11,22,33};

of size=5. Similarly,

array<Person, 10> people;

defines an array of Person class object of size=10.

If we filter out some of the common container classes of C++ standard library, they may be further categorized as: Sequential containers, associative containers, container adapters, and partial containers.

Sequential Containers

Sequential containers are those that provide sequential access to the elements it holds. It’s a linear data structure, such as <array>, <list>, <forward_list>, or <deque>. Sequential containers are also called first-class containers. First-class containers provide a set of common characteristics and behavior in their implementation as a form of the pure container class. However, their internal representation structure varies. For example, array is a data structure of a simple container for consecutive allocation of memory, whereas list is a linked list implementation. They are all inherently linear.

Sequential container classes of the standard library are as follows:

Containers Headers Description
Array <array> Represents a container of fixed sized. Supports sequential access.
Vector <vector> Represents a dynamic array. Supports sequential access.
Deque <deque> Represents a double-ended queue where insertion and deletion can occur at both ends. Supports sequential access.
Forward list <forward_list> Represents a container that supports fast insertion and removal of elements from the container. Implemented as a single-linked list. Supports random access. Traversal is unidirectional.
List <list> Implemented as a doubly linked list. Supports random access, but not a fast a forward_list. Traversal is bidirectional.

A Quick Example

#include <iostream>
#include <string>
#include <array>

using namespace std;

class Person{
   private:
      string name;
      string email;
   public:
      inline Person(string n, string em){name=n, email=em;}
      inline string getPerson(){return name+" "+email;}
};

int main(int argc, char **argv)
{
   array<int, 5> oddNumbers={1,3,5,7,9};
   array<Person *, 5> people={new Person("Peter","peter@gmail.com"),
                              new Person("harry","harru@anymail.com"),
                              new Person("Tom","tom@somemail.com"),
                              new Person("Billy","billy@xmail.com"),
                              new Person("Sandy","sandy@gmail.com")};

   // using some common functions
   cout<<"Size = "<<oddNumbers.size()<<endl;
   cout<<"Max size = "<<people.max_size()<<endl;
   cout<<"Element at 1 = "<<people.at(1)->getPerson()<<endl;
   cout<<"First Element = "<<people.front()->getPerson()<<endl;
   cout<<"Last Element = "<<people.back()->getPerson()<<endl;

   // traversing container
   for(const auto &refer:oddNumbers){
      cout<<refer<<' ';
   }

   // using [] operator directly to change a value
   oddNumbers[4]=999;

   cout<<endl;

   // using iterators
   array<int,5>::const_reverse_iterator revi;
   for(revi = oddNumbers.rbegin(); revi != oddNumbers.rend(); revi++)
      cout << *revi<<' ';

   cout<<endl;

   // traversing container
   for(const auto &refer2: people){
      cout<<refer2->getPerson()<<endl;
   }

   return 0;
}

Associative Containers

Associative containers are non-linear and store elements as key/value pairs, such as <map>, <multimap>, <set>, and <multiset>. They are typically used to locate elements in the container as efficiently as possible.

Associative container classes of the standard library are as follows:

Containers Headers Description
Map <map> Represents a container of key-value pairs, where each key must be distinct. Sorting uses the Compare function on the key type. Typically represented as red-black trees. Traversal operations have performance overhead and are inefficient.
Multimap <multimap> It is very similar to map in all aspects, except that it allows storage of duplicate keys.
Set <set> Represents a sorted set of distinct key objects. Sorting uses the Compare function on the key type. Typically represented as red-black trees. Traversal operations have performance overhead are and inefficient.
Multiset <multiset> It is very similar to set in all aspects, except that it allows storage of duplicate objects.
Unordered set <unordered_set> Represents a container for unsorted unique objects of type Key. Because this container uses hash functions to store elements, accessing any element is fast and exact.
Unordered multiset <unordered_multiset> It is very similar to unordered_set in all aspects, except that it allows storage of duplicate Key type objects.
Unordered map <unordered_map> Represents a container for unsorted key-value pairs of distinct keys. Because this container uses hash functions to store elements, accessing any element is fast and exact.
Unordered multimap <unordered_multimap> It is very similar to unordered_map in all aspects, except that it allows storage of duplicate keys.

A Quick Example

#include <iostream>
#include <string>
#include <set>

using namespace std;

class Person{
   private:
      string name;
      string email;
   public:
      inline Person(string n, string em){name=n, email=em;}
      inline string getPerson(){return name+" "+email;}
};

int main(int argc, char **argv)
{
   set<int> oddNumbers={1,3,5,7,9};
   set<Person *> people={new Person("Peter","peter@gmail.com"),
                         new Person("harry","harry@anymail.com"),
                         new Person("Tom","tom@somemail.com"),
                         new Person("Billy","billy@xmail.com"),
                         new Person("Sandy","sandy@gmail.com")};

   // using some common functions
   cout<<"Size = "<<oddNumbers.size()<<endl;
   cout<<"Max size = "<<people.max_size()<<endl;

   // traversing container
   for(const auto &refer:oddNumbers){
      cout<<refer<<' ';
   }


   cout<<endl;

   // using iterators
   set<int>::const_reverse_iterator revi;
   for(revi = oddNumbers.rbegin(); revi != oddNumbers.rend(); revi++)
      cout << *revi<<' ';

   cout<<endl;

   // traversing container
   for(const auto &refer2: people){
      cout<<refer2->getPerson()<<endl;
   }

   return 0;
}

Container adapters: These are special containers that enable a program to view a sequential container in a constrained manner. For example, <queue>, <priority_queue>, and <stack>. Though they are internally a linear implementation, they behave in a special way. For example, queue acts in a FIFO (first-in-first-out) manner, whereas stack acts in a LIFO (last-in-first-out) manner.

Container Adapter classes of the standard library are as follows:

Containers Headers
Stack <stack>
Queue <queue>
Priority Queue <queue>

A Quick Example

#include <iostream>
#include <string>
#include <stack>

using namespace std;

class Person{
   private:
      string name;
      string email;
   public:
      inline Person(string n, string em){name=n, email=em;}
      inline string getPerson(){return name+" "+email;}
};

int main(int argc, char **argv)
{
   stack<int> oddNumbers;
   oddNumbers.push(1);
   oddNumbers.push(3);
   oddNumbers.push(5);
   oddNumbers.push(7);
   oddNumbers.push(9);
   stack<Person *> people;
   people.push(new Person("Peter","peter@gmail.com"));
   people.push(new Person("harry","harru@anymail.com"));
   people.push(new Person("Tom","tom@somemail.com"));
   people.push(new Person("Billy","billy@xmail.com"));
   people.push(new Person("Sandy","sandy@gmail.com"));

   // using some common functions
   cout<<"Size = "<<oddNumbers.size()<<endl;

   while(!oddNumbers.empty()){
      cout<<oddNumbers.top()<<' ';
      oddNumbers.pop();
   }

   cout<<endl;

   while(!people.empty()){
      cout<<people.top()->getPerson()<<endl;
      people.pop();
   }
   return 0;
}

Partial Containers

Partial containers are those that behave like a container but do not provide all the capabilities of a first-class container. Some of them behaves like a primitive data type although they are not. For example, we can use string as a simple data type object and deal with it in a similar manner.

There are many partial container classes that we often use without considering them to be containers. The string class is very common among such containers. There is another container, called bitset. The bitset class makes it easy to create and manipulate bit sets that are useful for representing bit flags. It is very easy to perform bitwise logical operations with this container class. Let’s see how to it use with a very rudimentary example.

A Quick Example

#include <iostream>
#include <string>
#include <bitset>

using namespace std;

int main(int argc, char **argv)
{
   bitset<9> pattern1("10101100");
   bitset<9> pattern2("01011100");

   cout<<"Pattern1 = "<<pattern1.to_string()<<" Pattern2 =
      "<<pattern2.to_string()<<endl;

   cout<<"Pattern1 Size = "<<pattern1.size()<<endl;
   cout<<"pattern1 Count = "<<pattern1.count()<<endl;
   cout<<"Number of bits in Pattern 1 that are set =
      "<<pattern1.any()<<endl;

   cout<<"Logical OR Operation "<<(pattern1 | pattern2)<<endl;
   cout<<"Logical AND Operation "<<(pattern1 & pattern2)<<endl;
   cout<<"Logical XOR Operation "<<(pattern1 ^ pattern2)<<endl;
   cout<<"LEFT SHIFT Operation pattern1 "<<(pattern1 << 2)<<endl;
   cout<<"RIGHT SHIFT Operation pattern2 "<<(pattern2 >> 2)<<endl;

   return 0;
}

Conclusion

There there various types of container classes. Some methods are quite common, such as the generic size() operation. This method returns the number of elements currently present in the container. Each container should be able to say how many elements it contains. This operation is implemented as a member function to all container classes. This commonality, apart from leveraging the ease of use, leverages extensibility. We can inherit the existing container class and add a few more operations to give it a new form according to our customization needs.

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