|< C++ String Class 7 | Main | C++ STL Container 2 >| Site Index | Download |


 

 

 

 

 

 

MODULE 27

 THE STL CONTAINER C++ PROGRAMMING PART 1

vector, deque

 

 

 

 

 

My Training Period: xx hours

 

Program examples compiled using VC++7.0/.Net, win32 empty console mode application.  g++ examples given at the end of this Module. The source code for this tutorial is available in C++ STL Container source code.

 

The C++ STL container programming knowledge that should be acquired:

 

 

A Brief Intro

 

What do we have in this page?

  1. Introduction:  STL components

  2. What Is Containers?

  3. What Is Iterators?

  4. What IS Algorithms?

  5. Containers Type

  6. Sequence containers

  7. Associative containers

  8. Associative Container Category

  9. Common Container Operation

  10. Sequence Containers

  11. Vectors

  12. vector program example

  13. <vector> Header  Members

  14. vector, operators program example

  15. vector Class Template

  16. A vector Class Template Members

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

27.1  Introduction:  STL components

  • The STL consist of the containers, iterators, and algorithms.

27.1.1  What Is Containers?

  • Container classes’ purpose is to contain other objects.  Each of these classes is a template, and can be instantiated to contain any type of object.

  • The STL container classes include vector, list, deque, set, multiset, map, multimap, hash_set, hash_multiset, hash_map and hash_multimap to suit different kind of tasks.  You may find other containers that are implementation dependent/extension.

27.1.2  What Is Iterators?

  • It is a pointer used to manipulate the elements of the objects’ collections. These collections may be containers or subsets of containers. Iterators provide common interface for any arbitrary container type.

  • Every container class provides its own iterator type but when you try the program examples later, most of the containers have a common iterator types.  It is a smart pointer. For simple example, to increment an iterator you call operator ++. To access the value of an iterator you may use operator *.

27.1.3  What Is Algorithms?

  • Used to process the elements of collections. For example, algorithms can search, sort and modify. Algorithms use iterators. Thus, an algorithm has to be written only once to work with arbitrary containers because the iterator interface for iterators is common for all container types.

  • We can use a general algorithm to suit our needs even if that need is very special or complex. You will find in the program examples later, most of the member functions for processing the elements or data are common for various containers.

  • The data and operations in STL are decoupled. Container classes manage the data, and the operations are defined by the algorithms, used together with the iterators.

  • Conceptually, iterators are the linker between these two components. They let any algorithm interact with any container, graphically shown below.

C++ STL Container Iterator and Algorithm relationship illustration

  • Theoretically also, you can combine every kind of container with every kind of algorithm.  All components work with arbitrary types, a good example of the generic programming concept.

  • Containers and algorithms are generic for arbitrary types and classes respectively. The STL provides even more generic components. By using certain adapters and function objects (or functors) you can supplement, constrain, or configure the algorithms and the interfaces for special needs.

  • In this module we will discussed in detail about containers and at the same time the iterators and algorithm also will be introduced as well.

27.3  Containers Type

27.3.1  Sequence containers

27.3.2  Associative containers

27.3.2.1  Associative Container Category

*i = t.

i is of type map<int, double>

(*i).second = 3

27.4  Common Container Operation

Sample Code

Operation

con, con1 and con2 are containers.

ContainerType con

e.g. vector<int> vec0

Creates an empty container without any element.

ContainerType con1(con2)

e.g. vector<int> vec0(vec1)

Copies a container of the same type.

ContainerType con(begin,end)

e.g.

vector<int> vec0(p.begin(),p.end())

Creates a container and initializes it with copies of all elements of [begin, end).

con.~ContType()

Deletes all elements and frees the memory.

con.size()

Returns the actual number of elements.

con.empty()

Returns whether the container is empty, equivalent to size()==0, but might be faster.

con.max_size()

Returns the maximum number of elements possible.

con1 == con2

Returns whether con1 is equal to con2.

con1 != con2

Returns whether con1 is not equal to con2, equivalent to !(con1==con2)

con1 < con2

Returns whether con1 is less than con2

con1 > con2

Returns whether con1 is greater than con2, equivalent to con2 < con1.

con1 <= con2

Returns whether con1 is less than or equal to con2, equivalent to !(con2<con1).

con1 >= con2

Returns whether con1 is greater than or equal to con2, equivalent to !(con1<con2).

con1 = con2

Assignment, assigns all elements of con1 to con2.

con1.swap(con2)

Swaps the data of con1 and con2.

swap(con1,con2)

Same but a global function.

con.begin()

Returns an iterator for the first element.

con.end()

Returns an iterator for the position after the last element.

con.rbegin()

Returns a reverse iterator for the first element of a reverse iteration.

con.rend()

Returns a reverse iterator for the position after the last element of a reverse iteration.

con.insert(position,element)

Inserts a copy of element.

con.erase(begin,end)

Removes all elements of the range [begin, end), some containers return next element not removed.

con.clear()

Removes all elements, making the container empty.

con.get_allocator()

Returns the memory model of the container.

 

Table 27.1:  Common Operations Examples of Container Classes

// ls is a linked list of int

list<int> ls;

...

// copy all elements of the ls list into a con vector

vector<int> con(ls.begin(), ls.end());

 

27.5  Sequence Containers

27.5.1  Vectors

  • A vector manages its elements in a dynamic array. It enables random access.  Appending and removing elements at the end of the array is very fast.

  • However, inserting an element in the middle or at the beginning of the array takes time because all the following elements have to be moved to make room for it while maintaining the order.

  • It allows constant time insertions and deletions at the end of the sequence. Inserting or deleting elements in the middle of a vector requires linear time.  The structure of vector can be depicted as follow:

C++ STL Container vector

  • Vector reallocation occurs when a member function must increase the sequence contained in the vector object beyond its current storage capacity. Other insertions and deletions may alter various storage addresses within the sequence.

 

// vector example

#include <iostream>

// vector header file

#include <vector>

using namespace std;

 

int main()

{

    // vector container for integer elements declaration

    vector<int> coll;

    

    // append or push elements with values 1 to 10

    for(int i=1; i<=10; ++i)

        coll.push_back(i);

    // print all elements separated by a space

    for(i=0; i<coll.size(); ++i)

        cout<<coll[i]<<' ';

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL Container vector program example

<vector> Header  Members

Operators

 

Operator

Brief Description

operator!=

Tests if the vector object on the left side of the operator is not equal to the vector object on the right side.

The return value is true if the vectors are not equal; false if the vectors are equal.

operator<

Tests if the vector object on the left side of the operator is less than the vector object on the right side.

The return value is true if the vector on the left side of the operator is less than the vector on the right side of the operator; otherwise false.

operator<=

Tests if the vector object on the left side of the operator is less than or equal to the vector object on the right side.

The return value is true if the vector on the left side of the operator is less than or equal to the vector on the right side of the operator; otherwise false.

operator==

Tests if the vector object on the left side of the operator is equal to the vector object on the right side.

The return value is true if the vector on the left side of the operator is equal to the vector on the right side of the operator; otherwise false.

operator>

Tests if the vector object on the left side of the operator is greater than the vector object on the right side.

The return value is true if the vector on the left side of the operator is greater than the vector on the right side of the operator; otherwise false.

operator>=

Tests if the vector object on the left side of the operator is greater than or equal to the vector object on the right side.

The return value is true if the vector on the left side of the operator is greater than or equal to the vector on the right side of the vector; otherwise false.

 

Table 27.2

// vector, operators

#include <vector>

#include <iostream>

using namespace std;

 

int main()

{

    // vector container for integer elements declaration

    vector<int> vec1, vec2, vec3;

    

    cout<<"vec1 data: ";

    // append elements with values 1 to 10

    for(int i=1; i<=10; ++i)

           vec1.push_back(i);

    // print all elements separated by a space

    for(i=0; i<vec1.size(); ++i)

           cout<<vec1[i]<<' ';

    cout<<endl;

    cout<<"vec2 data: ";

    // append elements with values 1 to 10

    for(i=11; i<=20; ++i)

           vec2.push_back(i);

    // print all elements separated by a space

    for(i=0; i<vec2.size(); ++i)

           cout<<vec2[i]<<' ';

    cout<<endl;

    cout<<"vec3 data: ";

    // append elements with values 1 to 10

    for(i=1; i<=10; ++i)

           vec3.push_back(i);

    // print all elements separated by a space

    for(i=0; i<vec3.size(); ++i)

           cout<<vec3[i]<<' ';

    cout<<"\n\n";

    cout<<"Operation: vec1 != vec2"<<endl;

    if(vec1 != vec2)

          cout<<"vec1 and vec2 is not equal."<<endl;

    else

          cout<<"vec1 and vec2 is equal."<<endl;

    cout<<"\nOperation: vec1 == vec3"<<endl;

    if(vec1 == vec3)

          cout<<"vec1 and vec3 is equal."<<endl;

    else

          cout<<"vec1 and vec3 is not equal."<<endl;

    cout<<"\nOperation: vec1 < vec2"<<endl;

    if(vec1 < vec2)

          cout<<"vec1 less than vec2."<<endl;

    else

          cout<<"vec1 is not less than vec2."<<endl;

    cout<<"\nOperation: vec2 > vec1"<<endl;

    if(vec2 > vec1)

          cout<<"vec2 greater than vec1."<<endl;

    else

          cout<<"vec2 is not greater than vec1."<<endl;

    cout<<"\nOperation: vec2 >= vec1"<<endl;

    if(vec2 >= vec1)

          cout<<"vec2 greater or equal than vec1."<<endl;

    else

          cout<<"vec2 is not greater or equal than vec1."<<endl;

    cout<<"\nOperation: vec1 <= vec2"<<endl;

    if(vec1 <= vec2)

          cout<<"vec1 less or equal than vec2."<<endl;

    else

          cout<<"vec1 is not less or equal than vec2."<<endl;

    return 0;

}

 

Output:

 

C++ STL Container vector operator

 

A vector Class Template

 

Class

Description

vector

A template class of sequence containers that arrange elements of a given type in a linear arrangement and allow fast random access to any element.

 

Table 27.3

A vector Class Template Members

 

vector Class template Typedefs

 

Typedef

Description

allocator_type

A type that represents the allocator class for the vector object.

const_iterator

A type that provides a random-access iterator that can read a const element in a vector.

const_pointer

A type that provides a pointer to a const element in a vector.

const_reference

A type that provides a reference to a const element stored in a vector for reading and performing const operations.

const_reverse_iterator

A type that provides a random-access iterator that can read any const element in the vector.

difference_type

A type that provides the difference between the addresses of two elements in a vector.

iterator

A type that provides a random-access iterator that can read or modify any element in a vector.

pointer

A type that provides a pointer to an element in a vector.

reference

A type that provides a reference to an element stored in a vector.

reverse_iterator

A type that provides a random-access iterator that can read or modify any element in a reversed vector.

size_type

A type that counts the number of elements in a vector.

value_type

A type that represents the data type stored in a vector.

 

Table 27.4

 

vector Class Template Member Functions

 

Member 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 point 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()

Add 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()

Vector constructor, 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.

 

Table 27.5

 

tenouk C++ STL programming tutorial

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL container related reading:

 

  1. The source code for this tutorial is available in C++ STL Container source code.

  2. A complete C & C++ Standard Library documentation that includes STL.

  3. Check the best selling C / C++ books at Amazon.com.

 

 

 

 

 

 

|< C++ String Class 7 | Main | C++ STL Container 2 >| Site Index | Download |


C++ STL Container Classes:  Part 1 | Part 2 | Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 | Part 9 | Part 10 | Part 11