Overview Of The Standard Template Library (STL)

---

Writing generic code using templates can be fun, but, it is not always easy to write truly generic code. Planning for every contingency requires time, effort, and lots of thought. Here is where the C++ Standard Template Library (STL) can be a huge help. Before sitting down to write a class or function template, take time to explore the STL. It provides lots of functionality and many smart people have contributed to both its functionality and robustness over the years. This section will introduce you to a small portion of the STL. What you have learned in this chapter about function and class templates will make the following material easily understood. To learn more about the STL I recommend reading one of the excellent references listed at the end of this chapter.

The Standard Template Library provides functionality to you in three primary forms: containers, iterators, and algorithms. STL components can be used in your programs by including the necessary header files. The number and names of these header files may vary depending on the age of your compiler. Modern compilers conforming to the C++ standard will have the following STL header files:

<algorithm>	<deque>	<functional>	<iterator>	<vector>
<list>	<map>	<memory>	<numeric>
<queue>	<set>	<stack>	<utility>

Containers and Container Adapters

Containers are STL components that manage a sequence of elements. The STL provides the container components listed in table 15-1:

Table 15-1: STL Containers

Container Class	Header File	Container Type	Comment
deque	<deque>	non-associative	Double ended queue. Elements can be added and removed from either end.
list	<list>	non-associative	Stores elements in a doubly linked list. Provides quick insertion but each element must be sequentially accessed.
map	<map>	associative	Stores elements in an ordered binary tree. Does not allow adjacent elements to have keys with equivalent ordering. Stores elements of type pair<const key, T>. Only the const key participates in the ordering.
multimap	<map>	associative	Stores elements in an ordered binary tree. Allows adjacent elements to have keys with equivalent ordering Stores elements of type pair<const key, T>. Only the const key participates in the ordering.
set	<set>	associative	Stores elements in an ordered binary tree. Does not allow adjacent elements to have keys with equivalent ordering. Stores elements of type pair<const key, T>. Both the const key and T values participate in the ordering.
multiset	<set>	associative	Stores elements in an ordered binary tree. Allows adjacent elements to have keys with equivalent ordering. Stores elements of type pair<const key, T>. Both the const key and T values participate in the ordering.
vector	<vector>	non-associative	Stores elements as an array of contiguous elements.

The STL also provides the container adapters listed in table 15-2. A container adapter uses one of the container components listed in table 15-1 to do their dirty work.

Table 15-2: STL Container Adapters

Container Adapter	Header File	Comments
stack	<stack>	Inserts and removes elements in last-in/first out (LIFO) sequence. You specify what STL component will actually be used to store stack elements.
queue	<queue>	Inserts and removes elements in first-in/first-out (FIFO) sequence. You specify what STL component will actually be used to store queue elements.
priority_queue	<queue>	Removes elements based on their priority. You specify what STL component will actually be used to store priority_queue elements.

Iterators

Iterators provide a mechanism to uniformly manipulate elements held in a container component regardless of the container type. Iterators are closely related to pointers, so, if you understand how to use pointers then you will catch- on to the purpose of iterators quickly.

It is truly beyond the scope of this book to provide a detailed discussion of iterators. If you are writing template code you can define iterators that operate properly in the context of your design. If you are just using existing STL components to enhance your programs then an understanding of how to gain access to an iterator and use it to manipulate container-stored elements will take you far.

To give you some idea as to what iterators are consider the issue of manipulating an array of objects as shown in example 15.12.

Listing 15.12: main.cpp

  1  #include <iostream>  2  using namespace std;   3  4  int main(){  5      char message[] = "Hello World!";  6      char* cptr;  7      int message_length = sizeof(message);  8  9      for(int i = 0; i < message_length; i++){ 10          cout<<message[i]; 11      } 12 13      cout<<endl; 14 15      for(cptr = message; cptr != (message + message_length); cptr++){ 16          cout<<*cptr; 17  } 18 19      return 0; 20  }

On line 5 a character array named message is declared and initialized to contain the string 'Hello World!'. A char pointer is declared on line 6 named cptr, and on line 7 an integer variable named message_length is declared and initialized to the value of the size of the message array.

The for statement beginning on line 9 interates over the contents of the message array in the idiomatic way you have seen throughout this text. It results in the message 'Hello World' being printed to the console.

The for statement on line 15 does the same thing only it utilizes a pointer instead of an index value to iterate over the array. In the initialization section of the for statement the character pointer cptr is initialized to point to first character of the message array. During the iteration, the value of cptr is compared to the value of the address one element past the length of the message array. Using address arithmetic the value of cptr is incremented during each iteration. In this example, the character pointer cptr is used as an iterator.

Container components provide the iterators necessary to manipulate their elements. Container components also provide several member functions that simplify the use of iterators compared to the code shown in example 15.12.

Algorithms

In addition to container components and iterators, the STL provides algorithm function templates you can use to further manipulate container elements. Algorithm function templates rely heavily on iterators to provide their functionality. Table 15-3 provides a list of the different algorithms provided by the STL. For a detailed discussion of each I recommend consulting one of the STL references listed at the end of this chapter.

Table 15-3: STL Algorithm Function Templates

adjacent_find	find	lexicographical_compare	nth_element	remove_copy_if	search	swap_ranges
binary_search	find_end	lower_bound	partial_sort	remove_if	search_n	transform
copy	find_first_of	make_heap	partial_sort_copy	replace	set_difference	unique
copy_backward	find_if	max	partition	replace_copy	set_symmetric_difference	unique_copy
count	for_each	max_element	pop_heap	replace_copy_if	set_union	upper_bound
count_if	generate	merge	prev_permutation	replace_if	sort
equal	generate_n	min	push_heap	reverse	sort_heap
equal_range	includes	min_element	random_shuffle	reverse_copy	stable_partition
fill	inplace_merge	mismatch	remove	rotate	stable_sort
fill_n	inter_swap	next_permutation	remove_copy	rotate_copy	swap

Note that it is not necessary to understand containers to utilize the algorithm function templates, however, an understanding of iterators is required.

Quick Review

The C++ standard template library provides containers, iterators, and algorithms for use in your programs. Containers are components that manage a set of elements. Container adapters rely on containers to implement their functionality. The type of container used by a container adapter is left to the choice of the programmer.

Iterators provide a mechanism to manipulate the elements managed by a container. Algorithms make extensive use of iterators to provide you with additional alternatives to manipulate container elements.

---