STL stands for Standard Template Library. It is probably one of the most important contributions to the standard library. It has brought the most crucial improvements to the C++ language and redefined the way we perceive the data structures and the way we are coding right now. If you just know the basics of C++, then this is definitely an article that will help you gather knowledge and progress.
Throughout this article, I will try to present each existing type briefly, starting with their basic usage, how they are represented, and the way you should work with them. I’ll give the pros and cons, when and where to use it, and I’ll add data structures that are either related to it or are the same, but just an individualized version.
Before we begin, please make sure that you’ve read the previous part of this multi-part article series, Introduction to the STL. In it, I covered a few key points that are taken for granted because it’s assumed that you already know them. A quick search for the name of the article should reveal its location.
To start, STL containers can be divided into two parts: associative and sequence type. The sequence is probably familiar because you can use it in C too. An array of char would be a good example (char[100]). This is a succession of elements-one after another. Associative containers, on the other hand, are more elegant. The idea behind them is to provide a data structure from which elements can be accessed in an efficient way.
For example, let’s say we have 10 elements. Now if we put them in an array of size 10, and we want to access the last item, we would have to start from the first item and iterate through the array to the tenth element. This would result in a linear complexity of 10.
However, if the order of elements in the array is negligible, or a sorted array is preferred, we can find any item in it using the binary search algorithm (which is a logarithmic algorithm) in O(logN) time. This is quite an improvement for a structure containing many elements.
We can also add the vector, list, deque, and string (the slist, xstring, queue and stack as individualized types) to the sequence containers. As far as the associative containers, we can add the set and map (the multiset and multimap as individualized types). There are also the hash-related containers for the associative ones, however, I won’t present these because they are more complex and are rarely used.
Before we go any further, I’m going to show you how to make any of these containers available for use. First, you need to include the header for the container type. To make this even simpler for each of the containers this is exactly the same as its own name and because it’s included in the standards you can forget the .h extension.
The .h versions are also present for some backwards compatibility, so if you type them simply out of habit, they will work too. STL is included in the standard namespace, so you may have two ways to use it, such as presenting it on a vector:
#include<vector>
And:
std::vector
//or
using namespace std;
…
Vector
The using namespaces keyword notifies the compiler which namespace to include the vector. Now that we are through with this let’s take a closer look at each item.
1) Vector:
Declaration:
Header: vector<T, Alloc>
In code:
vector<int> aVector;
Representation:
The vector is the most commonly used type. It can be reduced on a theoretical level to an array of continuous elements in the memory. It will stay this way even after you add a new element.
If it is placed in the memory continuously, it will extend the current allocation or else it will reserve space in a new memory segment and copy the entire sequence data plus the new element to it. This way, you will always have a continuous data structure and you can refer to the nth member using the location of the first item + n size of the item.
Cons/Pros:
The memory management is dynamic and automatic. This construction allows random access to elements. It has constant time for insertion and deletion at the end (complexity 1), and linear time for the rest (complexity n). All iterators that point to a member are invalidated if the integrity of the block is changed (removing/inserting elements).
Some usage:
aVector.reserve(10); // Reserve memory for 10 items
aVector.resize(10,1); // Resize the vector with 10 1
aVector.push_back(item); // add another item to the end, note that the vector will be extended and a reserve will be called for it
aVector.insert(aVector.begin() + 3, 5); // Using the random //access iterator
aVector.clear(); // Removes all elements from vector
2) String:
Declaration:
Header: basic_string<charT, traits, Alloc>
typedef basic_string<char, char_traits<char>, allocator<char> > string;
In code:
string aString;
Representation:
Despite its complicated look and the long typedef string, it is nothing more than a vector<char> with a few extended functions that are specific to strings, such as search. So the usage of it is very much like the vector, just as it relates to char member types:
const char* text = “Lavigne”;
aString.assign(“Avril “); // Assign some data
aString += aString; // Double the same content
aString += text; // Add Lavigne
aString.find_last_of(“A”); // Returns 6, the pos of last A
Related types:
wstring -> Same as the string, but this is the Unicode version. However, pay attention because here we have an exception. The corresponding header isn’t wstring, it’s xstring.
rope -> rope has a different design compared to the string and its use is recommended for very long sequences of chars. However, in contrast to the string, which, in matters of complexity, is similar to the vector, a rope has a logarithmic complexity most of the time.
3) Deque:
Declaration:
Header: deque<T, Alloc>
In code:
deque<char> aDeque;
Representation:
This is also a container that is very much like the vector and has most of the same cons and pros. However, we do have a difference. A deque, unlike a vector, also supports constant time of insertion and removal from the beginning of the sequence. Of course, we have to pay a price for this. And the price is that the deque lacks functions like capacity() and reserve() and it can’t guarantee the validity of an iterator associated with those member functions. It’s up to you to decide whether you can pay this price for the extra insertion efficiency.
aDeque.assign(2, ‘A’); // Set two A’s
aDeque.pop_front(); // Remove a A
aDeque.push_front(‘V’);// Add at start a V
aDeque.insert(aDeque.begin(), 1, ‘R’); //Add at start a R all //this done in constant time
4) List:
Declaration:
Header:
In code:
list<int> aVector;
Representation:
Here we have, as the name suggests, a list. A list for which the allocation in a block isn’t a option. Here, each piece of data can be at any memory location. It’s linked together using pointers. The basic list is double linked, so you can iterate through it in both ways/directions.
Cons/Pros:
It has constant time insertion/removal to the end, beginning, and middle. However, the directly affected item’s iterator is deemed invalid whenever you modify the structure of the list. It is highly recommended when you have a long sequence with many elements. This way, memory reallocation can be avoided.
Related types:
slist -> Here we have a list that is only single linked in one direction. This is done in order to gain some efficiency when you are absolutely sure that you don’t need to do any backward traversing through the list.
aList.push_back(“Avril”); // Push at the end
aList.insert( aList.end() -1, “Lavigne”);
// Insert at the last valid position that is end()-1
aList.empty(); // Will return false
aList.erase(aList.begin()); // Delete the Avril
aList.clear();
aList.empty(); // Will return true
5) Stack:
Declaration:
Header: stack<T, Sequence>
In code:
stack<int> aVector;
Representation:
Stack is an adaptor, which is a container that provides a restricted container that behaves just like a stack in real life. This means it follows the LIFO (Last In, First Out) principle. So you can only see the data at the top of a stack and you can only remove the top item from a stack. Whatever you add will be added to the top.
Stack is, by default, constructed on a deque, however, you can specify what restrictions you want to impose so that it behaves as a stack for the second argument in the template (Sequence). You can select whatever you want if the default doesn’t satisfies your needs.
aStack.empty(); // observe if it’s empty
aStack.push(2); // add 2 to the stack
aStack.top(); // returns the item at the top
aStack.pop(); // remove the top/last added element
aStack.size(); // returns the size of the stack
6) Queue:
Declaration:
Header: queue<T, Sequence>
In code:
queue <int> aVector;
Representation:
If you read the information I presented earlier about stacks, then you won’t be surprised at all. Here, we have the same capabilities for a different principle. Namely, it’s about the FIFO (First In, First Out), so what you add first will be, and can only be, removed first. Think of it as though you are in a queue/line waiting to buy a ticket to the cinema. The first people who arrive are the first served, and, hence, the first removed from the line.
std::queue<string,list<string>> aQueue;
string text_1 = “Hilary”;
string text_2 = “Duff”;
aQueue.push(text_1);
aQueue.push(text_2);
aQueue.front(); // retrieve mutable reference to first pushed //item
aQueue.back(); // Mutable reference to the last pushed item
aQueue.pop(); // Eliminate the first element
1) Set:
Declaration:
Header: set<Key, Compare, Alloc>
In Code:
set<int> aSet;
Representation:
A set can be most easily comprehended as a sorted sequence of items. Items added to it are always added so that a sorted property of the set remains intact. The set is sorted in increasing order. The compare is handled by default by the >= operator when defined for the type, or you can pass a function as a second parameter at creation time.
The last parameter in the template declaration is the usual allocation-type chooser. For example, the code below will print 2 into the console for the size and 0 and 1 as members. This is because no multiple existence is allowed in a set. So, only one 1 is added from the vector.
int item = 0;
std::vector<int> aVector;
aVector.reserve(10); // Reserve memory for 10 items
aVector.resize(10,1); // Resize the vector with 10 1
aVector.push_back(item); // add another item / a resize will be called
std::set<int> aSet;
aSet.insert(aVector.begin(), aVector.end());
cout << aSet.size() << endl;
copy(aSet.begin(), aSet.end(), ostream_iterator<int>(cout, ” “));
Cons/Pros:
Inserting an item into a set is a fast operation. Inserting a range is also fast (linear time if the inserted range is already sorted). Iterators aren’t deemed invalid after modifying the structure of the set unless the iterator was pointing to the modified item. Searching for an item is very fast.
Related types:
multiset -> In this version, multiple presence of the same item is allowed. For example, you may have two “2” numbers within a set, despite the fact that this isn’t correct mathematically.
2) Map:
Declaration:
In Header: map<Key, Data, Compare, Alloc>
In Code:
map< string, int> aMap;
Representation:
A map is similar to a set, but, as you can see on the image above, we can also assign data for the key. For the containers above, the [] operator was just returning the nth item when available. However, for the map, this gets a new functionality. Check out the code below:
string text(“Avril”);
aMap[text] = 9;
aMap[text] = 10;
The first call of the operator inserts the text “Avril” into the container and sets the value pointed by it to 9. The second one just resets the value to 10. You see, the [] operator searches for the key and if it manages to find one, it returns a reference to the data member that was pointed to by the key. However, if it fails to find it, it inserts it, and right after the insertion, it returns the reference to the data member.
Just as for the set, here is a sorted container with the corresponding advantages. Also, an iterator that is returned is now a pair, since it holds the key and the data for it. You can refer to the key as first and the data as -> second. Take a look at the example following:
map<string, int>::iterator it = aMap.begin();
it->first; // will return the key, in our case the text //”Avril”
it->second; // return the second item, the 10
string text_2(” Lavigne”);
aMap[text_2] = 11;
it = aMap.find(text_2 + “None”);
if( it == aMap.end())
cout << ” The searched item not found”;
Related types:
multimap -> In this version, multiple presence of the same item is allowed. For example, you may have a “green”,1 pair and a “green”,2 at the same time.
We have just arrived at the end of part two. I sincerely hope that you have learned more about STL. But do I need to say it again? This isn’t a step-by-step introduction covering all kinds of usages, because you can use the SGI official site when you are searching for information about the STL.
SGI is the best place to search for help and information when you are stuck. However, by now you should have a good foundation for data structures/containers and you should be able to handle them easily with perhaps a little extra clarification from the SGI site. With some practice and much determination, you will get really good at this.
In the next part we’ll take look at a more complex example of STL usage; we shall implement an arithmetic expression calculator, one that can perhaps lie on the base of your own code compiler. In order to achieve this, Dijkstra’s Shunting algorithm will be presented. If you are still into this, don’t hesitate to come back and tune in for the final segment of the series.
See you next time and if you have any questions regarding the topic of this article and/or related to the things we’ve learned so far, feel free to ask it, here in the discussion section of the article, or on the forums.
Have a great week and keep on coding!