dcsimg
 

An Introduction to Sequence Containers in C++

by Manoj Debnath
An Introduction to Sequence Containers in C++

Go hands on in using each of the standard library's five sequence containers.

Overview

In C++, the sequence containers are a group of template classes to store data elements. Because they are template classes, they can be used to store any data elements, including custom classes. The data structure they implement enables a sequential access. There are five sequence containers offered by C++ Standard Template Library. They are: array, vector, deque, forward_list and list. The container classes array, vector, and deque are implemented by using an array data structure. And the container classes, list and forward_list, are implemented using a linked list data structure. The basic difference between these two types of data structures is that arrays are static in nature. This means the size of the container is fixed and set during compilation, although there is a provision to increase the size on requirement. The linked-list implementation is purely dynamic in nature. The container increases it size with each new element stored in it.

Design of the Sequence Container

Each container has a certain unique capability and adds value when culled appropriate to the requirement.

According to Bjarne Stroustrup: "The C++ standard library containers were designed to meet two criteria: to provide the maximum freedom in the design of an individual container, while at the same time allowing containers to present a common interface to users. This allows optimal efficiency in the implementation of containers and enables users to write code that is independent of the particular container used."

The array containers are an indexed-based structure. The size of the structure is clearly mentioned and set during compilation time. This means it is static in nature. It is quick to create but may waste a lot of space if a chunk of space remains unused. They typically are sequential memory locations under a common name. Although the size is fixed initially, the containers modeled with an array are sometime resized to accommodate insertion of elements if the array exceeds its initial size. Because array sizes are set during compilation, a dynamic extension of it is a performance tradeoff. Retrieving elements is easy; we can quickly refer to any elements by the index number. Therefore, fetching the last element does not require traversing of all the intermediate elements.

The linked-list is a reference implementation where a node contains the data element and reference context to point to the next element is implemented as a singly linked-list and both the previous and next elements are implemented as a doubly linked-list. The nodes are dynamically created only when needed. As a result, there is no redundant space to waste. Each node created is linked to the chain or list of nodes. This clearly is an efficient management of space, but note that storing every new element has to create a new node prior to that. This consumes extra time. The retrieval process is also comparatively slow, because unlike an indexed structure-like array, there is no way to jump between elements. The nodes are dynamically created and allocate non-sequential memory locations only linked by the reference element of the node. Therefore, to pick an element, we must traverse through all the nodes prior to it. In the worst case, we may have to traverse through all except the node we want to get the element. Insertion and deletion is also has a time tradeoff.

Now, let us take one container at a time and explicate the idea in a bit more detail.

The array Sequence Container

In essence, the array sequence container is nothing but a class representation of a C-style array data structure. But, there are some improvements made by C++. Because it is a template class representation, it keeps information about its size. This serve two purposes: one, we may not provide a size when creating it because the constructor is always able to create one with the default size provided in the class property or we can provide one explicitly. Secondly, we can always refer to its size property to know the exact size of the array. Another important distinction is that the C-style arrays can be easily be treated as a pointer. This can be confusing at times. But, with the class representation of an array in C++, there is no such confusion. Above all, the array sequence container class leverages reliability and efficiency. Otherwise, it can be treated as a simple and static implementation of C-style contiguous memory location only in more reliable way.

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;
   cout<<"Size : "<<arr.size()<<endl;

   return 0;
}

The vector Sequence Container

The vector implementation is nothing but dynamic arrays. They have the same data structure of contiguous memory location. Although it is implemented with arrays at the core, which is static in nature, the vibe of dynamism is in its ability to resize itself automatically as the number of elements inserted exceeds its initial capacity. The container implements the accommodation logic and allocates another chunk of memory. This means that the container has a built-in capability of storage management. We can use iterators to access and traverse the elements all throughout the store. The elements are inserted at the end of the container; therefore, any lack of space found during insertion leads to the extension of the container from the end. But, note that automatic resizing does not occur during element removal. Although there is a method called shrink_to_fit() to explicitly request for shrinking, the request may not be granted.

A Quick Example

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

int main()
{
   vector<string> planets;
   planets.push_back("Mercury");
   planets.push_back("Venus");
   planets.push_back("Earth");
   planets.push_back("Mars");
   planets.push_back("Jupiter");

   cout<<"Size = "<<planets.size()<<endl;
   cout<<"Capacity = "<<planets.capacity()<<endl;

   for(auto iter = planets.cbegin(); iter != planets.cend();
         iter++)
      cout<<*iter<<endl;

   return 0;
}

Resizing a vector is a time-space tradeoff and is not very clear exactly how C++ does it internally. Also note that different versions of the C++ compiler supply a slightly different version of the container classes. There can be some addition to the functions the sequence container supports. But, the core functionalities are more or less the same. With C++11, it is possible for vector or deque to release unneeded memory back to the system with the help of a function called shrink_to_fit(). Note that this is a request and C++ may ignore it in favor of implementation-specific optimization.

The deque Sequence Container

Understand that the array sequence container cannot expand and has one-way entry; the vector sequence container can expand but cannot contract; it also has one-way entry. But, the deque sequence container although uses vector as its core data structure implementation and can be expanded and contracted with insertion and deletion at both ends. They are more efficient than vectors but, unlike vectors, contiguous memory allocation is not guaranteed. The 'deque' essentially means double-ended-queue and works in a similar fashion as queues; in other words, a FIFO (first-in-first-out) manner. Double ended means that the FIFO can occur at both ends (front and rear).

A Quick Example

#include <iostream>
#include <iomanip>
#include <deque>

using namespace std;

void print(deque<int> dq)
{
   deque <int> :: iterator iter;
   for (iter = dq.begin(); iter != dq.end(); ++iter)
      cout<<*iter<<' ';
   cout<<endl;
}

int main()
{
   deque<int> nums;
   nums.push_back(10);
   nums.push_front(1);
   nums.push_back(9);
   nums.push_front(2);
   nums.push_back(8);
   nums.push_front(3);
   nums.push_back(7);
   nums.push_front(4);
   nums.push_back(6);
   nums.push_front(5);

   cout<<"Size = "<<nums.size()<<endl;
   cout<<"deque contents"<<endl;
   print(nums);
   cout<<"After popping an element from the front"<<endl;
   nums.pop_front();
   print(nums);
   cout<<"After popping an element from the back"<<endl;
   nums.pop_back();
   print(nums);

   return 0;
}

The forward_list Sequence Container

The forward_list is implemented as a singly linked-list where each node contains a data element and a reference pointer to point to the next element in the list. Due to its forward moving structure, each keeps information about its next element and hence traversal can be done in forward direction only. The container is useful for algorithms that require insertion, deletion, and forward iteration of elements. Because it is implemented with linked-list, it is completely dynamic in nature and the size of the list is immaterial.

A Quick Example

#include <iostream>
#include <iomanip>
#include <forward_list>

using namespace std;

void print(forward_list<int> flist)
{
   forward_list <int> :: iterator iter;
   for (iter = flist.begin(); iter != flist.end(); ++iter)
      cout<<*iter<<' ';
   cout<<endl;
}

int main()
{
   forward_list<int> nums;

   nums.assign({1,2,3,4,5,6,7,8,9});

   cout<<"forward_list contents"<<endl;
   print(nums);
   nums.merge({11,22,33,44});
   cout<<"After merging new element in the list"<<endl;
   print(nums);

   return 0;
}

The list Sequence Container

Similar to forward_list, the list is also non-contiguous memory allocation, but is implemented as a doubly linked-list. This means that in the list container both forward and backward traversal is possible. It also has a sort function to arrange elements in ascending order and invokes it after merging new elements into the list. The main operational difference between list and forward_list is that it supports traversal both way, whereas another supports forward traversal only. Compared to static sequence containers, both forward_list and list are slow to find a location in the list but, once found, insertion and deletion is pretty fast.

A Quick Example

#include <iostream>
#include <iomanip>
#include <list>

using namespace std;

void print(list<int> lst)
{
   list <int> :: iterator iter;
   for (iter = lst.begin(); iter != lst.end(); ++iter)
      cout<<*iter<<' ';
   cout<<endl;
}

int main()
{
   list<int> nums;

   nums.assign({1,2,3,4,5,6,7,8,9});

   cout<<"list contents"<<endl;
   print(nums);
   nums.merge({11,22,33,44});
   cout<<"After merging new element in the list"<<endl;
   print(nums);

   return 0;
}

Conclusion

Every container has a type called iterator. The iterator is nothing but a pointer to the elements of the container. It can be incremented or decremented to traverse through all the elements and also can be used to select one element from the container. The primary goal of the two types of sequence container implementation, be it array or linked-list, is to provide the maximum freedom in the design of an individual container, while at the same time allowing containers to present a common interface to users. The sequence containers comply with some common property: they are sequential in nature, which means that the elements can be accessed sequentially. Secondly, they have similar interfaces with many common functions.

References

  • Bjarne Stroustrup. The C++ Programming Language. 3rd ed.
  • Deitel, Paul J, and Harvey M Deitel. C++ How to Program, 9th ed.
This article was originally published on Thursday Dec 26th 2019
Home
Mobile Site | Full Site