Brief Introduction to the STL Containers
(Page 1 of 4 )
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. 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.
Next: Sequence Containers >>
More C++ Articles
More By Gabor Bernat
