container adapters in c++

Container classes, or containers for short, manage a collection of elements. To meet different needs, the STL provides different kinds of containers, as shown in figure below

Figure: STL Container Types

There are two general kinds of containers:

1. Sequence containers are ordered collections in which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element. For example, if you put six elements into a collection by appending each element at the end of the actual collection, these elements are in the exact order in which you put them. The STL contains three predefined sequence container classes: vector, deque, and list.
2. Associative containers are sorted collections in which the actual position of an element depends on its value due to a certain sorting criterion. If you put six elements into a collection, their order depends only on their value. The order of insertion doesn't matter. The STL contains four predefined associative container classes: set, multiset, map, and multimap.

An associative container can be considered a special kind of sequence container because sorted collections are ordered according to a sorting criterion. You might expect this especially if you have used other libraries of collection classes like those in Smalltalk or the NIHCL, in which sorted collections are derived from ordered collections. However, note that the STL collection types are completely distinct from each other. They have different implementations that are not derived from each other.

The automatic sorting of elements in associative containers does not mean that those containers are especially designed for sorting elements. You can also sort the elements of a sequence container. The key advantage of automatic sorting is better performance when you search elements. In particular, you can always use a binary search, which results in logarithmic complexity rather than linear complexity. For example, this means that for a search in a collection of 1,000 elements you need, on average, only 10 instead of 500 comparisons. Thus, automatic sorting is only a (useful) "side effect" of the implementation of an associative container, designed to enable better performance.

The following subsections discuss the different container classes in detail. Among other aspects, they describe how containers are typically implemented. Strictly speaking, the particular implementation of any container is not defined inside the C++ standard library. However, the behavior and complexity specified by the standard do not leave much room for variation. So, in practice, the implementations differ only in minor details. Coming post with covers the exact behavior of the container classes. It describes their common and individual abilities, and member functions in detail.

Sequence Containers

The following sequence containers are predefined in the STL:

• Vectors
  
• Deques
  
• Lists

In addition you can use strings and ordinary arrays as a (kind of) sequence container.

Vectors

A vector manages its elements in a dynamic array. It enables random access, which means you can access each element directly with the corresponding index. Appending and removing elements at the end of the array is very fast. However, inserting an element in the middle or at the beginning of the array takes time because all the following elements have to be moved to make room for it while maintaining the order. Strictly speaking, appending elements is amortized very fast. An individual append may be slow, when a vector has to reallocate new memory and to copy existing elements into the new memory. However, because such reallocations are rather rare, the operation is very fast in the long term. 

The following example defines a vector for integer values, inserts six elements, and prints the elements of the vector:

// stl/vector1.cpp #include <iostream> #include <vector> using namespace std; int main() { vector<int> coll; //vector container for integer elements // append elements with values 1 to 6 for (int i=1; i<=6; ++i) { coll.push_back(i); } //print all elements followed by a space for (int i=0; i<coll.size( ); ++i) { cout << coll[i] << ' '; } cout << endl; }
With

#include <vector>
the header file for vectors is included.
The declaration

vector<int> coll;
creates a vector for elements of type int. The vector is not initialized by any value, so the default constructor creates it as an empty collection.

The push_back() function appends an element to the container:

coll.push_back(i);

This member function is provided for all sequence containers. The size() member function returns the number of elements of a container:

for (int i=0; i<coll.size(); ++i) { ... }
This function is provided for any container class.
By using the subscript operator [], you can access a single element of a vector:

cout << coll[i] << ' ';
Here the elements are written to the standard output, so the output of the whole program is as follows:

1 2 3 4 5 6

Deques

The term deque (it rhymes with "check" ( It is only a mere accident that "deque" also sounds like "hack" :-)) ) is an abbreviation for "double-ended queue." It is a dynamic array that is implemented so that it can grow in both directions. Thus, inserting elements at the end and at the beginning is fast. However, inserting elements in the middle takes time because elements must be moved.

The following example declares a deque for floating-point values, inserts elements from 1.1 to 6.6 at the front of the container, and prints all elements of the deque:

// stl/deque1.cpp #include <iostream> #include <deque> using namespace std; int main() { deque<float> coll; //deque container for floating-point elements //insert elements from 1.1 to 6.6 each at the front for (int i=1; i<=6; ++i) { coll.push_front(i*1. 1); //insert at the front } //print all elements followed by a space for (int i=0; i<coll.size(); ++i) { cout << coll[i] << ' '; } cout << endl; }
In this example, with

#include <deque>
the header file for deques is included.
The declaration

deque<float> coll;
creates an empty collection of floating-point values.
The push_front() function is used to insert elements:

coll.push_front(i*1.1);
push_front() inserts an element at the front of the collection. Note that this kind of insertion results in a reverse order of the elements because each element gets inserted in front of the previous inserted elements. Thus, the output of the program is as follows:

6.6 5.5 4.4 3.3 2.2 1.1
You could also insert elements in a deque by using the push_back() member function. The push_front() function, however, is not provided for vectors because it would have a bad runtime for vectors (if you insert an element at the front of a vector, all elements have to be moved). Usually, the STL containers provide only those special member functions that in general have "good" timing ("good" timing normally means constant or logarithmic complexity). This prevents a programmer from calling a function that might cause bad performance.

Lists

A list is implemented as a doubly linked list of elements. This means each element in a list has its own segment of memory and refers to its predecessor and its successor. Lists do not provide random access. For example, to access the tenth element, you must navigate the first nine elements by following the chain of their links. However, a step to the next or previous element is possible in constant time. Thus, the general access to an arbitrary element takes linear time (the average distance is proportional to the number of elements). This is a lot worse than the amortized constant time provided by vectors and deques.

The advantage of a list is that the insertion or removal of an element is fast at any position. Only the links must be changed. This implies that moving an element in the middle of a list is very fast compared with moving an element in a vector or a deque.

The following example creates an empty list of characters, inserts all characters from 'a' to 'z', and prints all elements by using a loop that actually prints and removes the first element of the collection:

// stl/list1.cpp #include <iostream> #include <list> using namespace std; int main() { list<char> coll; //list container for character elements // append elements from 'a' to 'z' for (char c='a'; c<= ' z '; ++c) { coll.push_back(c); } /* print all elements * - while there are elements * - print and remove the first element */ while (! coll.empty()) { cout << coll.front() << ' '; coll.pop_front(); } cout << endl; }
As usual, the header file for lists, <list>, is used to define a collection of type list for character values:

list<char> coll;
The empty() member function returns whether the container has no elements. The loop continues as long as it returns true (that is, the container contains elements):

while (! coll.empty()) { ... }
Inside the loop, the front() member function returns the actual first element:

cout << coll.front() << ' ';
The pop_front() function removes the first element:

coll.pop_front();

Note that pop_front() does not return the element it removed. Thus, you can't combine the previous two statements into one.

The output of the program depends on the actual character set. For the ASCII character set, it is as follows:

a b c d e f g h i j k l m n o p q r s t u v w x y z

Of course it is very strange to "print" the elements of a list by a loop that outputs and removes the actual first element. Usually, you would iterate over all elements. However, direct element access by using operator [] is not provided for lists. This is because lists don't provide random access, and thus using operator [] would cause bad performance. There is another way to loop over the elements and print them by using iterators. After their introduction I will give an example.

Strings

You can also use strings as STL containers. By strings I mean objects of the C++ string classes (basic_string<>, string, and wstring). Strings are similar to vectors except that their elements are characters.

Ordinary Arrays

Another kind of container is a type of the core C and C++ language rather than a class: an ordinary array that has static or dynamic size. However, ordinary arrays are not STL containers because they don't provide member functions such as size() and empty(). Nevertheless, the STL's design allows you to call algorithms for these ordinary arrays. This is especially useful when you process static arrays of values as an initializer list.

The usage of ordinary arrays is nothing new. What is new is using algorithms for them.

Note that in C++ it is no longer necessary to program dynamic arrays directly. Vectors provide all properties of dynamic arrays with a safer and more convenient interface.

Associative Containers

Associative containers sort their elements automatically according to a certain ordering criterion. This criterion takes the form of a function that compares either the value or a special key that is defined for the value. By default, the containers compare the elements or the keys with operator <. However, you can supply your own comparison function to define another ordering criterion.

Associative containers are typically implemented as binary trees. Thus, every element (every node) has one parent and two children. All ancestors to the left have lesser values; all ancestors to the right have greater values. The associative containers differ in the kind of elements they support and how they handle duplicates.

The following associative containers are predefined in the STL. Because you need iterators to access their elements.

• Sets
  A set is a collection in which elements are sorted according to their own values. Each element may occur only once, thus duplicates are not allowed.
• Multisets
  A multiset is the same as a set except that duplicates are allowed. Thus, a multiset may contain multiple elements that have the same value.
• Maps
  A map contains elements that are key/value pairs. Each element has a key that is the basis for the sorting criterion and a value. Each key may occur only once, thus duplicate keys are not allowed. A map can also be used as an associative array, which is an array that has an arbitrary index type (see page 91 for details).
• Multimaps
  A multimap is the same as a map except that duplicates are allowed. Thus, a multimap may contain multiple elements that have the same key. A multimap can also be used as dictionary. See page 209 for an example.

All of these associative container classes have an optional template argument for the sorting criterion. The default sorting criterion is the operator <. The sorting criterion is also used as the test for equality; that is, two elements are equal if neither is less than the other.

You can consider a set as a special kind of map, in which the value is identical to the key. In fact, all of these associative container types are usually implemented by using the same basic implementation of a binary tree.

Container Adapters

In addition to the fundamental container classes, the C++ standard library provides special predefined container adapters that meet special needs. These are implemented by using the fundamental containers classes. The predefined container adapters are as follows:

• Stacks
  The name says it all. A stack is a container that manages its elements by the LIFO (last-in-first-out) policy.
• Queues
  A queue is a container that manages its elements by the FIFO (first-in-first-out) policy. That is, it is an ordinary buffer.
• Priority Queues
  A priority queue is a container in which the elements may have different priorities. The priority is based on a sorting criterion that the programmer may provide (by default, operator < is used). A priority queue is, in effect, a buffer in which the next element is always the element that has the highest priority inside the queue. If more than one element has the highest priority, the order of these elements is undefined.

Container adapters are historically part of the STL. However, from a programmer's view point, they are just special containers that use the general framework of the containers, iterators, and algorithms provided by the STL.

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

• Complete Tutorial of C++ Template's
• Standard Template Library Tutorial
• Inter Process Communication Tutorial
• Advance Programming in C & C++

-----------------------------------------------------------------

The Art of Learning with Innovation,
eLearning Courses for C and C++ Programming Language - The Most appreciated course !!!

Copyright © ccplusplus.com