The basics of programming in c++ for beginners

Algorithms. STL (part 10)

STL containers would be a beautiful fiction quite far from practical use (as it was in the first years of existence of STL), if not the following fact: because of the single overall nature of container basic algorithms, of interest in practice, It can be implemented in a generalized form, applicable to any types of containers.

Algorithms - is the bulk and the most demanded part of the library. Provided so many algorithms, that for a detailed description of all of them and not enough bulk book. Below we completely conditionally We divide them into groups and call by name (and also not all), and only for certain use cases construct.

for_each() The most commonly used algorithm - is for_each(): implementation of actions for the groups of elements (may all) container. The following shows a few examples of the algorithm for_each() for an array and vector, likewise, this algorithm can be used with any container STL:

the stl algorithms, find(), count(), count_if(), search(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), equal()

Note: strings 3 It shows the operation of the new (introduced C ++ 11 standard) design for( auto &x : …), which has a similar effect assignment and can be applied to arrays and containers (in-operator function output vector in the flow shown such an option). This construction, generally speaking, It is not part of a library or algorithms STL, but it has the same effect, that algorithm for_each(): apply consistently to all elements of the collection.  

This example shows the basic organization of logic all algorithms: a specified range (not necessarily to the entire collection), limited iterator start and end (often indicates the first 2 options) applied alternately function, functor, Or predicate (function, returns a result logixchesky, allowing for the selection of any ground).

find() Next algorithm significance - it find(). How intuitive behalf of, a search for an element in the collection. Note, many containers have method find(), which is an object to be called as obj.find(…), while algorithm It will be called as find( obj:iteator, … ).

Properly, it is not one, this algorithm, but a whole group of their extensive, which can be combined on the basis of, what are they selected elements of a collection on some grounds, condition, predicate: find(), find_if(), find_if_not(), find_first_of(), find_end(), adjacent_find(). In the same group, with some stretch, can be attributed count(), count_if(), search(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), equal() and etc.

Another conventional group - algorithms, in some way "who shuffle" collection, permute elements in places, changing values: fill(), replace_copy(), reverse(), rotate(), rotate_copy(), shuffle(), random_shuffle(), transform(), replace(), replace_if() and etc.

More artist - this algorithm works with 2 collections, toDrawing and moving content (moreover, perhaps, between the different types of collections, for example, vector<> in set<>): copy(), copy_if(), move(), swap_ranges(), remove_copy(), remove_copy_if(), merge(), set_intersection(), set_difference() and etc.

And, finally, very special group of algorithms is associated with a variety of sortings elements within the collection: sort(), stable_sort(), is_sorted(), is_sorted_until() and etc. This interesting group of us aside, for separate detailed consideration.

With such an abundance of implemented algorithms, and the number of which increases with time library, and that, that most of them do not really nowhere described in the literature, the question naturally arises: how to understand all this diversity? These difficulties are removed so that:

  • All STL objects (containers, algorithms) described in syntax patterns (template). Therefore, their descriptions necessarily You should be included in the compiled code as part of their header files (header files).

  • Go to the default directory </usr/include/c++> and find the header files of the form files stl_algo * - There you will find all functions prototypes algorithms. Furthermore, there each prototype is preceded by a thorough comment, explaining the purpose of the algorithm, and explains the call options.

  • Consider the sample code, using some BASICх STL algorithms - a lot of them in the network. By analogy elementary and simply reproduce the behavior all the other algorithms.

Note: This is due to the fact, that the library of template classes are defined in terms of template, about syntax errors are a compilation). verbose, for tens of strings of messages and b). awfully vague to find bugs. This is the flip side of such a powerful mechanism as the template, and this should be ready.

As I mentioned above, case studies will remove a lot of questions, and therefore proceed to the code … Now watch carefully for hands (STL is a set of algorithms, that every comment – beyond a reasonable presentation of the volume, but they all work like one another):

Here containers used for char (as compact, but the most unpleasant work), over which run a variety of algorithms for almost all the designated groups:

the stl algorithms, find(), count(), count_if(), search(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), equal()

4 thoughts on “Algorithms. STL (part 10)


  1. if (color[g[v][i]] == 0)
    {
    a = make_pair(v, g[v][i]);
    b = make_pair(g[v][i], v);
    for (int j = 0; j < res.size(); j++)
    {
    if (res[j] == a || res[j] == b)
    k = false;
    }
    if (k)
    res.push_back(make_pair(v, g[v][i]));
    p[g[v][i]] = v;
    f = false;
    dfs(g, color, p, g[v][i], res);
    }

  2. //random_shuffle(suv.begin(), suv.end()); //The std::random_shuffle() function is deprecated, replaced by std::shuffle().

    change to
    srand(time(NULL));
    shuffle(suv.begin(), suv.end(), std::default_random_engine());

Leave a Reply

Your email address will not be published. Required fields are marked *