Sequence And Associative Containers In C++

A Container in C++ serves as a mechanism for storing various sets of data. These containers have the flexibility to store a wide range of data types, including custom-defined types, as they are designed using class templates. Within the realm of C++, there exist three main categories of containers: sequential containers, associative containers, and unordered (associative) containers.

Sequential Containers

An arranged collection of similar data in C++, where each item is stored at a specific position, is known as a sequential container. The element's placement is influenced by when and where it was added. Sequential containers are also known as sequence containers. There exist three categories of sequential containers:

1. Arrays:

Arrays are structured collections with a fixed size, containing a finite number of elements arranged in a sequential manner. This linear arrangement allows for direct access to specific array elements through their respective indices, eliminating the need to iterate through the entire array.

Example:

Let's consider a C++ illustration to demonstrate the utilization of arrays in sequence containers:

#include <iostream>
 #include <array>
 using namespace std;
 int main()
 {
 // array creation
 array<int, 5> a = {11, 16, 19, 10, 14};
 // creation of the iterator
 array<int, 5>::iterator ite;
 // The values of the array is iterated
 cout << "The array is: ";
 for(ite = a.begin(); ite < a.end(); ite++)
 {
 cout << *ite << " ";
 }
 cout << endl;
 cout << "The Size of the array given array is: " << a.size() << endl;
 return 0;
 }

Output:

The array is: 11 16 19 10 14 
The Size of the array given array is: 5

Explanation:

In this code, we utilized the array standard library to construct an array named a. Subsequently, we employed various functions specified in the array library. The functions begin and end provide pointers to the array's initial and final elements. The function size gives the array's size.

2. Vectors

Array containers, such as vectors, have the ability to dynamically adjust their size. Vectors, similar to arrays, utilize consecutive memory blocks to store their elements. Nevertheless, in contrast to arrays, vectors have the flexibility to modify their data size continuously, with efficient storage management by the container.

Example:

Let's consider a C++ illustration to demonstrate the utilization of Vectors in sequence containers:

#include <iostream>
 #include <vector>

 using namespace std;

 int main()
 {
 vector<int> vect;

 for (int i = 1; i <= 40; i = i * 2)
 vect.push_back(i);

 cout << "The output with vect.begin() and vect.end(): ";
 for (auto i = vect.begin(); i != vect.end(); i++)
 cout << *i << " ";

 cout << "\nThe output with vect.rbegin() and vect.rend(): ";
 for (auto ite = vect.rbegin(); ite != vect.rend(); ite++)
 cout << *ite << " ";

 return 0;
 }

Output:

The output with vect.begin() and vect.end(): 1 2 4 8 16 32 
The output with vect.rbegin() and vect.rend(): 32 16 8 4 2 1

Explanation:

In this instance, a vector named vect was created. Elements were appended to this vector using the push_back function. Subsequently, the begin and end methods were employed, along with the rbegin and rend functions, to display the vector in both forward and reverse order.

3. Deque:

A deque is short for a double-ended queue. It is a data structure that allows for dynamic resizing on both ends. Random access iterators can be used to access specific elements within a deque, which are pointers that enable reading, writing, and random access to containers.

Example:

Let's consider a C++ instance to demonstrate the utilization of Deque in sequential containers:

#include <iostream>
 #include <deque>

 using namespace std;

 int main()
 {
 deque<int> deq;

 deq.push_back(10); // adding element to the back of the queue
 deq.push_front(20); // element was added to front
 deq.push_back(30); 
 deq.push_front(40); 

 deque<int>::iterator ite;

 cout << "The dequeue is: ";
 for (ite = deq.begin(); ite != deq.end(); ite++)
 {	
 cout << *ite << " ";
 }

 cout << "\nThe size deq.size(): " << deq.size();

 //The first element of the array is
 deq.pop_front();

 cout << "\nThe Deque after using pop_front() is: ";
 for (ite = deq.begin(); ite != deq.end(); ite++)
 {	
 cout << *ite << " ";
 }

 return 0;
 }

Output:

The dequeue is: 40 20 10 30 
The size deq.size(): 4
The Deque after using pop_front() is: 20 10 30

Associative containers

Associative structures are those where an element's position is defined by its value rather than the order of insertion. The arrangement of items does not affect where the element is located within the structure. The keys, also referred to as search keys, are employed to retrieve the elements stored in an associative container.

There are four distinct types of associative containers:

1. Set

A set functions as a collection that mandates each element or key to be distinct. Once an element is included in a set, it remains unalterable but can be removed. The elements within a set are organized in a sorted order to facilitate straightforward storage and access.

Example:

Let's consider a C++ instance to demonstrate the utilization of Set in Associative containers:

#include <iostream>
 // #include <iterator>
 #include <set>
 using namespace std;
 int main()
 {
 // declaring the empty set
 set<int> ss1;

 // a set ierator is declared
 set<int>::iterator ite;

 //The elements of the array are randomly arranged
 ss1.insert(50);
 ss1.insert(70);
 ss1.insert(80);
 ss1.insert(90);

 // adding 50 to the set again
 ss1.insert(50);

 // display of set 1
 cout << "The set ss1 is -> ";
 for (ite = ss1.begin(); ite != ss1.end(); ite++) 
 {
 cout << *ite << " ";
 }
 cout << endl << endl;

 // removal of element
 ss1.erase(50);

 cout << "Set ss1 after the using of s1.erase(50) method-> ";
 for (ite = ss1.begin(); ite != ss1.end(); ite++) 
 {
 cout << *ite << " ";
 }

 return 0;
 }

Output:

The set ss1 is -> 50 70 80 90 
Set ss1 after the using of s1.erase(50) method-> 70 80 90

Explanation:

In this instance, we attempted to insert the number 50 twice into the set. Nonetheless, only one instance of 50 was added to the set as each element in a set must be distinct. Subsequently, the set element was deleted using the erase function.

2. Multiset

Multisets are collection structures that share similarities with sets but allow for the inclusion of duplicate elements (keys). The individual value assigned to an element within a multiset remains immutable once stored, although the element itself can be deleted from the container of the multiset.

Example:

Let's consider a C++ instance to demonstrate the utilization of Multiset within Associative containers:

#include <iostream>
 #include <set>

 using namespace std;

 int main()
 {
 // declaring an empty multiset
 multiset<int> mset1;

 //The elements are inserted in random order
 mset1.insert(60);
 mset1.insert(80);
 mset1.insert(40);
 mset1.insert(30);

 // 30 is added to the set twice
 mset1.insert(30);

 // the display of multi set
 multiset<int>::iterator ite;
 cout << "The multiset ms1 is: " << endl;
 for (ite = mset1.begin(); ite != mset1.end(); ite++) 
 {
 cout << *ite << " ";
 }

 cout << endl << endl;

 // Remove all items in ms1 up to the one with value 40.
 cout << "The multiset after the removal of values< 40: " << endl;
 mset1.erase(mset1.begin(), mset1.find(40));

 for (ite = mset1.begin(); ite != mset1.end(); ite++) 
 {
 cout << *ite << " ";
 }

 return 0;
 }

Output:

The multiset ms1 is: 
30 30 40 60 80 

The multiset after the removal of values< 40: 
40 60 80

Explanation:

In this instance, we successfully inserted element 30 twice within the specified application due to the capability of multisets to allow for element repetition. Furthermore, we made use of the erase function to eliminate all elements in the multiset that were below 40. The clear function might have wiped out the entire multiset if 40 had not been part of the set.

3. Map

A Map is a data structure that stores information in key-value pairs. Each key in a map must be unique and can only have one corresponding value. The key and value can be of different data types. The elements in a map are organized based on their keys, allowing for easy retrieval and manipulation of data. Users can add or remove elements from a map as needed.

Example:

Let's consider a C++ instance to demonstrate the utilization of Map in Associative containers:

#include <iostream>
 #include <map>

 using namespace std;

 int main()
 {
 //An empty map container is declared
 map<int, char> map1;

 map<int, char>::iterator ite;

 // elements are inserting
 map1.insert(pair<int, char>(1, 'c'));
 map1.insert(pair<int, char>(3, 'h'));
 map1.insert(pair<int, char>(4, 'i'));
 map1.insert(pair<int, char>(5, 'c'));
 map1.insert(pair<int, char>(2, 'k'));

 //display of the mapped values

 cout << "The map map1 contains: " << endl;

 cout << "KEY -> VALUE" << endl;
 for (ite = map1.begin(); ite != map1.end(); ++ite)
 {
 cout << " " << ite->first << " -> " 
 << ite->second << endl;
 }

 cout << endl;

 //The element with key 4 is removed
 map1.erase(4);
 cout << "After running m1.erase(4), the map is: " << endl;

 cout << "KEY -> VALUE" << endl;
 for (ite = map1.begin(); ite != map1.end(); ++ite)
 {
 cout << " " << ite->first << " -> " 
 << ite->second << endl;
 }

 return 0;
 }

Output:

The map map1 contains: 
KEY -> VALUE
 1 -> c
 2 -> k
 3 -> h
 4 -> i
 5 -> c

After running m1.erase(4), the map is: 
KEY -> VALUE
 1 -> c
 2 -> k
 3 -> h
 5 -> c

Explanation:

In this instance, a map was initialized and the insert function was employed to append entries to it. Subsequently, a component with a key value of 4 was deleted utilizing the erase method.

4. Multimap

Multimap data structures share commonalities with map containers, with the key distinction being their ability to accommodate multiple keys within a single container. This leads to a one-to-many relationship between key-value pairs. Unlike maps, multimaps allow for keys and their corresponding values to have different data types.

Example:

Let's consider a C++ instance to demonstrate the application of Multimap in Associative data structures:

#include <iostream>
 #include <map>

 using namespace std;

 int main()
 {
 // An empty multimap is initialized
 multimap<int, int> mmap1; 

 multimap<int, int>::iterator ite;

 // values are inserted into the multimap
 mmap1.insert(pair<int, int>(35, 4));
 mmap1.insert(pair<int, int>(31, 3));
 mmap1.insert(pair<int, int>(61, 6));
 mmap1.insert(pair<int, int>(90, 9));
 mmap1.insert(pair<int, int>(34, 1));

 // Display oof multimap1
 cout << "The multimap m1 ha elements: " << endl;

 cout << "KEY -> VALUE" << endl;
 for (ite = mmap1.begin(); ite != mmap1.end(); ite++) 
 {
 cout << " " << ite->first << " -> " 
 << ite->second << endl;
 }

 cout << endl;

 // removing the elements upto the specific key value
 mmap1.erase(mmap1.begin(), mmap1.find(31));

 cout << "The multimap mmap1 after removing the key values upto (31 " << endl;

 cout << "KEY -> VALUE" << endl;
 for (ite = mmap1.begin(); ite != mmap1.end(); ite++) 
 {
 cout << " " << ite->first << " -> " 
 << ite->second << endl;
 }

 return 0;
 }

Output:

The multimap m1 ha elements: 
KEY -> VALUE
 31 -> 3
 34 -> 1
 35 -> 4
 61 -> 6
 90 -> 9

The multimap mmap1 after removing the key values up to (31 KEY -> VALUE
 31 -> 3
 34 -> 1
 35 -> 4
 61 -> 6
 90 -> 9

Explanation:

In this instance, we built a multimap data structure. Subsequently, we have the ability to employ identical keys multiple times within the multimap due to its support for duplicate key values. The erase function was utilized to remove all records associated with key values below 31.

Main Differences between Sequence and Associative Containers in C++:

Here are the variances between Sequence and Associative data structures in C++: