C++ STL (Standard Template Library) Tutorial and Examples

Free Information Technology Software and Development Magazine Subscriptions and Document Downloads

The Standard Template Libraries (STL's) are a set of C++ template classes to provide common programming data structures and functions such as doubly linked lists (list), paired arrays (map), expandable arrays (vector), large string storage and manipulation (rope), etc. The STL library is available from the STL home page. This is also your best detailed reference for all of the STL class functions available.

Also see our C++ Templates tutorial

STL can be categorized into the following groupings:

• Container classes:
  • Sequences:
    • vector: (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      (also see the YoLinux.com tutorial on using and STL list and boost ptr_list to manage pointers.)
    • deque: Array which supports insertion/removal of elements at beginning or end of array
    • list: (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
  • Associative Containers:
    • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
    • map (unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
  • Container adapters:
    • stack LIFO
    • queue FIFO
    • priority_queue returns element with highest priority.
  • String:
    • string: Character strings and manipulation
    • rope: String storage and manipulation
  • bitset: Contains a more intuitive method of storing and manipulating bits.
• Operations/Utilities:
  • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
  • algorithm: Routines to find, count, sort, search, ... elements in container classes
  • auto_ptr: Class to manage memory pointers and avoid memory leaks.

Also see the YoLinux.com GDB tutorial on dereferencing STL containers.

vector: Dynamic array of variables, struct or objects. Insert data at the end.

Simple example of storing STL strings in a vector. This example shows three methods of accessing the data within the vector:

Compile: g++ exampleVector.cpp

Run: ./a.out

Output:

Loop by index:
The number is 10
The number is 20
The number is 30

Constant Iterator:
The number is 10
The number is 20
The number is 30

Reverse Iterator:
The number is 30
The number is 20
The number is 10

Sample Output:
3
The number is 30
The number is 10

[Potential Pitfall]: Note that the iterator is compared to the end of the vector with "!=". Do not use "<" as this is not a valid comparison and may or may not work. The use of "!=" will always work.

---

Two / Three / Multi Dimensioned arrays using vector:

A two dimensional array is a vector of vectors. The vector contructor can initialize the length of the array and set the initial value.

Example of a vector of vectors to represent a two dimensional array:

Compile: g++ exampleVector2.cpp

Run: ./a.out

Loop by index:
0
1
10
11
20
21
      

---

A three dimensional vector would be declared as:

or declare all in one statement:

---

Using an iterator:

Example of iterators used with a two dimensional vector.

Compile: g++ exampleVector2.cpp

Run: ./a.out

Using Iterator:
10
20
30
100
200
300
      

[Potential Pitfall]: Note that "end()" points to a position after the last element and thus can NOT be used to point to the last element.

iter_jj = SS.end();
cout << *iter_jj << endl;

This will result in a "Segmentation fault" error.

Constructor/Declaration:

Method/operator	Description
vector<T> v;	Vector declaration of data type "T".
vector<T> v(size_type n);	Declaration of vector containing type "T" and of size "n" (quantity).
vector<T> v(size_type n,const T& t);	Declaration of vector containing type "T", of size "n" (quantity) containing value "t". Declaration: vector(size_type n, const T& t)
vector<T> v(begin_iterator,end_iterator);	Copy of Vector of data type "T" and range begin_iterator to end_iterator. Declaration: template vector(InputIterator, InputIterator)

Size methods/operators:

Method/operator	Description
empty()	Returns bool (true/false). True if empty. Declaration: bool empty() const
size()	Number of elements of vector. Declaration: size_type size() const
resize(n, t=T())	Adjust by adding or deleting elements of vector so that its size is "n". Declaration: void resize(n, t = T())
capacity()	Max number of elements of vector before reallocation. Declaration: size_type capacity() const
reserve(size_t n)	Max number of elements of vector set to "n" before reallocation. Declaration: void reserve(size_t)
max_size()	Max number of elements of vector possible. Declaration: size_type max_size() const

Note: size_type is an unsigned integer.

Other methods/operators:

Method/operator	Description
erase() clear()	Erase all elements of vector. Declaration: void clear()
erase(iterator) erase(begin_iterator,end_iterator)	Erase element of vector. Returns iterator to next element. Erase element range of vector. Returns iterator to next element. Declarations: iterator erase(iterator pos) iterator erase(iterator first, iterator last)
= Example: X=Y()	Assign/copy entire contents of one vector into another. Declaration: vector& operator=(const vector&)
<	Comparison of one vector to another. Declaration: bool operator<(const vector&, const vector&)
==	Returns bool. True if every element is equal. Declaration: bool operator==(const vector&, const vector&)
at(index) v[index]	Element of vector. Left and Right value assignment: v.at(i)=e; and e=v.at(i); Declaration: reference operator[](size_type n)
front() v[0]	First element of vector. (Left and Right value assignment.) Declaration: reference front()
back()	Last element of vector. (Left and Right value assignment.) Declaration: reference back()
push_back(const T& value)	Add element to end of vector. Declaration: void push_back(const T&)
pop_back()	Remove element from end of vector. Declaration: void pop_back()
assign(size_type n,const T& t)	Assign first n elements a value "t".
assign(begin_iterator,end_iterator)	Replace data in range defined by iterators. Declaration:
insert(iterator, const T& t)	Insert at element "iterator", element of value "t". Declaration: iterator insert(iterator pos, const T& x)
insert(iterator pos, size_type n, const T& x)	Starting before element "pos", insert first n elements of value "x". Declaration: void insert(iterator pos, size_type n, const T& x)
insert(iterator pos, begin_iterator,end_iterator)	Starting before element "pos", insert range begin_iterator to end_iterator. Declaration: void insert(iterator pos, InputIterator f, InputIterator l)
swap(vector& v2)	Swap contents of two vectors. Declaration: void swap(vector&)

Iterator methods/operators:

Method/operator	Description
begin()	Return iterator to first element of vector. Declaration: const_iterator begin() const
end()	Return iterator to end of vector (not last element of vector but past last element) Declaration: const_iterator end() const
rbegin()	Return iterator to first element of vector (reverse order). Declaration: const_reverse_iterator rbegin() const
rend()	Return iterator to end of vector (not last element but past last element) (reverse order). Declaration: const_reverse_iterator rend() const
++	Increment iterator.
--	Decrement iterator.

---

Vector Links:

• YoLinux.com GDB tutorial on dereferencing vectors and STL containers
• SGI: vector - Detail of all vector member functions and operators available.
• Also see Boost ptr_vector - used to hold vector of pointers.

list: Linked list of variables, struct or objects. Insert/remove anywhere.

Two examples are given:

1. The first STL list example is using a native data type (int)
2. The second for a list of objects (class instances)

They are used to show a simple example and a more complex real world application.

Lets start with a simple example of a program using STL for a linked list to store integers:

Compile: g++ example1.cpp

Run: ./a.out

Output: 0 2 0 5 6

[Potential Pitfall]: In Red Hat Linux versions 7.x one could omit the "using namespace std;" statement. Use of this statement is good programming practice and is required in Red Hat 8.0 and later.

[Potential Pitfall]: Red Hat 8.0 and later requires the reference to "#include <iostream>". Red Hat versions 7.x used "#include <iostream.h>".

The following example stores a class object in a doubly linked list. In order for a class to be stored in an STL container, it must have a default constructor, the class must be assignable, less than comparable and equality comparable.

Since we are storing class objects and we are not using defined built-in C++ types we have therefore included the following:

• To make this example more complete, a copy constructor has been included although the compiler will generate a member-wise one automatically if needed. This has the same functionality as the assignment operator (=).
• The assignment (=) operator must be specified so that sort routines can assign a new order to the members of the list.
• The "less than" (<) operator must be specified so that sort routines can determine if one class instance is "less than" another.
• The "equals to" (==) operator must be specified so that sort routines can determine if one class instance is "equals to" another.

Output:

Print x:
7 5 5 3 

Print x, y, z:
7 2 4.2355
5 2 4.2355
5 2 3.2355
3 7 7.2355

Sorted: 
3 7 7.2355
5 2 3.2355
5 2 4.2355
7 2 4.2355

Iterate in Reverse: 
7 2 4.2355
5 2 4.2355
5 2 3.2355
3 7 7.2355

Remove where x=5: 
3 7 7.2355
7 2 4.2355

---

List Links:

• YoLinux.com GDB tutorial on dereferencing lists and STL containers
• SGI: list - Detail of all "list" member functions and operators available.
• Boost ptr_list and STL list of pointers - YoLinux Tutorial
• Also see Boost ptr_list - used to hold list of pointers.

Function	vector	list	deques
constructor	yes	yes	yes
destructor	yes	yes	yes
empty()	yes	yes	yes
size()	yes	yes	yes
max_size()	yes	yes	yes
resize()	yes	yes	yes
capacity()	yes	no	no
reserve()	yes	no	no
erase()	yes	yes	yes
clear()	yes	yes	yes
operator=	yes	yes	yes
operator<	yes	yes	no
operator==	yes	yes	no
operator[]	yes	no	yes
at()	yes	no	yes
front()	yes	yes	yes
back()	yes	yes	yes
push_back()	yes	yes	yes
pop_back()	yes	yes	yes
assign()	yes	yes	yes
insert()	yes	yes	yes
swap()	yes	yes	yes
push_front()	no	yes	yes
pop_front()	no	yes	yes
merge()	no	yes	no
remove()	no	yes	no
remove_if()	no	yes	no
reverse()	no	yes	no
sort()	no	yes	no
splice()	no	yes	no
unique()	no	yes	no

• GNU String class - YoLinux Tutorial
• Boost pointer container library - containter libraries (vectors,lists,maps,...) to hold pointers.
• An old fashioned linked list with pointers (old homework problem)
• GTK API:
  • Singly linked list API
  • Doubly linked list API

Software and Documentation Available From:

• http://www.sgi.com/tech/stl/ - STL home page

	The C++ Standard Library: A Tutorial and Reference Nicolai M. Josuttis ISBN #0201379260, Addison Wesley Longman This book is the only book I have seen which covers string classes as implemented by current Linux distributions. It also offers a fairly complete coverage of the C++ Standard Template Library (STL). Good reference book.
	STL for C++ programmers Leen Ammeraal ISBN #0 471 97181 2, John Wiley & Sons Ltd. Short book which teaches C++ Standard Template Library (STL) by example. Not as great as a reference but is the best at introducing all the concepts necessary to grasp STL completely and good if you want to learn STL quickly. This book is easy to read and follow.
	Data Structures with C++ Using STL William Ford, Willaim Topp ISBN #0130858501, Prentice Hall
	STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library David R. Musser, Gillmer J. Derge, Atul Saini ISBN #0201379236, Addison-Wesley Publications
	The C++ Templates: The complete guide. David Vandevoorde, Nicolai Josuttis ISBN #0201734842, Addison Wesley Pub Co. Covers complex use of C++ Templates.
	C++ How to Program by Harvey M. Deitel, Paul J. Deitel ISBN #0131857576, Prentice Hall Fifth edition. The first edition of this book (and Professor Sheely at UTA) taught me to program C++. It is complete and covers all the nuances of the C++ language. It also has good code examples. Good for both learning and reference.