An overview of Generic Containers in C++

In C++, a container is a class template that provides a way to store and manipulate a collection of objects of the same type. Generic containers are container classes that can be used with any type of object, such as integers, floats, strings, or user-defined types.

Container classes are the solution to a specific kind of code reuse problem. They are building blocks used to create object-oriented programs. They make the internals of a program much easier to construct. A container class describes an object that holds other objects. Container classes are so important that they were considered fundamental to early object-oriented languages. So it became natural that C++ compilers also include a container class library.

The C++ approach to containers is based on templates. The containers in the standard C++ library represent a full complement of data structures designed to work well with the standard algorithms and to meet common software development needs.

Table of Contents

• Containers and Iterators
  • Inheriting from STL containers
  • Understanding C++ Iterator Types and Their Usage
  • Iterators in Reversible Containers in C++
  • C++ Iterator Categories
  • Iterator Invalidation
• The Basic Sequences
  • Basic Sequence Operations
• The std:vector Class
  • Inserting elements in Vectors
  • Removing elements from Vectors
• The std:deque Class
• The std:list Class
  • Special list operations
• Creating your own Containers
• STL extensions
• Non-STL containers

Containers and Iterators

Any good object-oriented programming language comes with a set of containers. In C++, it’s the Standard Template Library. In some libraries, a generic container is considered good enough for all needs, and in others (C++ in particular) the library has different types of containers for different needs: a vector for consistent access to all elements, and a linked list for consistent insertion at all elements, for example, so you can choose the particular type that fits your needs. These containers can include sets, queues, hash tables, trees, stacks, and so on.

The C++ standard library provides several generic container classes, including:

1. std::vector: a dynamic array that can be resized at runtime.
2. std::list: a doubly-linked list that supports constant-time insertion and removal of elements.
3. std::deque: a double-ended queue that supports constant-time insertion and removal at both ends.
4. std::set and std::multiset: containers that store elements in sorted order, and allow for efficient search, insertion, and deletion of elements.
5. std::map and std::multimap: containers that store key-value pairs in sorted order, and allow for efficient search, insertion, and deletion of elements based on the keys.

These container classes are designed to be generic, which means that they can store objects of any type, as long as the objects support certain operations, such as copy construction and assignment, equality comparison, and ordering.

All containers have some way to put things in and get things out. The way you place something into a container is fairly obvious. There’s a function called “push” or “add” or a similar name. Fetching things out of a container is not always as apparent; if an entity is array-like, such as a vector, you might be able to use an indexing operator or function. But in many situations this doesn’t make sense. Also, a single-selection function is restrictive. What if you want to manipulate or compare a group of elements in the container?

The solution, of course, is an iterator, which is an object whose job is to select the elements within a container and present them to the user of the iterator. As a class, an iterator also provides a level of abstraction, which you can use to separate the details of the container from the code that’s accessing that container.

The container, via the iterator, is abstracted to be simply a sequence. The iterator lets you traverse that sequence without worrying about the underlying structure that is, whether it’s a vector, a linked list, a set, or something else. This gives you the flexibility to easily change the underlying data structure without disturbing the code in your program that traverses the container. Separating iteration from the control of the container traversed also allows having multiple iterators that traverse the same container simultaneously.

Inheriting from STL containers

In C++, the Standard Template Library (STL) provides powerful container classes that allow you to quickly and easily manage collections of objects. In many cases, you may want to create a new class that uses one of these container classes, such as a vector or list.

When deciding whether to use composition (creating a member object of the container class) or inheritance (creating a derived class from the container class), the general guideline is to prefer composition. However, when working with STL container classes, it is often more convenient to inherit from the container class, because so many existing algorithms and functions in the STL are designed to work with these container types.

For example, if you need to create a class that manages a list of strings, you might want to use a vector as the underlying container. In this case, it would make sense to inherit from the vector class, rather than creating a member object of type vector.

Overall, inheriting from STL containers can be a useful technique for creating new classes that use these powerful container classes. Here’s an example of how to inherit from the std::vector container class to create a new class that provides additional functionality:

In this example, the MyVector class inherits from std::vector<std::string>, and provides two additional member functions: print() and append(). The print() function prints all the elements of the vector to the console, and the append() function adds a new string to the end of the vector.

In the main() function, we create an instance of MyVector, add three strings to it using the append() function, and then print the contents of the vector using the print() function.

Understanding C++ Iterator Types and Their Usage

As mentioned earlier an iterator is an abstraction that allows code to be generic, that is, to work with different types of containers without knowing the underlying structure of those containers. Most containers support iterators . You can always say:

to produce the types of the iterators produced by that container. Every container has a begin() member function that produces an iterator indicating the beginning of the elements in the container, and an end() member function that produces an iterator which is the as the past-the-end marker of the container. If the container is const begin() and end() produce const iterators, which disallow changing the elements pointed to (because the appropriate operators are const).

All iterators can advance within their sequence (via operator++) and allow == and != comparisons. Thus, to move an iterator it forward without running it off the end, you say something like:

in which pastEnd is the past-the-end marker produced by the container’s end() member function.

In C++, an iterator is an object that allows you to access the elements of a container (such as an array, vector, or list) in a sequential manner. Iterators are a key feature of the C++ Standard Template Library (STL), and are used extensively in algorithms and container classes.

Here’s an example of using an iterator to traverse a vector of integers:

In this example, we create a std::vector object myvec that contains five integers. We then use a for loop with an iterator to traverse the vector and print the contents to the console.

The myvec.begin() function returns an iterator pointing to the first element of the vector, and myvec.end() returns an iterator pointing to the position after the last element. We initialize the it variable to the beginning of the vector using myvec.begin(), and then use the * operator to dereference the iterator and access the value of the current element.

The loop continues until the iterator it is equal to myvec.end(), at which point we have reached the end of the vector.

Overall, iterators provide a flexible and efficient way to access the elements of a container in a sequential manner, and are a key feature of the C++ language and STL.

Iterators in Reversible Containers in C++

In C++, an iterator is an object that allows you to access the elements of a container in a sequential manner. In addition to forward iterators, the C++ Standard Template Library (STL) also provides reverse iterators, which allow traversal in the opposite direction. Reverse iterators are useful for iterating over containers in reverse order, or for implementing algorithms that require bidirectional traversal.

Here’s an example of using a reverse iterator to traverse a std::vector of integers in reverse order:

In this example, we use the rbegin() and rend() member functions of std::vector to obtain reverse iterators pointing to the last element and one position before the first element, respectively. We then use a for loop with a reverse iterator rit to traverse the vector in reverse order, and print the contents to the console.

The myvec.rbegin() function returns a reverse iterator pointing to the last element of the vector, and myvec.rend() returns a reverse iterator pointing to the position before the first element. We initialize the rit variable to the beginning of the vector using myvec.rbegin(), and then use the * operator to dereference the iterator and access the value of the current element.

The loop continues until the iterator rit is equal to myvec.rend(), at which point we have reached the position before the first element of the vector.

C++ Iterator Categories

The iterators are classified into categories that describe their capabilities. The order in which they are generally described moves from the categories with the most restricted behavior to those with the most powerful behavior.

In C++, iterators are classified into five categories based on the operations that they support. They are defined as follows:

1. Input iterators: These iterators allow you to read the values of the elements in a container, but not modify them. Input iterators support the ++ operator for advancing to the next element, and the * operator for dereferencing the iterator to obtain the value of the current element.
2. Output iterators: These iterators allow you to write values to the elements in a container, but not read them. Output iterators support the ++ operator for advancing to the next element, and the * operator for assigning a value to the current element.
3. Forward iterators: These iterators allow you to read and write values to the elements in a container in a forward direction. Forward iterators support the same operations as input and output iterators, as well as the == and != operators for comparing two iterators for equality.
4. Bidirectional iterators: These iterators allow you to read and write values to the elements in a container in both forward and backward directions. In addition to the operations supported by forward iterators, bidirectional iterators also support the -- operator for moving to the previous element.
5. Random access iterators: These iterators allow you to read and write values to the elements in a container in any order, and support random access to elements based on their position. Random access iterators support all of the operations supported by bidirectional iterators, as well as the +, -, +=, and -= operators for advancing or retreating the iterator by a specified number of positions, and the [] operator for accessing elements by index.

The iterator categories become important in some cases:

For example, if you are implementing an algorithm that only needs to read values from a container, you can use an input iterator. If you need to write values to a container, you can use an output iterator. If you need to read and write values to a container in a forward direction, you can use a forward iterator. If you need to read and write values in both forward and backward directions, you can use a bidirectional iterator. And if you need random access to elements in a container, you can use a random access iterator.

By choosing the appropriate iterator category, you can ensure that your code is efficient and correct. For example, if you use a random access iterator when you only need to read values in a forward direction, your code may run slower than necessary because random access iterators can be slower than forward iterators. Similarly, if you use a forward iterator when you need to write values to a container, your code may not work correctly because forward iterators do not support writing values to a container.

Iterator Invalidation

In C++, an iterator is considered invalidated when its underlying container is modified in a way that changes the iterator’s position or makes it point to an element that no longer exists in the container. When an iterator is invalidated, dereferencing or incrementing/decrementing it leads to undefined behavior.

Iterator invalidation can occur in various ways, depending on the container and the operation performed on it. For example, inserting or erasing elements in a vector or deque can invalidate all iterators that point to elements after the insertion/deletion point. Similarly, inserting elements in a list invalidates only the iterators that point to the inserted elements, but not the ones that point to other elements in the list.

To avoid iterator invalidation, it’s important to carefully read the documentation for the container and the operations performed on it, and to update the iterators accordingly after each modification of the container. Alternatively, using container member functions that return new iterators, such as begin() and end(), can help avoid iterator invalidation in many cases.

The Basic Sequences

Sequences keep objects in whatever order you store them. They differ in the efficiency of their operations, however, so if you are going to manipulate a sequence in a particular fashion, choose the appropriate container for those types of manipulations.

1. Vectors: Vectors are dynamic arrays that can grow or shrink in size at runtime. Vectors are implemented as templates in C++, which means that you can create vectors of any data type. Vectors have a size() method that returns the number of elements in the vector, and an operator[] that allows you to access individual elements.
2. Deques: Deques (short for double-ended queues) are similar to vectors, but they allow efficient insertion and removal of elements at both ends of the sequence. Deques are implemented as a vector of pointers to blocks of memory, which allows them to be more efficient than lists for certain operations.
3. Lists: Lists are a sequence of elements that are linked together using pointers. Each element in a list contains a value and a pointer to the next element. Lists are efficient for inserting and removing elements, but accessing individual elements can be slower than with arrays or vectors.

Basic Sequence Operations

The following C++ program shows the operations that all the basic sequences, vector, deque, and list, support.

This C++ program demonstrates the basic operations that can be performed on three different types of sequence containers: vector, deque, and list.

The program defines a templated function called print() which takes a reference to a container and a character array as arguments. It then prints out the name of the container, followed by its elements, size, max size, front element, and back element.

The program also defines a templated function called basicOps() which takes a character array as its argument. It then initializes several containers of the specified type (vector, deque, or list) using various constructors and iterators, and performs a variety of operations on them, including assignment, resizing, pushing and popping elements, and inserting and erasing elements.

In the main() function, the basicOps() function is called with each of the three container types as its template parameter, printing out the results for each container type.

The std:vector Class

In C++, a vector is a sequence container that represents a dynamic array. It is a part of the Standard Template Library (STL) and provides fast and efficient access to elements using an index-based interface.

Unlike built-in arrays in C++, vectors can grow dynamically. The size of a vector is not fixed, and it can change dynamically during runtime as elements are added or removed from the vector.

Here’s an example of creating a vector of integers and inserting elements into it:

Inserting elements in Vectors

You can insert an element into a vector by using the insert() method. The insert() method takes an iterator position and the value to insert as arguments. Here’s an example:

In this example, we have created a vector vec with four integer values. We have initialized an iterator it to point to the position at index 2 (value 4) in the vector. We have then used the insert() method to insert the value 3 at this position, shifting all the elements after it to the right. The output shows the updated vector with the value 3 inserted at position 2.

Removing elements from Vectors

To remove an element from a vector in C++, you can use the erase() function provided by the standard library.

The erase() function removes an element or a range of elements from the vector. It takes an iterator as input, which specifies the element or range of elements to remove. After erasing an element, the iterator to that element and all iterators to the right of that element become invalid, which is called iterator invalidation.

Here’s an example of how to use erase() to remove an element from a vector:

This code removes the element with value 3 (at index 2) from the vector v using the erase() function. The v.begin() + 2 iterator points to the element to be erased, and erasing it invalidates the iterator. Finally, the code prints the updated vector {1, 2, 4, 5} to the console.

The std:deque Class

The std::deque class is a standard template library (STL) container in C++ that stands for “double-ended queue”. It provides a dynamic array-like container with efficient insertion and deletion of elements at both the beginning and the end of the sequence.

The main difference between std::deque and std::vector is in how they allocate and store memory. While std::vector allocates a contiguous block of memory, std::deque divides the storage into chunks, usually called “blocks” or “pages”. This allows for efficient insertions and deletions at both ends of the deque, but it also means that accessing elements in the middle of the sequence is slower than with a std::vector.

Here’s an example of creating a deque of integers and insert and remove elements from it:

The std:list Class

The std::list is a class template in C++ standard library that implements a doubly-linked list. It provides constant time insert and erase operations anywhere in the list, as well as iteration in both directions. It is defined in the <list> header file.

A list is slow when randomly accessing elements that it does not have an operator[ ]. Its best used when you’re traversing a sequence, in order, from beginning to end (or vice-versa), rather than choosing elements randomly from the middle.

The list is implemented as a series of nodes, where each node contains a value and two pointers that point to the previous and next nodes in the list. The list is organized in such a way that each node is connected to its previous and next nodes, forming a linked list.

Here is an example C++ code that demonstrates the usage of std::list:

In this example, a std::list of integers is created, elements are added to the list using the push_back() function, and an element is removed from the list using the remove() function. The elements of the list are then printed using an iterator.

If you have large, complex objects, you might want to choose a list first, especially if construction, destruction, copy-construction, and assignment are expensive and if you are doing things like sorting the objects or otherwise reordering them a lot.

Special list operations

The list has some special built-in operations to make the best use of the structure of the list. You’ve already seen reverse() and sort(), and here are some of the others in use:

If you merge() one list with another, the merge only works sensibly if the lists have been sorted. What you end up with in that case is a sorted list containing all the elements from both lists (the source list is erased that is, the elements are moved to the destination list).

A unique() member function removes all duplicates, but only if the list has been sorted first:

Creating your own Containers

With the STL as a foundation, you can create your own containers. In C++, you can create your own containers by defining a class that encapsulates the data structure you want to use. This class should provide all the necessary functions for manipulating the data, such as adding or removing elements, and iterating over the container.

To create a container, you need to define the following:

1. The container class: This is the class that will represent your container. It should contain the necessary data members to store the elements and any other metadata required by the container.
2. Constructors and destructors: You need to define at least one constructor for your container that initializes its data members, and a destructor to clean up any resources when the container is destroyed.
3. Element access functions: These functions allow you to access the elements stored in the container. They may include functions to add or remove elements, or to access individual elements by their index or key.
4. Iterators: Iterators are used to traverse the elements in the container. You need to define at least two iterator types: one for iterating over the elements in the forward direction, and another for iterating in the reverse direction.
5. Other functions: You may also need to define other functions to manipulate the container, such as sorting, searching, or filtering elements.

Here’s an example of the ring data structure, which is a circular sequence container. If you reach the end, it just wraps around to the beginning. This can be implemented on top of a list as follows:

You can see that most of the coding is in the iterator. The Ring iterator must know how to loop back to the beginning, so it must keep a reference to the list of its parent Ring object in order to know if its at the end and how to get back to the beginning.

STL extensions

The STL extensions refer to additional libraries that provide extra functionality beyond the standard C++ STL. These libraries are not part of the standard C++ library, but they are widely used and supported by many compilers and libraries. Some examples of STL extensions are:

1. Boost: a set of libraries that provide advanced functionality in many areas such as smart pointers, regular expressions, numerical algorithms, and more.
2. Qt: a cross-platform application framework that includes a large set of libraries for GUI development, networking, XML parsing, and more.
3. Adobe Source Libraries: a collection of libraries that provide advanced functionality for multimedia and graphic applications, such as image processing, color management, and font rendering.
4. ACE: a set of libraries that provide advanced network programming functionality, such as concurrency, threading, and interprocess communication.
5. GSL: a library that provides mathematical algorithms and functions for scientific computing, such as linear algebra, numerical integration, and optimization.

STL extensions are often used in complex applications that require advanced functionality beyond the basic STL. They can be downloaded and installed separately, and they usually come with their own documentation and support community.

Non-STL containers

Non-STL containers are data structures that are not provided by the Standard Template Library (STL) in C++. These containers are typically not included in the C++ Standard Library, but may be implemented by third-party libraries or created by the programmer.

Examples of non-STL containers include:

• Hash tables: A hash table is a data structure that maps keys to values for efficient retrieval. Popular hash table implementations include Google’s SparseHash and dense_hash_map.
• Trie: A trie is a tree-like data structure that stores keys in a way that allows for fast lookup, insertion, and deletion of entries. Tries are used in many applications including text processing and network routing. An example implementation of a trie is the libTrie library.
• Bloom filter: A bloom filter is a probabilistic data structure that tests for set membership. It can quickly tell you whether an element is definitely not in the set or may be in the set. The Boost library provides a bloom filter implementation.

While non-STL containers may not be as widely used or standardized as STL containers, they can offer unique features and benefits for specific use cases.