A study of STL container, Iterator and Predicates

• Download source files - 50 Kb
• Download demo project - 19 Kb

Introduction

This article aims to introduce container and Iterator of C++ Standard Template Library (STL) with the help of the std::vector. While covering container, this article covers some functions usage of the std::vector and while covering Iterator, this article covers predicates and function pointers.

Containers

Containers are objects that hold other objects. There are two types of containers:

1. Sequence container: It stores and allows data retrieval sequentially. E.g. the vector class defines a dynamic array, deque creates a double-ended queue, and list provides a linear list.

2. Associative container: It allows efficient retrieval of values based on keys. For example, a map provides access to values with unique keys. Thus, a map stores a key/value pair and allows a value to be retrieved given its key. 

Container uses allocator and predicates.

Allocators manage memory. Each container has defined for it an allocator. Allocators manage memory allocation for a container. The default allocator is an object of class allocator, but you can define your own allocators if needed by specialized applications. For most uses, the default allocator is sufficient.

Some containers use a special type of function called a predicate. There are two variations of predicates: unary and binary. A unary predicate takes one argument, while a binary predicate has two. These functions return true/false results. But the precise conditions that make them return true or false are defined by you.

Container	Description	Required Header
Bitset	A set of bits.	<bitset>
Deque	A double-ended queue.	<deque>
List	A linear list.	<list>
Map	Stores key/value pairs in which each key is associated with only one value.	<map>
Multimap	Stores key/value pairs in which one key may be associated with two or more values.	<map>
Multiset	A set in which each element is not necessarily unique.	<set>
priority_queue	A priority queue.	<queue>
Queue	A normal queue.	<queue>
Set	A set in which each element is unique.	<set>
Stack	A stack.	<stack>
Vector	A dynamic array.	<vector>

Iterators

Iterator gives ability to cycle through the elements stored in the containers. They are more or less pointers. There are five types of Iterators:

1. Random Access : Store and retrieve values. Elements may be accessed randomly.

2. Bidirectional : Store and retrieve values. Forward and backward moving.

3. Forward : Store and retrieve values. Forward moving only.

4. Input : Only retrieve, but not store values. Forward moving only.

5. Output : Only store, but not retrieve values. Forward moving only.

Apart from this STL also supports Reverse iterator. They are either bidirectional or random access. They move in the reverse direction. E.g. if it is pointing to last element then incrementing the pointer would point to the second last element.

Let’s take an example of vector template class to understand container, iterator and predicate:

Vector Overview

Vector is a container class and it implements dynamic array which grows as per need. The template specification for vector is shown here:

template <class T, class Aallocator = Allocator <T>>class vector

In order to use vector, you need to include <vector> header file.The vector is part of the std namespace, so you need to qualify the name. This can be accomplished as shown here:

using std::vector;

vector<int> vInts;

or you can fully qualify the name like this: std::vector<int> vInts;

Vector Member Functions

Vector Operators

Creating Vector

There are several constructors for the vector container. Following are most commonly used constructors

Empty vector for int:

vector<int> vInt;

Vector to hold 10 int:

vector<int> vInt(10);

Vector holding 10 int initialized with 0:

vector<int> vInt(10, int(0));

Vector from another vector int:

vector<int> vIntA(vIntB);

Filling Vector

std::vector<CItem> m_vItem;
m_vItem.push_back(Item);
    

Above code constructs m_vItem vector, which would hold objects of type CItem. puch_back would add element at the end of the vector.

Accessing Vector elements

std::vector<CItem>::iterator m_iItem;
for (m_iItem = m_vItem.begin();m_iItem != m_vItem.end(); m_iItem++) 
{
    index = m_List.InsertItem(0,m_iItem->GetNumber());
    m_List.SetItemText(index,1,m_iItem->GetName());
}

Above code constructs m_iItem Iterator. m_vItem.begin() would initialize Iterator at the start of the vector and looping it untill it reaches m_vItem.end(). The code also add item into the List.

Removing Vector elements

std::vector<CItem>::iterator end;
end = std::remove_if(m_vItem.begin(),m_vItem.end(),IsSelected);
m_vItem.erase(end,m_vItem.end());
        

Above code define end iterator. remove_if removes all elements which are in the range of m_vItem.begin() to m_vItem.end() and for which predicate IsSelected returns true. erase() function erase all the removed objects from vector.

IsSelected is a unary predicate. It takes one argument (object of type CItem) and returns true or false.

Conclusion

This article and sample project attached with it, would be good reference for all the developers who are just putting feet in the STL. It would also solve some basic queries of even experience STL developers.

References

  Herbert Schildt (Complete  Reference C++)