Template Library. General concepts. Containers. Algorithms. Iterators. Functors

This topic is the beginning of the study of the STL library of the C++ language.

---

Contents

• 1. Standard Template Library. General concepts
• 2. Containers. General information. List
• 3. Algorithms. General information
• 4. Iterators. General information
• 5. Functors. General information
• Related topics

---

Search other resources:

1. Standard Template Library. General concepts

The C++ language has developed a powerful set of tools for creating a variety of programs – the Standard Template Library (STL). This library, in fact, is an integral part of the C++ language, which is a great achievement of its developers. The STL is included in the C++ standard and contains generic template classes and functions that implement a wide range of algorithms and data structures. These programming tools can be applied to almost any type of data.

There are the following main components of the STL library:

• containers
• algorithms
• iterators
• functional objects or functors.

The use and combination of these components allows programming solutions to a very wide range of programming problems.

  ⇑

2. Containers. General information. List

In programming, a container is an object that stores other objects within itself. Objects stored in containers can be both basic (primitive) types and instances of classes with the corresponding necessary functionality.

The following containers are implemented in the STL library:

• bitset – a set of bits;
• deque – bi-directional queue;
• list – linear list;
• map – associative container constructed according to the principle key:value, wherein each key corresponds to the key value of the value;
• multimap – associative container in which one value (key) corresponds to multiple values (value1, value2, …, valueN);
• multiset – set, in which one and the same element can occur several times;
• priority_queue – priority queue;
• queue – a queue;
• set – a set in which each element occurs only once;
• stack – stack;
• vector – dynamic array.

  ⇑

3. Algorithms. General information

The contents of the containers are processed using algorithms. Algorithms allow you to process containers for every taste: initialize, sort the contents of containers, transform, implement various types of search, and the like.

To access the algorithms, you need to include the appropriate library

#include <algorithm>

All algorithms are template functions. They can be applied to any type of container. Below is a list of the STL algorithms:

• adjacent_find – searches for a pair of adjacent elements that match each other;
• binary_search – performs a binary search in an ordered sequence;
• copy – copies one sequence to another;
• copy_backward – does the same as copy, only the resulting sequence is written in reverse order;
• count – counts the number of occurrences of a given element in the sequence;
• count_if – calculates the number of occurrences of an element in a sequence that meets a specified condition;
• equal – determines if the elements of the two ranges are the same;
• equal_range – returns a range that allows for the insertion of elements without disrupting the order;
• fill, fill_n – fill the range with the required values;
• find – searches for an element in a given sequence, returns the position (iterator) of the first occurrence of an element in the sequence;
• find_end – searches for the last occurrence of a subsequence contained in the specified range;
• find_first_of – searches for the first element of a subsequence that matches any element of another subsequence;
• find_if – finds the first element of a sequence that matches an element from another sequence;
• for_each – applies the specified function to the specified range of elements;
• generate, generate_n – assigns the values returned by the generator function to the elements of the range;
• include – determines if one sequence contains another;
• inplace_merge – merges two ranges;
• iter_swap – swaps the two values pointed to by the arguments;
• lexicographical_compare – performs lexicographical comparison of two sequences;
• lower_bound – defines the first element of the sequence, which is not less than the specified value;
• make_heap – based on the specified sequence, creates a “heap”;
• max – returns the maximum of two values;
• max_element – returns the position (iterator), which is set to the maximum element of the sequence;
• merge – merges two ordered sequences. The result is written to the third sequence;
• min – returns the minimum of two values;
• min_element – returns the position (iterator), which is set to the minimum element of the sequence;
• mismatch – finds the first mismatch for two given sequences;
• next_permutation – forms the next permutation of the elements of the sequence;
• nth_element – orders the sequence so that all elements that are less than the specified element are placed before this element in the sequence;
• partial_sort – performs sorting of elements in the specified range;
• partial_sort_copy – orders the elements of the sequence in the specified range, then copies the sorted elements into the resulting sequence;
• partition – orders the sequence so that all elements that match a given condition are placed before all other elements of this sequence;
• pop_heap – swaps the first and penultimate elements and rearranges the “heap”;
• prev_permutation – renders the previous permutation consisting of sequence elements;
• push_heap – pushes the element to the end of the heap;
• random_shuffle – changes the sequence in the specified range;
• remove – removes from the specified sequence elements that have a certain value;
• remove_if – removes elements from the specified sequence according to the specified predicate;
• remove_copy – copies from the specified sequence elements that have a specific value into the specified sequence;
• remove_copy_if – copies elements from the specified sequence to another area based on the specified predicate;
• replace – replaces elements of a specified range from one value to another;
• replace_if – replaces elements of a given range based on a predicate;
• replace_copy_if – copies elements of a given sequence to another area, replacing one value with another;
• replace_copy – copies elements of a given range into another sequence, replacing elements based on a given predicate with another value;
• reverse – changes the order of the sequence elements to the opposite within the specified range;
• reverse_copy – reverses the order of elements in the sequence and writes the result to another sequence;
• rotate – performs a cyclic left shift of the elements of the sequence within the specified limits;
• rotate_copy – performs a cyclic left shift of the elements of the sequence, the result is placed in another sequence;
• search – searches for a subsequence in the sequence;
• search_n – finds the n-th occurrence of the specified element in the sequence;
• set_difference — for two given sequences, creates a sequence containing mismatched elements (difference of sets);
• set_intersection – for two given sequences, creates a sequence containing matching elements (intersection of sets);
• set_symmetric_difference – creates a sequence that is the symmetric difference of two sequences;
• set_union – creates a sequence that is the union of two sequences;
• sort – orders the sequence in the specified range;
• sort_heap – orders the “heap” within the specified range;
• stable_partition – orders the sequence within the given limits so that all elements that meet a given condition precede all other elements. The breakdown of the sequence is fixed;
• stable_sort – orders the sequence within the specified limits in such a way that equal elements do not change their places;
• swap – swaps the values specified by references;
• swap_ranges – swaps the elements of the specified range;
• transform – for a given sequence, executes a function to each element of this sequence. The result is saved in a new sequence;
• unique – pulls duplicates from the specified sequence;
• unique_copy – makes a copy from the sequence, extracting duplicates from it (identical elements);
• upper_bound – finds the last element of the sequence not exceeding the specified value.

  ⇑

4. Iterators. General information

Iterators – are objects that allow you to navigate through the contents of the container. Iterators are like pointers. Iterators are an abstraction of a pointer. Using iterators, you can read and change the values of the elements of the container.

To use iterators, you need to include the iterator header

#include <iterator>

There are 5 types of iterators in C++:

• RandIter – random access iterator – writes and retrieves a value from a container. Provides random access to items in a container;
• BiTter – bi-directional iterator – writes and retrieves values. Moves back and forth;
• ForIter – forward iterator – moves forward only. Writes and retrieves values;
• InIter – input iterator – only retrieves values. Moves forward only;
• OutIter – output iterator – only writes values. Moves forward only.

The <iostream> library defines the following classes that implement iterators:

• iterator – base class for all iterators;
• iterator_traits – represents the various types defined by the iterator;
• insert_iterator – provides output iterators that insert objects into containers;
• back_insert_iterator – provides output iterators that insert objects at the end of the container;
• front_insert_iterator – provides output iterators that insert objects at the beginning of the container;
• reverse_iterator – supports reverse iterators;
• istream_iterator – supports streaming input iterators;
• istreambuf_iterator – supports streaming character input iterators;
• ostream_iterator – supports the operation of streaming output iterators;
• ostreambuf_iterator – supports the operation of streaming iterators for character output.

  ⇑

5. Functors. General information

Functors are used to provide flexible communication between iterators, containers and algorithms. A functor is a class in which the operator function operator () is implemented. Thanks to functors, a class object is represented as a function.

To use functors in a program, you need to include the functional header

#include <functional>

Functors are divided into two categories:

• binary – contain two arguments;
• unary – contain one argument.

The STL contains the following binary functors:

• plus – adds (+) two arguments;
• minus – subtracts (–) arguments;
• multplies – multiplies (*) two arguments;
• divides – divides (/) arguments;
• modulus – returns the result of operation % for two arguments;
• equal_to – compares two arguments for equality (==);
• not_equal_to – compares two arguments for inequality (!=);
• greater – determines whether the first argument is greater than the second argument (>);
• greater_equal – determines if the first argument is greater than or equal to the second argument (>=);
• less – determines if the first argument is less than the second argument (<);
• less_equal – determines if the first argument is less than or equal to the second argument (<=);
• logical_and – applies logical “AND” to arguments;
• logical_or – Applies logical “OR” to two arguments.

There are also two unary functors defined:

• logical_not – applies logical “NOT” to the argument;
• negate – changes the sign of its argument to the opposite.

  ⇑

---

Related topics

• Class template. The ‘template’ keyword. Advantages of using templates. Arguments in templates. Examples

  ⇑

---