The C++ Standard Library Categories

By John Paul Mueller, Jeff Cogswell

The Standard Library documentation uses a formal approach that you’re going to find difficult to read and even harder to understand. The best way to begin is to break the Standard Library into smaller pieces. You can categorize the Standard Library functions in a number of ways. One of the most common approaches is to use the following categories:

Containers

Containers work just like the containers in your home — they hold something. For example, both queues and deques are kinds of containers. The Containers category doesn’t contain any functions, but it does contain a number of types including the following:

basic_string
bit_vector
bitset
char_producer
deque
hash
list
map
multimap
multiset
priority_queue
queue
rope
set
slist
stack
vector

Iterators

Iterators enumerate something. When you create a list of items, and then go through that list checking items off, you’re enumerating the list. Using iterators helps you create lists of items and manipulate them in specific ways. The kind of iterator you create is important because some iterators let you go forward only, some can go in either direction, and some can choose items at random. Each kind of iterator has its specific purpose.

The Iterators category includes a number of types. These types determine the kind of iterator you create in your code and the capabilities of that iterator. Following is a list of the iterator types:

back_insert_iterator
bidirectional_iterator
bidirectional_iterator_tag
forward_iterator
forward_iterator_tag
front_insert_iterator
input_iterator
input_iterator_tag
insert_iterator
istream_iterator
iterator_traits
ostream_iterator
output_iterator
output_iterator_tag
random_access_iterator
random_access_iterator_tag
raw_storage_iterator
reverse_bidirectional_iterator
reverse_iterator
sequence_buffer

The Standard Library also includes a number of iterator-specific functions. These functions help you perform tasks such as advance (increment) the iterator by a certain number of positions. You can also measure the distance between the beginning and end of the iterator. The following is a list of iterator functions:

advance
distance
distance_type
iterator_category
value_type

Algorithms

Algorithms perform data manipulations such as replacing, locating, or sorting information. It’s hard to create a substantial application without using one. There aren’t any types in the Algorithms category. The following is a list of algorithm functions:

accumulate
adjacent_difference
adjacent_find
advance
binary_search
copy
copy_backward
copy_n
count
count_if
distance
equal
equal_range
fill
fill_n
find
find_end
find_first_of
find_if
for_each
generate
generate_n
includes
inner_product
inplace_merge
iota
is_heap
is_sorted
iter_swap
lexicographical_compare
lexicographical_compare_3way
lower_bound
make_heap
max
max_element
merge
min
min_element
mismatch
next_permutation
nth_element
partial_sort
partial_sort_copy
partial_sum
partition
pop_heap
power
prev_permutation
push_heap
random_sample
random_sample_n
random_shuffle
remove
remove_copy
remove_copy_if
remove_if
replace
replace_copy
replace_copy_if
replace_if
reverse
reverse_copy
rotate
rotate_copy
search
search_n
set_difference
set_intersection
set_symmetric_difference
set_union
sort
sort_heap
stable_partition
stable_sort
swap
swap_ranges
transform
uninitialized_copy
uninitialized_copy_n
uninitialized_fill
uninitialized_fill_n
unique
unique_copy
upper_bound

Functors

Functors are a special class of object that acts as if it’s a function. In most cases, you call a functor by using the same syntax you use for a function, but functors possess all the good elements of objects as well, such as the ability to instantiate them at runtime.

Functors come in a number of forms. For example, a binary function functor accepts two arguments as input and provides a result as output. Functors include a number of types that determine the kind of function the code creates:

binary_compose
binary_function
binary_negate
binder1st
binder2nd
divides
equal_to
greater
greater_equal
hash
identity
less
less_equal
logical_and
logical_not
logical_or
mem_fun1_ref_t
mem_fun1_t
mem_fun_ref_t
mem_fun_t
minus
modulus
multiplies
negate
not_equal_to
plus
pointer_to_binary_function
pointer_to_unary_function
project1st
project2nd
select1st
select2nd
subtractive_rng
unary_compose
unary_function
unary_negate

Utilities

Utilities are functions and types that perform small service tasks within the Standard Library. The functions are min(), max(), and the relational operators. The types are chart_traits (the traits of characters used in other Standard Library features, such as basic_string) and pair (a pairing of two heterogeneous values).

Adaptors

Adaptors perform conversions of a sort. They make it possible to adapt one kind of data to another. In some cases, adaptors perform data conversion, such as negating numbers. The Adaptors category includes one function, ptr_fun(). In addition, the Adaptors category includes the types listed here:

back_insert_iterator
binary_compose
binary_negate
binder1st
binder2nd
front_insert_iterator
insert_iterator
mem_fun1_ref_t
mem_fun1_t
mem_fun_ref_t
mem_fun_t
pointer_to_binary_function
pointer_to_unary_function
priority_queue
queue
raw_storage_iterator
reverse_bidirectional_iterator
reverse_iterator
sequence_buffer
stack
unary_compose
unary_negate

Allocators

Allocators manage resources, normally memory. In most cases, you won’t ever need to use the members of the Allocators category. For example, you normally create new objects using the new operator. The new operator allocates memory for the object and then creates it by calling the object’s constructor.

In rare cases, such as when you want to implement a form of object pooling, you may want to separate the memory allocation process from the construction process. In this case, you call construct() to perform the actual task of constructing the object based on its class definition. The Allocators category has the following functions.

construct
destroy
get_temporary_buffer
return_temporary_buffer
uninitialized_copy
uninitialized_copy_n
uninitialized_fill
uninitialized_fill_n

The Allocators category also includes a couple of types. These types help you manage memory, and you may find more use for them than you will the functions in this category. The types are

raw_storage_iterator
temporary_buffer

Polymorphic allocators

When working with older versions of the Standard Library, allocators used as arguments to templates create problems because they’re bound by type. What this means is that a vector created using std::vector<int> is a completely different type from a vector created using std::vector<int, myalloc>, even though one is simply an extension of the other.

The myalloc part of the template simply defines the method used to allocate memory; it doesn’t actually affect the type of data managed by the template. So, in both cases, you’re created a vector to hold int data — the types are the same. The only difference is the method in which memory is allocated (the first uses standard memory allocation techniques, while the second uses a custom allocator).

Using polymorphic allocators eliminates this problem by defining an abstract base memory class, memory_resource, to use for all memory allocators. This abstract class defines the following pure virtual methods:

allocate
deallocate
is_equal()