HomeC&C++WainTutorialsSamplesTip & TrickTools

Here I will try to explain some of the basic features of STL containters.
The containers share some characteristics but are optimized for different purposes. They all store elements of the same type, you can use iterators to loop through an container.

First the most simple one, the vector. You can use a std::vector as as smart and dynamic array. It can do what an array can, and a lot more:
1: It can be sized dynamically.
2: You can allways ask it for it's size.
3: You can return it from a function.
4: You don't have to care about allocation and deallocation.

To create a vector of int's:
std::vector<int> MyIntVector;
To create a vector of doubles, with an initial size of 10:
To change the size use resize:
Or use clear() to set the size to zero.
To add an element to the end:
To get element number N use the [] operator, as an array:
MyDoubleVector[4] = 12;
int n = MyIntVector[3];
Remember that [index] must exist, before you try to use it.
As any other std containers, the vector has iterators, which can be handy:
std::vector<int>::iterator it;
for(it = MyVector.begin(); it != MyVector.end(); it++)
   std::cout << *it << std::endl;
You don't have to use iterators to loop thru the vector, you can also use:
std::vector<int>::size_type i;
for(i = 0; i < MyVector.size(); i++)
    std::cout << MyVector[i] << std::endl;
size() returns the size of the vector, i.e. the number of elements in the vector.
std::vector<int>::size_type is the type of the vector's size, it's an integer, but it's unsigned on some platforms and signed on others, its normally an int, but might be a long or a short, so better use the size_type, even if a int will normally do.

You can return it from a function:
std::vector<int > Func2()
   std::vector<int >::size_type i;
   for(i = 0; i < 6; i++)
      Local.push_back(i ^ 0x0A);
   return Local;
And assign it:
MyVector = Func2();
You can sort it with:
std::sort(MyVect.begin(), MyVect.end());
You can remove any element with the erase function (in this case index 1):
MyVector.erase(MyVector.begin() + 1);
Or you can remove a number of elements at once:
MyVector.erase(MyVector.begin() + 1, MyVector.begin() + 5);
Notice that the above line removes elements 1,2,3,4; ranges in STL is allways including the first but not the last. MyVector.end() is thus an element just after the end of the vector.

Some might ask if there is a price to pay for all these features. Yes, there is a price, but it's small. The vector itself will take up some space, from 12 to 32 bytes on the four compilers I have by hand. A vector might be slower than an array, but the difference is negligible, provided that you turn your compilers optimization on.

We have already seen that we can create a vector of int's with:
std::vector<int >IntVector;
And to set the initial size to 10:
std::vector<int >IntVector(10);
But there is another argument you can use, the initial value:
std::vector<int >IntVector(10, 11);
Here all initial elements will have the value 11.
To create a 2 dimensional vector:
std::vector<std::vector<int > >Int2dVector
And to set the initial size, for both dimensions:
std::vector<std::vector<int > >Int2dVector(10, std::vector<int >(20));
This create a vector with 10 vectors of 20 ints, corresponding to:
int Int2dArray[10][20];
You can naturally create as many dimensions as you like (well allmost).
In some cases it is handy to use a typedef:
typedef std::vector<int >IntVectorType;
This is just a int vector type, to create 2 dimensional vector type:
typedef std::vector<IntVectorType >Int2dVectorType;
To use them:
IntVectorType IntVector(10);
Which is a one dimensional vector vith initial size 10.
Int2dVectorType Int2dVector(10, IntVectorType(20));
Which is a two dimensional vector as the one above.
The typedef are especially handy when using iterators/size_type on the vector, so you don't have to type:
std::vector<std::vector<int> >::iterator i;
Over and over, but kan use:
Int2dVector::iterator i;
You can allso typedef the iterator and the size_type:
typedef Int2dVectorType::iterator Int2dVectorTypeIterator;
typedef Int2dVectorType::size_type IntVectorTypeSizeType;

And now a simple program to read the content of file into a std::vector of std::string's.
First we open the file:
   std::ifstream is("test.txt");
test.txt is simply the name of the file to read.
We must check that we could open the file for reading, and warn the user if we could not:
      std::cout << "Failed to open file" << std::endl;
      return 0;
Then we create the std::vector of std::string's:
   std::vector<std::string >MyVector;
To read the file we use the std::copy function:
The std::back_inserter will append to the end of the vector, this is requered as it was created empty.
This is fine, except that this metode does not read lines but words, to read lines you can use:
   while(std::getline(is, Line))
Now the file has been read, and we can write it to std::cout, again with the std::copy function:
It's as simple as that. You have to include: iostream, fstream, iterator, vector, string.

We will now crate an extension to the file input/output program.
You can use the same method to read and write your own classes. If you want to create a collection of you CD-records you might create a class like this:
class CDRecordClass
   std::string Title;
   std::string Artist;
Then you have to create two operators for your class, a << and a >> operator:
std::istream &operator >> (std::istream &is,
                           CDRecordClass &CDRecord)
   std::getline(is, CDRecord.Title);
   std::getline(is, CDRecord.Artist);
   return is;

std::ostream &operator <<  (std::ostream &os,
                           const CDRecordClass &CDRecord)
   os << CDRecord.Title << std::endl;
   os << CDRecord.Artist;
   return os;
The input operator uses std::getline rather than >> as the title and artist name might contain spaces.
You can use these operators as any other input and output operators, e.g:
   CDRecordClass CDRecord;
   std::cout << CDRecord << std::endl;
Or you can use them with the copy functions used in the program from above.
The complete code and a sample application here, it reads a file, asks for a new entry, prints it, and write everything back into the file.

To sort the vector used:
   std::sort(MyVector.begin(), MyVector.end());
But we have to tell std::sort how to compare two items. For this we create a < operator:
bool operator < (const CDRecordClass &lhs, const CDRecordClass &rhs)
   return lhs.Artist < rhs.Artist;
This will sort the list according to artist, we could create a slightly more advanced comparison criteria:
bool operator < (const CDRecordClass &lhs, const CDRecordClass &rhs)
   if(lhs.Artist != rhs.Artist)
     return lhs.Artist < rhs.Artist;
   return lhs.Title < rhs.Title;
Which will sort according to artist first, if two albums have same artist it will use the title.

Enough on vectors, lets have a look at std::map.
A std::map is a container, that holds a ordered sequence of pairs.
The first part of the pair is the key, which determins how the map is sorted. The second part of the pair is the value part.
The pair used by maps are a template class on its own called std::pair. As such the key is called first and the value part is called second.
You can use any type as key, but the key must be compareable, that is there must exist a < operator for it, which is the case for standard types. If you use your own type/class you must create a < operator.
You can create a map:
std::map<std::string, int>MyMap;
This is a map for which a std::string is used as key, and the value is an int.
You can add elements to the map:
   MyMap["Peter"] = 12;
   MyMap["John"] = 14;
The [ ] operator will create an entry if it does not exist, and assign the value.
This makes the list look a bit like an array in which you can any type as index, not just ints.
Internaly an map is organized as an binary tree, so to lookup entries is fast, but not as fast as for an array or vector.
To print all entries in the map:
   std::map<std::string, int>::iterator it;
   for(it = MyMap.begin(); it != MyMap.end(); ++it)
      std::cout << it->first << " " << it->second << std::endl;
This is the same as for any other container, except that the iterator is a pointer to a pair.
To remove an entry from the list:
If you use the [ ] operator to add members to the map, there is no way to know if an entry was added to the map, or an existing entry just got a new walue.
You can use the insert function to add members:
   MyMap.insert(std::make_pair("Alice", 33));
The insert function returs a std::pair, for which first is an iterator to the new entry, and second is an boolean which tells if an entry was added:
   std::pair<std::map<std::string, int>::iterator, bool>Result;
   Result = MyMap.insert(std::make_pair("Alice", 33));
      std::cout << Result.first->first << " Was added" << std::endl;
      std::cout << "Alice was not added" << std::endl;
If the else part is executed Alice did exist in the map and was not added and the value part of Alices entry is not changed.
If you just want to check if the entry was added:
   if((MyMap.insert(std::make_pair("John", 55))).second)
      std::cout << "John has been added" << std::endl;
If you just want to check if the entry exists:
   it = MyMap.find("Alice");
   if(it != MyMap.end())
      std::cout << "Found Alice: " << it->second << std::endl;
An std::map can not have more than one entry with the same key, if you need this you have to use an std::multimap.

std::queue is a very simple container.
It is a sequence of elements, you can add elements in the back of the queue, and you can get from the front of the queue. That is, a std::queue is a FIFO buffer.
To create a queue of int:
std::queue<int >MyQueue;
As you can only add elements to the start of the queue there is only one push function:
std::queue does not have an insert function, as you can't insert at arbitrary positions.
You can inspect the front and the back of the queue:
   std::cout << MyQueue.back() << std::endl;
   std::cout << MyQueue.front() << std::endl;
back() returns a reference to the most recent added element, and font() the oldest element.
But a queue does not have iterators, so there is no way to see whats in the middle of the queue, and there is no find function, so you can't check if a value is in the queue.
You can remove the element at the end of the queue:
And you can check the size of the queue:
   std::cout << MyQueue.size() << std::endl;
If you need to insert and remove at both ends of a queue you have to use a std::deque, which also has iterators.

Some notes on std::stack
A std::stack is a container, which stores a sequence of elements of some type. You can add elements to a stack in one end, the top, and remove them from the same end. That is a stack works as a LIFO, the one you get is the most resent added.
A simple example:
#include <stack>
#include <iostream>
int main()
   std::stack<int >MyStack;
   std::cout << MyStack.top() << std::endl;
   std::cout << MyStack.top() << std::endl;
Which will show 321 and 123.
Apart from the adding elements, peeking the top, and removing you can get the size of the stack, and check if it is empty:
   std::stack<int >MyStack;
   std::cout << MyStack.size() << std::endl;
   std::cout << (MyStack.empty() ? "Empty" : "Not Empty") <<
There is no iterators or other ways to inspect anything but the top element of the stack.
You can also create your own container. This might be handy, and you will learn how a container works.
The containter will behave as a normal array, the size will be fixed when the object is created. The container has no overhead compared to a normal array.
First the basic:
template <typename T, size_t N>
class ArrayClass
   T Array[N];
T is the type, e.g. and int, N is the size of the array.
To use it:
   ArrayClass<int, 10> Array;
Which will create a array of 10 ints.
Then we will create some types, as for any other container:
   typedef T *iterator;
   typedef size_t size_type;
But we have to add a way to access the array:
   T &operator [] (size_type idx) { return Array[idx]; }
Which can be used as the [ ] for arrays and std::vector:
   Array[7] = 7;
   int x = Array[7];
We must then have a size() function as the other containers:
   size_type size() const { return N; }
With these we can use the array:
   ArrayClass<int, 10>::size_type i;
   for(i = 0; i < Array.size(); i++)
      Array[i] = i;
And now the begin and end functions:
   iterator begin() { return Array; }
   iterator end() { return &Array[N]; }
Which can be used:
   ArrayClass<int, 10>::iterator it;
   for(it = Array.begin(); it != Array.end(); it++)
      std::cout << *it << std::endl;
We can use our container with the normal algorithms:
   std::swap(Array[4], Array[6]);
   std::sort(Array.begin(), Array.end());
   std::fill(Array.begin(), Array.end(), 111);
Now we just need a at() function which is to throw a exception if we try to use an illegal index:
   T &at(size_type idx)
      if(idx < size())
         return Array[idx];
      throw std::out_of_range("ArrayClass::at()");
To test it:
      std::cout << Array.at(10) << std::endl;
   catch(const std::exception &e)
      std::cerr << "Catch: " << e.what() << std::endl;

One disadvantage with STL containers is that they can only store elements of the same type, but there are ways to circumvent this limitation.
We will use the fact that pointers to classes who are derived from the same base class, are close enough to beeing "same type" to be stored in the same container.
The example code here will use a std::vector, but the methods can be used for any STL container.
First we define a base class, that will know what type the derived class is:
class BaseClass
   enum ClassType
   const ClassType Type;
   virtual ~BaseClass(){}
   BaseClass(ClassType aType) : Type(aType)
The Type member tells which class the derived class is, the enumeration must be extended for each class which are derived from the base class. Type is const as classes can't change type on-the-fly.
The default constructor (the one without arguments) is private as we want to force the derived classes to use the other constructor, which sets the Type member. This constructor is protected as we do not want to let users create an instance of the base class, they have to derive a class from the base class.
The destructor is not strictly necessary, but we add it as we want to be able to use dynamic_cast, more on that later.
Then we can create some classes derived from BaseClass:
class DoubleClass : public BaseClass
   DoubleClass(double aD) : BaseClass(DoubleType), D(aD)
   double D;

class IntClass : public BaseClass
   IntClass(int aI) : BaseClass(IntType), I(aI)
   int I;
And now we can create the container and add some objects to it:
   std::vector<BaseClass *>MyVector;
   MyVector.push_back(new IntClass(123));
   MyVector.push_back(new DoubleClass(1.123));
To get an element from the vector, is a bit more tricky, as we first has to check which type we get.
One simple approach:
   if(MyVector[i]->Type == BaseClass::IntType)
      IntClass *Int = (IntClass *)MyVector[i];
      std::cout << Int->I << std::endl;
Now this cast is not nice, this is C++ after all, so we can do better:
   DoubleClass *Double = dynamic_cast<DoubleClass *>(MyVector.[i]);
      std::cout << Double->D << std::endl;
      std::cout << "Ups it was not a DoubleClass" << std::endl;
dynamic_cast is a cast operator, which knows if the cast is legal, and can take propper action if not. As we cast a pointer dynamic_cast will return a NULL pointer if the cast was not legal, for other types it will throw an exception.
It could be nice if we could avoid putting casts everywhere, so lets add some "cast functions" to the base class:
   class DoubleClass *GetAsDoubleClass();
   class IntClass *GetAsIntClass();
We write class in front of the return type as the compiler don't know these types when we define BaseClass.
To implement these:
class DoubleClass *BaseClass::GetAsDoubleClass()
   DoubleClass *Ret = dynamic_cast<DoubleClass *>(this);
class IntClass *BaseClass::GetAsIntClass()
   IntClass *Ret = dynamic_cast<IntClass *>(this);
And to use them:
   DoubleClass *Double = MyVector[i]->GetAsDoubleClass();
   IntClass *Int = MyVector[i]->GetAsIntClass();
But you still have to check if the pointer is a NULL pointer.
It might be more handy to use exceptions, to do this we let the cast-functions throw an exception if the conversion fails:
class DoubleClass *BaseClass::GetAsDoubleClass()
   if(Type != DoubleType)
      throw std::bad_cast();
   DoubleClass *Ret = dynamic_cast<DoubleClass *>(this);
      throw std::bad_cast();
   return Ret;
Now we have to catch these:
      IntClass *Int = MyVector[1]->GetAsIntClass();
   catch (std::bad_cast)
      std::cout << "Ups, bad cast" << std::endl;
You can naturally use try/catch on an block of code, e.g. a compte function.
I have put the code I wrote to test this here.

Another way to do this is to use the visitor design pattern. I will create an example one of these days.