36 Other containers and generic algorithms
Bhushan Trivedi
Introduction
In this module, we will look at other types of containers and a few examples of generic algorithms. We will discuss how the list works and how it allows insertions at random places, we will discuss the Deque and four sorted associative containers, viz. set, multiset, map, and multimap. We will look at how the find(), sort() and copy() algorithms can be used with different containers.
List
The list is a type of container which adds an element into a doubly linked list. The list is the most efficient data structure for inserting and deleting from an arbitrary position in the sequence. We have stated in the previous module that once you learn one type of container, it is an easy job to learn another. You can see that defining and using list is quite straight forward once you have learned how to use vector. You can see how the list is defined.
list <Cricketer> ls;
You can also see how an element is inserted at the end of the list
ls.push_back(Mithali);
You can also see how we traverse through the list
for (CricketerIndex = ls.begin(); CricketerIndex != ls.end(); CricketerIndex++)
You can see that we have just replaced Vc with ls. The functions ls.begin() returns the iterator pointing to the first element of the list and ls.end() points immediately after the last element of the list. However, both containers (vector and list) are different and the difference is also important for us to learn.
The first important difference is that the begin() and end() returns bidirectional iterators unlike the random access iterators when we work with vectors. What does that mean? Carefully observe the class Cricketer. It does not have an operator < overloaded now, it has operator == overloaded. This operator == is critical for the bidirectional iterators, in the sense that the find algorithm does not work on the list if the element does not have operator==defined. The vector had the operator < for random access iterator it had to overload for the find algorithm to work there. This is a very clever design. It avoids any inefficient solution that it can. When we cannot access the elements randomly (in the list case for example), there is no point in using operator < to compare elements and move them around. It is only necessary to have operator == which is good enough for sequential movement of the iterator. The list iterators also indicate that they do not work with any algorithm which demands random access iterators, for example, algorithms like sort(). A class designer can specify if he wants the class objects to be manipulated using the list or some other type of container by overloading specific operators for the same.
Program 33.1
#include <list>
#include <iostream>
#include <string>
#include <algorithm> //for find()
using namespace std;
class Cricketer
{ //same as before };
int main()
{
list <Cricketer> ls;
Cricketer Mithali (1, “Mithali Raj”);
..
ls.push_back(Mithali);
ls.push_back(Sushma);
ls.push_back(Harman);
ls.push_back(Dipti);
ls.push_back(Zulan);
ls.push_back(Veda);
list<Cricketer>::iterator CricketerIndex;
// adding an element at any place is most efficient for list
Cricketer Shikha(7, “Shikha Pande”);
CricketerIndex = find(ls.begin(),ls.end(),Dipti);
ls.insert(CricketerIndex, Shikha);
for (CricketerIndex = ls.begin(); CricketerIndex != ls.end(); CricketerIndex++)
cout << *CricketerIndex;
}
Jersey Number: 1 Name: Mithali Raj
Jersey Number: 2 Name: Sushma Verma
Jersey Number: 3 Name: Harmanpreet Kaur
Jersey Number: 7 Name: Shikha Pande
Jersey Number: 4 Name: Dipti Sharma
Jersey Number: 5 Name: Zulan Goswami
Jersey Number: 6 Name: Veda Krishnamurthi
Program ended with exit code: 0
The list container is better than vector in one typical case, inserting or deleting at a random place. Above program 33.1 indicates the case. It, first of all, finds where Dipti is and inserts Shikha just before that.
CricketerIndex = find(ls.begin(),ls.end(),Dipti);
Above statement finds the place where Dipti is, and make the CricketerIndex pointing to it. Next statement inserts Shikha just there.
ls.insert(CricketerIndex, Shikha);
The output shows the result. Now we have Shikha just before Dipti in the container.
Difference between vector and list
Let us try to learn a few important differences between these two containers; i.e. vector and a list. A list is better when random insertion or deletion takes place because it only demands reshuffling the pointers in a doubly linked list. In case of a vector, it requires relocating all the elements below that element one place down. It takes a lot of time depending on the size of the vector. The list is the only container with a constant insertion time. Unlike that, accessing a random element in a list is a very costly operation as it needs to traverse the list sequentially. Vector scores over the list in case of random access as it allows directly jumping to a specific element as all elements are contiguously stored and finding out the address of any element and jumping to that location is quite an easy exercise in that case. Another point is, vectors, when grows, adds an additional overhead and thus may not provide consistent insertion timings. For example, when the 16th element is inserted, it is inserted in the final empty space. The next insertion demands the vector grows to 32 elements and that will take some time which is definitely more than the 16th element. Similarly, the 33rd element will take more time than other elements.The list and vector are not the same, and one must choose the one that suits his operation.
Deque
Deque is the final sequence container that we will see in this module. We will not describe it much as it is quite similar to two earlier containers. It allows insertions at both the ends and also allows deletions from both the ends. We look at the inserting at the beginning using push_front(). Deque allows both push_back() as well as push_front(). Function push_back inserts the element at the end while push_front adds it at the beginning. The program 33.2 indicates using push_front every element and thus acting exactly like a stack. The definition and use of Deque are quite similar to other containers. We have overloaded operator == which is good enough for the bidirectional iterator. However, Deque provides random access iterators and thus it can even work if operator < is overloaded. This is an example of how an algorithm which demands an iterator can also work with an iterator of the higher order type.
class cricketer { }
int main()
{
deque <Cricketer> ds;
Cricketer Mithali (1, “Mithali Raj”);
..
ds.push_front(Veda);
deque<Cricketer>::iterator CricketerIndex;
for (CricketerIndex = ds.begin(); CricketerIndex < ds.end(); CricketerIndex++)
cout << *CricketerIndex;
}
Sorted Associative Containers
The sequential containers are good but then we also need to have containers which keep the data in sorted order. Many systems are such where the data is referred to a large number of times while inserted or deleted once in a while. Another requirement is about accessing elements based on some key item. Unlike arrays, where the key items are always an int, we need to have indices of arbitrary types for some systems, including a case where items indexed by objects. Neither vector nor list can work like this. The sorted associative containers are the answer to this puzzle. Whenever an element is inserted in a sorted associative container, it is inserted in the exact position of the sorted list. The sorting process depends on the key value and the ordering provided in the key value. For built in types, the ordering is simple but for user defined types, the users will have to provide overloaded operator < as const to indicate the order. That user defined type acts as a key and while we use map, one can use it as if an array with that type as an index. The reference will always find the data sorted and thus can deploy algorithms like binary search which is an order of magnitude more efficient than the sequential search. STL provides four containers of sorted associative type, map, set, multimap and multiset. Let us look at each one.
Sorted associative containers are, as the name suggests, sorted. The sorting processhappens as the user indicates in the overloaded operator <() That means, it is compulsory to overload operator < 1 in the key objects while working with sorted associative containers. The incoming element is compared with existing elements using this operator and inserted at its specified place. The sorted associative containers are implemented using height balance tree structures which are the most efficient ways to store and retrieve elements of this nature.
One of the important differences between a sequence container and sorted associative container is that a sequence associative container elements are accessed using their index value, or position in the sequence while sorted associative container elements are accessed based on the key value. Every element of a sorted associative container contains a key and based on the key value in the typical sorted order specified in the overloaded operator <, the insertion, deletion or reference takes place, there is no notion of position in the sorted associative container.
Map
The first sorted associative container that we are going to look at is called map. It has two items, a key, and a value. The map is automatically sorted on the key value at the time of insertion. Any user defined objects used in the map must have overloaded operator < as const.
In the program 33.3, we have a cricketer object and a float number, indicating the number of runs scored by that cricketer. We may order cricketers on a number of wickets taken, or strike rate or an average or number of centuries scored etc. We will have to design our Cricketer class accordingly. Before we look at the program, kindly note that we need to include <map> for both map and multimap (described in next section). Multimap can have multiple records with the same key, unlike map. Defining map is straightforward. Here are two examples. First is a map of string data (key) and float value while secondly is Cricketer data (key) and float value.
map<string, float> sCrickData;
map<Cricketer,float> cCrickData;
Insertion and reference to any element in the map are done using two methods, one is an insert function and another is more conventional and easier method using operator []. Here is an example showing how it is done. The first call adds a pair of data, “Mithali” is a string object and 4000 as a value. Another example uses Mithali as a cricketer object and a float value. In both cases, a string object and a cricketer object are keys. Thus a map can actually provide an array with arbitrary index types!
sCrickData[“Mithali”] = 4000;
cCrickData[Mithali] = 4000;
One can even refer to these items using the array subscript notation after assigning. When one refers to an item, it is done very fast using the binary search over the height balanced tree. Instead of using an array subscript operator, one can use an insert function demonstrated in the next example which discusses multimap. When an insert operation is carried out with multimap where there is already an old key and value pair exists, the old value is retained, unlike map where the old value is overwritten.
Here is a program.
Program 33.3
#include <map>
…
class Cricketer
{
..
};
int main()
{
map<string, float> sCrickData;
sCrickData[“Mithali”] = 4000;
sCrickData[“Zulan”] = 2000;
sCrickData[“Harman”]=3000;
Cricketer Mithali(1,”Mithali Raj”);
Cricketer Zulan(2,”Zulan Goswami”);
Cricketer Harman(3,”Harmanpreet Kaur”);
map<Cricketer,float> cCrickData;
cCrickData[Mithali] = 4000;
cCrickData[Zulan] = 2000;
cCrickData[Harman] = 3000;
}
Multimap
As described earlier, multimap container can have multiple records with the same key. Program 33.4 describes a case which is similar to the earlier program, now with inserting the data twice in the same structure now defined as multimap instead. The shortcut [] approach, unfortunately, does not work here as [] becomes ambiguous when there are multiple elements associated with the key. One will have to use insert function to insert elements. Interestingly map does not insert a single element but a pair of elements, key, and a value. Inserting them requires another container called pair. Following is an example of how pair is possible to be used
pair<Cricketer,float> (Mithali,4000)
In above case, the pair is used to have a pair of a cricketer object and a float value, Mithali and 4000. Now, this pair is inserted in the multimap using insert function as follows.
sCricData.insert(pair<Cricketer,float> (Mithali,4000));
In fact, every element is purposefully inserted twice to showcase the multimap nature of accepting multiple values with same keys. If we have used a map instead, the new value, once inserted, would have overwritten the old value. Reference is done using an iterator and the find() member function. As we cannot use a [] operator we will have to use find function to find a record with a given key.
Position = sCricData.find(Mithali);
{
cout << Position->first;
cout << “Runs scored are: “;
cout << Position->second;
cout << endl;
}
}
Jersey Number: 1 Name: Mithali Raj
Runs scored are: 4000
In above code, you can see that position, the iterator is used to find the place where Mithali’s record is stored. Once we get that record, we need to get both elements of the pair, named as first and second. The output is shown displaying how these values are printed. The iterator position points to multimap elements and each of them is a pair so we need to access them in the manner shown.
Program 33.4
// header files
class Cricketer
{
//data
};
int main()
{
Cricketer Mithali(1,”Mithali Raj”);
Cricketer Zulan(2,”Zulan Goswami”);
Cricketer Harman(3,”Harmanpreet Kaur”);
multimap<Cricketer,float> sCricData;
sCricData.insert(pair<Cricketer,float> (Mithali,4000));
sCricData.insert(pair<Cricketer,float> (Harman,3000));
sCricData.insert(pair<Cricketer,float> (Zulan,2000));
sCricData.insert(pair<Cricketer,float> (Mithali,4000));
sCricData.insert(pair<Cricketer,float> (Harman,3000));
sCricData.insert(pair<Cricketer,float> (Zulan,2000));
multimap <Cricketer,float> :: iterator Position;
Position = sCricData.find(Mithali);
{
cout << Position->first;
cout << “Runs scored are: “;
cout << Position->second;
cout << endl;
}
}
Jersey Number: 1 Name: Mithali Raj
Runs scored are: 4000
Program ended with exit code: 0
We can write something like this and get all elements printed, in both cases, 33.3 and 33.4. We can get all of the elements displayed, twice in case of multimap and once in case of a map, even if inserted twice.
for (Position = sCricData.begin(); Position != sCricData.end(); Position++)
{
cout << Position->first;
cout << “Runs scored are: “;
cout << Position->second;
cout << endl;
}
Set
Set is simpler than the map. It only contains key items. The set is used to access if the key value is really part of the set or not in a quick manner. Following program describes how that is done. The first part of the program is what we have already seen, inserting cricketer data in the vector. Now we will print each element of the vector and at the same point in time inserted in the set using following two statements.
cout << *CricIndex;
SetCric.insert(*CricIndex);
The insertion in the set is done in the order which is described in the overloaded operator < of the class. The output at the end showcases the point.
Program 33.5
#include <set>
// header files
class Cricketer
{
..
};
int main()
{
vector <Cricketer> vc;
Cricketer Mithali (1, “Mithali Raj”);
.. //insertion in different order
vc.push_back(Mithali);
vc.push_back(Veda);
vc.push_back(Dipti);
vc.push_back(Sushma);
vc.push_back(Zulan);
vc.push_back(Harman);
set <Cricketer > SetCric;
vector<Cricketer>::iterator CricIndex;
for (CricIndex = vc.begin(); CricIndex < vc.end(); CricIndex++)
{
cout << *CricIndex;
SetCric.insert(*CricIndex);
}
cout << “Set is sorted on jersey number \n”;
set <Cricketer>::iterator SetCIndex;
for (SetCIndex = SetCric.begin(); SetCIndex != SetCric.end(); SetCIndex++)
{
cout << *SetCIndex ;
}
}
Jersey Number: 1 Name: Mithali Raj
Jersey Number: 6 Name: Veda Krishnamurthi
Jersey Number: 4 Name: Dipti Sharma
Jersey Number: 2 Name: Sushma Verma
Jersey Number: 5 Name: Zulan Goswami
Jersey Number: 3 Name: Harmanpreet Kaur
Set output is sorted on jersey number
Jersey Number: 1 Name: Mithali Raj
Jersey Number: 2 Name: Shushma Verma
Jersey Number: 3 Name: Harmanpreet Kaur
Jersey Number: 4 Name: Dipti Sharma
Jersey Number: 5 Name: Zulan Goswami
Jersey Number: 6 Name: Veda Krishnamurthi
Program ended with exit code: 0
Multiset
Unlike Set, and like multimap, multiset allows multiple keys to be inserted. We have another example in program 33.6 describing the case of the multiset. We insert the same items we did in the earlier case twice and they are inserted twice. The multimap constructor that we have used is available to most of the containers, for copying data from other types of containers at the time of defining a container. multiset <Cricketer > mSetCric (vc.begin(),vc.end()); it constructs the multiset from the vc vector copying from the first element to the last. This is a simpler method than what we have seen in the previous case.
Program 33.6
#include <set>
//header files
class Cricketer
{ .. };
int main()
{
vector <Cricketer> vc;
Cricketer Mithali (1, “Mithali Raj”);
..// inserted twice in other order
vc.push_back(Harman);
multiset <Cricketer > mSetCric(vc.begin(),vc.end());
vector<Cricketer>::iterator CricIndex;
cout << “Set is sorted on jersey number \n”;
multiset <Cricketer>::iterator SetCIndex;
for (SetCIndex = mSetCric.begin(); SetCIndex != mSetCric.end(); SetCIndex++)
cout << *SetCIndex ;
}
} //outputs in sorted order, twice every record!
Algorithms
Now it is time to turn to algorithms. We will start with find(), the algorithm we have any way encountered while discussing vectors. In fact, the find() algorithm can be used with vector list Deque and all other containers as it works with Input iterators which are simplest types of iterators supported by all containers.The algorithm find() takes three arguments. First two arguments are iterators defining the range, the first and the last element, usually being returned by begin() and end() functions. The third argument is the element to be found in the given range. Find returns the same type of iterator it was passed with. Following statements indicate how it can be put to use.
int *pos = find(iArray, iArray+6, 4);
ListIndex = find(ls.begin(),ls.end(),Harman);
DeqIndex = find(ds.begin(),ds.end(),Zulan);
All three of above statement look similar. If you recall, we have used similar statement for the vector container earlier. An interesting case is shown is an integer array, iArray. The statement is used to find where in the array there is an element called 4 exists and return the pointer to it. That indicates that find() can also work with normal arrays. This is the power of algorithm being generic. An important requirement of a program using find() etc algorithms, is to #include <algorithm>.
The next algorithm that we look at is sort(), which is also encountered earlier. The statements in the following demonstrate the sort(), which takes two iterators as arguments. Like find(), the sort() can work with normal arrays. It is important to note that sort() demands random access iterators which are not provided by some containers, for example, list. So deque and vector’s data can be sorted using sort() but not list’s, as list works on bidirectional iterators. Another need for sort is the overloaded < operator as const.
deque<Cricketer> ds (vs.begin(),vs.end());
sort(ds.begin(),ds.end())
sort(IntArray, IntArray+6);
The final algorithm that we will throw some light on, is called copy. It is used to copy the content of one container into another. Following three statements showcases the usage of copy. In the first case, a vector’s data is copied to another vector and second and third case the data is copied to list and deque respectively.
copy(vs.begin(),vs.end(),t_Vect.begin());
copy(vs.begin(),vs.end(),ls.begin());
copy(vs.begin(),vs.end(),ds.begin());
Summary
The module discussed sequence containers like list and deque and sorted associative containers like map and set with their multi- versions. We have also looked at three most used algorithms as well.
- Reference 1:Introduction to ANSI C++, Bhushan Trivedi, Oxford University Press
- Reference2:www.stroustrup.com, homepage of Bjarne Stroustrup, the creator of C++
- Reference 3:The C++ Primer, Stanley Lippmann, Addition Wesle