Openismus - C++ Standard Containers

C++ Standard Library Containers

Introduction
Declaring
Inserting Items
Iterating
Algorithms
Commonly used containers

Introduction

The C++ Standard Library includes several very useful standard containers, such as lists and vectors. Because they are templates they can be used to store your own C++ types while still allowing your compiler to do proper type-checking.

Previously, programmers had tended to create their own implementations for such containers, which were specialised for only one class, had their own non-standard interfaces, and were generally subject to memory management errors. The Standard Library containers make our life easier - resulting in programs which are written faster, are more robust, and are more readable.

There are several containers, such as list, vector, map, set, stack, and string. Some of these are described here, but they all have very similar interfaces. After you have used one container, you should have no problem understanding the documentation for the others.

Declaring

The Standard Containers are all in the std namespace, so you will need to declare them like so:
std::list<MyThing> listOfMyThings;

The contained item class should have a copy constructor and an assignment operator. Note that Visual C++ requires some extra operators to be defined, although they should not really be necessary.

You should typedef the template specialization, because you will probably need to use it more than once.

For instance:
typedef std:list<Item> type_listOfNodes;
type_listOfNodes m_listOfNodes;

Iterating

To access the items in the container you need to use an iterator. The iterator provides access to a particular item via the dereferencing operator (*, or ->), and it can change to the next or previous item by using the - or + operators.

Each container has a different iterator, but you can declare an iterator very easily, like so:
type_listOfNodes::iterator iter;
Each container has a begin() method, which returns an iterator which gives access to the first item, and an end() method which returns an iterator representing the position just after the last item. By using these in a loop, you can access each item in turn. For example:
typedef std:list<Item> type_listOfNodes;
type_listOfNodes m_listOfNodes;

...//Some code that adds items to the list.

for(type_listOfNodes::iterator iter = m_listOfNodes.begin(); iter != m_listOfNodes.end(); iter++)
{
    Item itemTemp = *iter;
    ...
}

Inserting Items

You can add items to most standard containers by using the insert(), push_front(), or push_back() methods.

The push_front() and push_back() methods accept an item as their argument. For instance:
typedef std:list<Item> type_listOfNodes;
type_listOfNodes m_listOfNodes;

Item itemOne;
... //Do some stuff with itemOne.
m_listOfNodes.push_back(itemOne); //Add the item.
The insert() method accepts an iterator to the item before which you wish to insert the new item. For instance,
typedef std:list<Item> type_listOfNodes;
type_listOfNodes m_listOfNodes;

Item itemToFind;
...//Set up the itemToFind.
type_listOfNodes::iterator iter = m_listOfNodes.find(itemToFind); //See Find in the Algorithms section.


if( iter != m_listOfNodes.end() )
{
    Item itemOne;
    ... //Do some stuff with itemOne.
    m_listOfNodes.insert(iter, itemOne); //Add the item.
}
Some containers, such as vector, map, or string, have special methods of adding or accessing items. These are described in the Commonly Used Containers section.

Notice that we are adding items to the container, not a pointer to the item. This means that your item class must have a copy constructor and a =operator method, but it saves you from the trouble of memory management. You can of course have a container of pointers, by declaring your container with the appropriate template specialisation.

Algorithms

There are various standard algorithms which can be used with the standard containers, to do things such as sorting, finding, reordering, or selective deletion of items. To use these you will need to #include the <algorithms> header. There are many standard algorithms, so I will describe only the most commonly used: std::sort(),and std::find().

sort

The std::sort algorithm can be used with containers which have random-access iterators. By default, the < operator of the item's class will be used to sort the items. For example:
std::sort(vecExample.begin(), vecExample.end();
But you can provide an additional sort function. For instance:
std::sort(vecExample.begin(), vecExample.end(), CustomSort);
where CustomSort() is previously defined as:
bool CustomSort(const CExample& a, const CExample& b)
{
    return a < b; //example comparison.
}
Other containers have a sort() method. For instance:
std:list<Item> m_listOfNodes;
...
m_listOfNodes.sort(predSort)
The sort() method can be used with or without the predicate. The default uses the < operator of the items. At present the second method (using the container's sort() method) is not possible with the Microsoft Visual C++ implementation.

find
You can do a very simple search for a specific object. For example:
type_listOfNodes::iterator iter = m_listOfNodes.find(itemToFind);
if( iter != m_listOfNodes.end() )
{
    Item itemTemp = *iter;
    ...
}
Or, you can provide a predicate function or class to find_if() to use a more complicated find criteria. When using a predicate class, the ()operator of that class will be used by find_if() to check whether the item matches the criteria. The ()operator could use member data which you have previously set, in order to customise the find criteria. For example:
PredFind predFind;
predFind.SetThing(thingOne); //customise the find predicate.

type_listOfNodes::iterator iter = m_listOfNodes.find_if(m_listOfNodes.begin(), m_listOfNodes.end(), predFind);
if( iter != m_listOfNodes.end() )
{
    Item itemTemp = *iter;
    ...
}
Where PredFind is previously defined as:
class PredFind
{
protected:
    Thing m_thing;
public:
    PredFind() {}

    bool operator() (Item item)
    {
        return item.foo(m_thing);
    }

    void SetThing(Thing& thing) {m_thing = thing;}

};

Commonly Used Containers

map
You can use a map to store data which can later be retrieved by using a key. This is a bit like using a primary key to refer to a record in a database table.

You will need to #include <map>.

Declaring
typedef std:map<int, Item> type_mapItems;
type_mapItems m_mapItems;
Assigning
Item itemTemp;
itemTemp.SetName("foo");
itemTemp.SetWidth(573);

m_mapItems[2] = itemTemp;
Retrieving

You can use array notation to access the item, but you should use find() before doing so. The array notation will not return a null or error if the key is not present - it will just add an item with that key by using the item's default constructor, then return a copy of it to you.
Item itemTemp;
type_mapItems::iterator iterFind = m_mapItems.find(2);
if( iterFind != m_mapItems.end() )
{
    itemTemp = *iterFind;
    ...
}
Iterating

A map iterator refers to a std::pair, which gives you access to both the key and the value. You can access the two parts like so:
typedef std:map<int, Item> type_mapOfItems;
type_mapOfItems m_mapOfItems;

...//Some code that adds items to the map.

for(type_mapOfItems::iterator iter = m_mapOfItems.begin(); iter != m_mapOfItems.end(); iter++)
{
    int iKey = iter->first;
    Item itemValue = iter->second;
    ...
}
list
Lists are ideal for storage of variable numbers of items. A std::list is an implementation of a linked list - one of the most commonly used memory management techniques.

For example:
//Declare a list:
typedef std:list<Item> type_listOfNodes;
type_listOfNodes m_listOfNodes;

//Insert some items:
Item itemOne;
itemOne.SetThing(1);
Item itemTwo;
itemTwo.SetFoo(5);
m_listOfNodes.push_back(itemOne);
m_listOfNodes.push_back(itemTow);

//Iterate through the list:
for(type_listOfNodes::iterator iter = m_listOfNodes.begin(); iter != m_listOfNodes.end(); iter++)
{
    Item itemTemp = *iter;
    ...
}

//Copy the list:
type_listOfNodes m_listCopy;
m_listCopy = m_listOfNodes;
vector
Vectors can be used in place of arrays, but unlike arrays they can be safely passed in function arguments and return values, without worries about memory management. Also, they can be resized at runtime.

A std::vector is like a std::list which can be accessed via the square-bracket array operators.

You will need to #include <vector>.

For example:
//Declare a vector:
typedef std::vector<int> type_vecOfInts;
type_vecOfInts vecOfInts(10);

//Access the vector:
vecOfInts[0] = 1;
int iTest = vecOfInts[5];

//Resize the vector:
vecOfInts.resize(20);

//Copy the vector:
type_vecOfInts vecCopy;
vecCopy = vecOfInts;
string
The std::string is fast becoming the standard way to deal with strings in C++. There is no longer any need for your code to expose character array pointers, or require discipline on the part of programmers who use your code.

You will need to #include <string>.

For example:
//Declare a string:
std::string strName;
strName = "Murray Cumming";

//Access the string's characters:
char chTest = strName[1];
strName[7] = "_";

//Concatenation:
strName += ", Programmer";

//Copy the string:
std::string strCopy;
strCopy = strName;

This work is licensed under a Creative Commons License.

C++ Standard Library Containers

Contents

Introduction

Declaring

Iterating

Inserting Items

Algorithms

sort

find

Commonly Used Containers

map

Declaring

Assigning

Retrieving

Iterating

list

vector

string