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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <iostream> #include <vector> #include <algorithm> using namespace std; inline ostream& operator <<( ostream& out, const vector< unsigned > & obj ) { cout << "< "; for( auto& p: obj ) cout << p << " "; return out << ">"; } void pow2( unsigned& i ) { i *= i; } int main( void ) { const int examples = 4; for( int i = 0; i < examples; i++ ) { unsigned ai[] = { 1, 2, 3, 4 , 5, 6, 7, 8, 9 }, ni = sizeof( ai ) / sizeof( ai[ 0 ] ); vector< unsigned > vi( ai, ai + ni ); cout << vi; switch( i ) { case 0: for_each( vi.begin(), vi.end(), pow2 ); cout << " => " << vi << endl; break; case 1: for_each( ai, ai + ni, pow2 ); cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break; case 2: for( auto& i : ai ) pow2( i ); cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break; case 3: for_each( vi.begin() + 2, vi.end() - 2, pow2 ); cout << " => " << vi << endl; break; } } } |
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):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <iostream> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> using namespace std; inline ostream& operator <<( ostream& out, const vector<char>& obj ) { for( auto p: obj ) cout << p; return out; } int main( void ) { char s[] = "The Life and Strange Surprizing Adventures of Robinson \ Crusoe, Of York, Mariner: Who lived Eight and Twenty \ Years, all alone in an un-inhabited Island on the \ Coast of America, near the Mouth of the Great River of \ Oroonoque; Having been cast on Shore by Shipwreck, \ wherein all the Men perished but himself. With \ An Account how he was at last as strangely deliver'd \ by Pyrates"; // название книги vector<string> vs = { "Supercalifragilisticexpialidocious", // cамое длинное слово на английском языке "Pneumonoultramicroscopicsilicovolcanoconiosis" // самый длинный термин на английском языке }; // copy & find : vector<char> v1( strlen( s ) ); copy( s, s + v1.size(), v1.begin() ); int nb = 0; for( auto is = find( v1.begin(), v1.end(), ' ' ); is != v1.end(); is = find( ++is, v1.end(), ' ' ) ) nb++; cout << "в фразе пробелов " << nb << " (" << nb + 1 << " слов)" << endl; // min & max : auto mm = minmax_element( v1.begin(), v1.end() ); cout << "диапазон символов: '" << *mm.first << "' ... '" << *mm.second << "'" << endl; // fill & reverse & rotate & shuffle : vector<char> suv( vs[ 0 ].size() ); copy( vs[ 0 ].begin(), vs[ 0 ].end(), suv.begin() ); cout << suv << endl; random_shuffle( suv.begin(), suv.end() ); cout << suv << endl; reverse( suv.begin(), suv.end() ); cout << suv << endl; rotate( suv.begin(), suv.begin() + suv.size() / 2, suv.end() ); cout << suv << endl; // set_intersection & set_difference set< char > sus, pns; for( char s: vector<char>( vs[ 0 ].begin(), vs[ 0 ].end() ) ) sus.insert( s ); for( char s: vector<char>( vs[ 1 ].begin(), vs[ 1 ].end() ) ) pns.insert( s ); vector<char> outi( 100 ), outd( 100 ); auto ret = set_intersection( sus.begin(), sus.end(), pns.begin(), pns.end(), outi.begin() ); cout << "общих литер " << ( ret - outi.begin() ) << " : " << outi << endl; ret = set_difference( sus.begin(), sus.end(), pns.begin(), pns.end(), outd.begin() ); cout << "уникальных литер " << ( ret - outd.begin() ) << " : " << outd << endl; } |
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:
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);
}
What was it, dad? ;-)
//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());