C++ Container Types and Sequences

C++ Container Types

There are three types of containers in C++. These are:

1. Sequential Containers
2. Associative Containers
3. Unordered (Associative) Containers

Let us take a look at each one of them.

1. Sequential Containers

A Sequential Container in C++ is an ordered collection of the same type of data in which each element is stored in a specific position. The position of an element depends on the place and time of insertion of that element. Sequential containers are also called sequence containers.

There are five types of sequential containers in the Standard Template Library (STL):

1. Arrays: Arrays are containers of fixed size. They hold a specific number of elements. These elements are arranged in a strict linear sequence. We can directly use array elements by specifying their index i.e. we do not need to traverse the complete array. Learn more about Array in C++.

For example:

Output of the program:

We used the array standard library in the above program to create an array arr. Then, we used different predefined functions of the array library. The functions begin() and end() return pointers pointing to the array's first and last elements, respectively. The function size() returns the size of the array.

2. Vectors: Vectors are those array containers that can change their size. Like arrays, vectors use contiguous memory locations to store their elements. However, unlike arrays, the size of a vector can change dynamically, with their storage being handled by the container automatically. To learn more about Vector in C++, click here.

For example:

Output of the program:

In the above program, we created a vector vec. We added elements to this vector using the push_back() function. Then, we used the begin() and end() , and the rbegin() and rend() functions to print the vector in left-to-right and right-to-left direction respectively.

3. Deque: Deque stands for double ended queue. A deque is a container whose size can increase or decrease dynamically on both ends. Deque allows us to access its individual elements through random access iterators (generalized pointers that can read, write, and allow random access to containers).
   For example:

Output of the program:

In the above example, we created a deque dq. We added elements to the back and front of the deque using the push_back() and push_front() functions, respectively. Then, we used the size() function to get the size of the deque. Finally, we used the pop_front() function to remove the first element of the deque.

4. Forward_list: Forward lists are sequence containers that allow insert and erase operations in constant time, anywhere in the sequence. Forward lists are implemented as singly-linked lists. Hence, each element in a forward list can be stored in unrelated memory locations.

For example:

Output of the program:

In this example, we created a forward list fr_lst and added five elements to it. Then, we used the push_front() function to add two more elements to the list. Finally, we removed the first element from the list using the pop_front() function.

5. Lists: Like forward lists, lists are sequence containers that allow insert and erase operations in constant time, anywhere in a sequence. Lists are implemented as doubly-linked lists. Hence, iteration is possible in both directions (front and back).

For example:

Output of the program:

In the above example, we created a list lst and added elements using the push_back() function. Then, we printed the first and the last elements of the list using the front() and back() functions. Finally, we used the reverse() function to reverse the list.

2. Associative Containers

Associative containers are those containers in which the location of an element depends on the element's value. The order of insertion of elements is not considered in determining the position of the element. The elements of an associative container are accessed via keys, also called search keys.

There are four types of associative containers in the STL:

1. Set: A set is a container in which each element (or key) must be unique. Once an element is inserted into a set, it can't be modified. However, the element can be removed from the set. The elements in a set are stored in a sorted way so that the storage and retrieval of the elements are quick.

For example:

Output of the program:

In this example, we tried to insert the number 50 two times in the set. However, since each element in a set must be unique, 50 was added only once to the set. The erase() function was then used to remove an element from the set.

2. Multiset: Multisets are containers similar to sets but they allow duplicate elements (keys). Once stored, the value of an element can't be modified in a multiset, but the element can be removed from the container.

Output of the program:

In the above program, we were able to add element 50 twice in the multiset because multisets allow the duplication of elements. We also used the erase() function to remove all the elements in the multiset that was smaller than the number 40. Had 40 not been in the set, the erase function would have deleted the whole multiset.

3. Map: A map is a container that stores data in key-value pairs. The keys in a map container must be unique, and there must be only one value associated with a particular key. The data type of the key and its associated value may be different. The elements in a map are stored with respect to the key. We can add or remove elements from any position in a map container.

For example:

Output of the program:

In the above example, we created a map and added elements to it using the insert() function. Then, we used the erase() function to remove the element with key = 4.

To learn more about Map in C++, Click here.

4. Multimap: Multimap containers are similar to map containers, but multimap containers allow duplicate keys to be stored in a container. Hence, the relationship between the key-value pairs is one to many. In multimaps, the datatype of the key can be different from its associated value as well.

For example:

Output of the program:

In this example, we created a multimap. Because multimap supports duplicate key values, we were able to insert the same key twice in the multimap. We also used the function erase() to remove all the elements with the key values less than 30.

3. Unordered (Associative) Containers

Unordered containers or unordered associative containers are those containers in which the position of elements does not matter. The elements in unordered containers are not stored according to the order of their insertion or their values. If n elements are stored in an unordered container, the order of their positions will be undefined, and it might even change over time. The elements of these containers can be accessed using hash.

There are four types of unordered containers in C++ STL:

1. Unordered_set: Unordered sets are containers used to store unique elements in no particular order. The value of an element in an unordered set is it's key itself. The elements of an unordered set can not be modified, however, they can be inserted and removed.

For example:

Output of the program:

In the above example, we inserted elements to the unordered set using the insert() function. We used the find() function to check whether the elements 's' and 'o' were present in the unordered set or not. From this example, we can observe that the order in which the elements were printed is different from the order of insertion of the elements. It means that the elements in unordered sets are not stored in a particular sequence.

2.Unordered_multiset: Unordered multisets are similar to unordered sets, the only difference being, unordered multisets allow duplicate elements. Like in unordered sets, the elements of an unordered multiset can not be modified. They can only be inserted or removed.

For example:

Output of the program:

In this program, we used the size() function to get the size of the unordered multiset. Then, we used the count() function to find out how many times the element 5 appeared in the multiset. Finally, we used the clear() function to remove all the elements from the multiset.

3. Unordered_map: Unordered maps are those containers that store elements in key-value pairs in no particular order. In unordered maps, the key is used to uniquely identify the element. In unordered maps, each key must be unique. The data type of the key and the mapped value can be different.

For example:

Output of the program:

In this example, we created an unordered map uno_map and added elements to it using square brackets ([ ]). Because unordered maps can only store unique keys, we were able to add the key Mangoes only once in the unordered map. When we try to re-insert the key in the unordered map it updates the new value for the same key.

4. Unordered_multimap: Unordered multimaps are similar to unordered maps, the only difference being, in unordered multimaps, different elements can have the same key. The data type of the key and the mapped value(s) can be different.

For example:

Output of the program:

In the above example, we were able to add the key "Apples" twice in the unordered multimap because multimaps allow duplicate keys. We used the find() function to check whether the key "Oranges" was present in the multimap or not. Finally, we used the clear() function to remove all the elements having the key Apples from the unordered multimap.

Sequence vs Associative (complexity wise)

• In the case of sequence containers:

  1. Simple insertion of elements takes O(1) (constant time).
  2. Insertion of elements in the middle is slower compared to insertion in associative containers.

• In associative containers, most complexities are in logarithmic terms:

  1. Inserting, removing, and searching for an element takes O(log n) time.
  2. Incrementing or decrementing an iterator takes O(1) amortized time.
  3. Insertion of an element in the middle is faster compared to insertion in sequence containers.