Click here to Skip to main content
Click here to Skip to main content

A study of STL container, Iterator and Predicates

By , 3 Dec 2006
Rate this:
Please Sign up or sign in to vote.

Sample Image - GoodCode.gif

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

Function

Description

assign

Erases a vector and copies the specified elements to the empty vector.

at

Returns a reference to the element at a specified location in the vector

back

Returns a reference to the last element of the vector

begin

Returns a random-access iterator to the first element in the container.

capacity

Returns the number of elements that the vector could contain without allocating more storage.

clear

Erases the elements of the vector

empty

Tests if the vector container is empty.

end

Returns a random-access iterator that points just beyond the end of the vector

erase

Removes an element or a range of elements in a vector from specified positions.

front

Returns a reference to the first element in a vector

get_allocator

Returns an object to the allocator class used by a vector

insert

Inserts an element or a number of elements into the vector at a specified position.

max_size

Returns the maximum length of the vector

pop_back

Deletes the element at the end of the vector

push_back

Adds an element to the end of the vector

rbegin

Returns an iterator to the first element in a reversed vector

rend

Returns an iterator to the end of a reversed vector

resize

Specifies a new size for a vector

reserve

Reserves a minimum length of storage for a vector object.

size

Returns the number of elements in the vector

swap

Exchanges the elements of two vectors.

vector

Constructs a vector of a specific size or with elements of a specific value or with a specific allocator or as a copy of some other

Vector Operators

Operator

Description

operator []

Returns a reference to the <SPAN style="FONT-FAMILY: 'Courier New'">vector element at a specified position.

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++)

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

JPandya
Web Developer
United States United States
Jigar Pandya has done Bachelors in Mathematics and Masters in computer science and application. He is a Microsoft Certified Technology Specialist.

Comments and Discussions

 
GeneralGood Article Pinmemberhiteshmaheta5-Dec-06 22:09 
Generalstd::list PinmemberTodd Smith3-Dec-06 22:53 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140421.2 | Last Updated 4 Dec 2006
Article Copyright 2006 by JPandya
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid