|
Real Power of STL Revealed Part I As mentioned before, STL contains large set of algorithms to be used with containers and other data types. Full description of STL algorithms you can get with your C++ compiler or from literature. Here we will concentrate on most often used ones. Let's start with the sort. // Sort vL1 is ascending
and descending order. What the heck is strangely looking less<long> Function object is an object which is constructed from the class with operator () defined or overloaded. Function objects are really essential part of STL since most STL algorithms use function objects. Function objects may be unary (with one argument) or binary (with two arguments). less is actually a class with template member function-operator "()" which takes two arguments and returns bool. You can consider third argument of sort something like less myCompareObject; ... bool returnValue = myCompareObject(arg1, arg2)...Parameter within "<>" tells compiler that less will be used with long data type. For custom data-types, programmers need to define two operators: "<" and "==". The rest of comparison operators can be derived from these two (for example, if a is not less than b and a is not equal to b it means that a is greater than b). Also, you can define your own comparison classes for creating function objects. STL Code - Sample of Real STL Power Let's construct class for manipulating spreadsheet's column and row labels. Spreadsheet's label represents pair of values: character - column number and integer - row number (a1, a2, a3, ..., b1, b2, b3, ..., etc.). This class will not serve any useful purpose except sample usage of STL containers and algorithms. You can view or download source code, as well as output in text format. First of all, we need to declare pair type - column&row label, vector type of labels, and associated iterator type. STL template class pair allows to construct data which consist of two values, which can be accessed with first and second data members respectively. //
Spreadsheet's column/row label pair type. I believe it is a good idea to add suffix to custom derivative types which show their nature. For example, pair types would have suffix PairType, vector types - VectType, iterator types - IterType, etc. (structures will not have custom suffix, however). Just consider above type definitions if they do not have suffix. Sample usage of STL algorithms will be shown inside main function. int
main(void)
What we really need is to display what is going on with our data, right? Of course, we can write function which loops through container and prints each item to standard console, but we rather will go STL way: we will use algorithm for_each(), which applies specified function to each item of input container within range of specified iterators. Like many other STL algorithms, for_each() uses function object to perform task. for_each(splv.begin(), splv.end(), SpShLab_Cout()); Class SpShLab_Cout() is shown below. struct
SpShLab_Cout
}; If you take a look at declaration of spreadsheet's label vector, you can notice that we used constructor to fill vector with initial values (just to avoid garbage values). It is possible to use STL fill() for the same purpose. //
*** Here is the result of fill: STL fill() test: b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 However, did you have seen spreadsheet whose all columns and rows had the same label? I am not. Sure, it is possible to use two nested loops to number columns and rows, but we will do the same with STL generate() algorithm, which fills input container within range of specified iterators with the value generated by supplied function object. // *** Class used in generate() is shown below. struct SpShLab_GenColsAndRowsNo /** Columns and rows number generator (a0, a1, ..., b1, b2, ...). */ {
}; Result of generate: STL generate() test: a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b3 c3 d3 e3 a4 b4 c4 d4 e4 Effect of algorithms which will be used after will be more visual if items within vector are not in particular order. STL random_shuffle() will disorder items using default random number generating function. // *** Result of random_shuffle: STL random_shuffle() test: a3 e1 c2 c3 e4 c1 a4 e2 d3 a1 a2 e3 b3 b2 b1 c4 d1 d4 b4 d2 Then, in order to use other STL algorithms, certain comparison classes required. In fact, we can directly use some binary predicates like less or greater with our column&row pair type, because of SpSheetLabPairType consist of standard types (character and integer), and therefore, all comparison operators are available by default. However, this sample is intended to show different approaches of construction of STL code, so we will forget about this possibility for some time. Let's define comparison classes "Less" and "Greater" for comparison spreadsheet's labels by column and row numbers separately. struct CmpByColNo_Less: public
/** Comparison class less (by column#). */ { bool operator()(const SpSheetLabPairType& lab1, const SpSheetLabPairType& lab2)
}; struct CmpByColNo_Greater: public
/** Comparison class greater (by column#). */ { bool operator()(const SpSheetLabPairType& lab1, const SpSheetLabPairType& lab2)
}; struct CmpByRowNo_Less: public
/** Comparison class less (by row#). */ { bool operator()(const SpSheetLabPairType& lab1, const SpSheetLabPairType& lab2)
}; struct CmpByRowNo_Greater: public
/** Comparison class greater (by row#). */ { bool operator()(const SpSheetLabPairType& lab1, const SpSheetLabPairType& lab2)
}; Now we can perform various sort test. // *** Result: STL sort() test (ascending order by column No) : a3 a4 a1 a2 b3 b2 b1 b4 c2 c3 c1 c4 d3 d1 d4 d2 e4 e1 e2 e3 // --- Result: STL sort() test (descending order by column No) : e4 e1 e2 e3 d3 d1 d4 d2 c2 c3 c1 c4 b3 b2 b1 b4 a3 a4 a1 a2 Suppose we need to sort our container by both column and row numbers with four comparison classes listed above. Let's make two consecutive calls of sort. random_shuffle(splv.begin(), splv.end()); Result: STL sort() test (ascending order by column and row No) : a1 b1 c1 d1 e1 b2 c2 a2 d2 e2 b3 d3 a3 c3 e3 a4 c4 b4 e4 d4 Guess why sort order by column number is broken? Its because STL sort do not preserve relative order of equal items. We need to use stable_sort in order to achieve desirable result. random_shuffle(splv.begin(), splv.end()); Result: STL stable_sort() test (ascending order by column and row No) : a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b3 c3 d3 e3 a4 b4 c4 d4 e4 As mentioned before, we can apply binary predicates directly to our pair type SpSheetLabPairType (I hope you remember why). random_shuffle(splv.begin(), splv.end()); Result: STL sort() using binary predicate "less" to the entire pair (ascending order by column and row No) : a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4 e1 e2 e3 e4 You should understand why consecutive calls of sort() and stable_sort() produce different result from the last sort() which uses function object created with binary predicate. Some STL algorithms are not so easy to use for beginners because the way they work and their result are not so obvious. One of them is unique(), which, as name suggest, used to remove duplicates from the container. Let's go step by step and learn how unique() works. First, we need to add few duplicate items. // *** //
Add duplicate items. Result (duplicate items marked with red): Let's add duplicate items (a2, c2, d3): a1 a2 c2 d3 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4 e1 e2 e3 e4 Very important step: unique() should be performed on SORTED container in order to eliminate ALL, not just currently CONSECUTIVE duplicates. sort(splv.begin(), splv.end(), less<SpSheetLabPairType>()); Result (duplicate items marked with red): Sort container before applying unique: a1 a2 a2 a3 a4 b1 b2 b3 b4 c1 c2 c2 c3 c4 d1 d2 d3 d3 d4 e1 e2 e3 e4 Now we are ready to apply unique(): SpSheetLabIterType toBeDeleted; toBeDeleted = unique(splv.begin(), splv.end(), equal_to<SpSheetLabPairType>()); Result of STL unique: a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4 e1 e2 e3 e4 e2 e3 e4 What's wrong? Size of container seems to be the same as before. Do not worry, everything is OK. STL unique() DO NOT erases items! Items to be deleted are located starting from iterator returned by unique(). All items within range of this iterator and container end are garbage (marked with red on the output shown above). We need to use erase() to clean up container completely. splv.erase(toBeDeleted, splv.end()); Final result: a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4 e1 e2 e3 e4 Well, all shown examples are fairly simple because of they use custom types directly derived from standard types. What if data types are more complex than pair of character and integer? |