Kĩ thuật lập trình - Chapter 21: The STL (maps and algorithms)

Chapter 21The STL(maps and algorithms)Bjarne Stroustrup www.stroustrup.com/ProgrammingAbstractThis talk presents the idea of STL algorithms and introduces map as an example of a container.*Stroustrup/Programming Nov'13OverviewCommon tasks and idealsContainers, algorithms, and iteratorsThe simplest algorithm: find()Parameterization of algorithmsfind_if() and function objectsSequence containersvector and listAlgorithms and parameterization revisitedAssociative containersmap, setStandard algorithmscopy, sort, Input iterators and output iteratorsList of useful facilitiesHeaders, algorithms, containers, function objects*Stroustrup/Programming Nov'13Basic modelA pair of iterators defines a sequenceThe beginning (points to the first element – if any)The end (points to the one-beyond-the-last element)*begin:end:An iterator is a type that supports the “iterator operations” of++ Point to the next element* Get the element value== Does this iterator point to the same element as that iterator?Some iterators support more operations (e.g., --, +, and [ ])Stroustrup/Programming Nov'13Accumulate (sum the elements of a sequence)templateT accumulate(In first, In last, T init){ while (first!=last) { init = init + *first; ++first; } return init;}*1432v:int sum = accumulate(v.begin(), v.end(), 0); // sum becomes 10Stroustrup/Programming Nov'13Accumulate (sum the elements of a sequence)void f(vector& vd, int* p, int n){ double sum = accumulate(vd.begin(), vd.end(), 0.0); // add the elements of vd // note: the type of the 3rd argument, the initializer, determines the precision used int si = accumulate(p, p+n, 0); // sum the ints in an int (danger of overflow) // p+n means (roughly) &p[n] long sl = accumulate(p, p+n, long(0)); // sum the ints in a long double s2 = accumulate(p, p+n, 0.0); // sum the ints in a double // popular idiom, use the variable you want the result in as the initializer: double ss = 0; ss = accumulate(vd.begin(), vd.end(), ss); // do remember the assignment}*Stroustrup/Programming Nov'13Accumulate(generalize: process the elements of a sequence)// we don’t need to use only +, we can use any binary operation (e.g., *)// any function that “updates the init value” can be used:templateT accumulate(In first, In last, T init, BinOp op){ while (first!=last) { init = op(init, *first); // means “init op *first” ++first; } return init;}*Stroustrup/Programming Nov'13Accumulate// often, we need multiplication rather than addition:#include #include void f(list& ld){ double product = accumulate(ld.begin(), ld.end(), 1.0, multiplies()); // }// multiplies is a standard library function object for multiplying*Note: multiplies for *Note: initializer 1.0Stroustrup/Programming Nov'13Accumulate (what if the data is part of a record?)struct Record { int units; // number of units sold double unit_price; // };// let the “update the init value” function extract data from a Record element:double price(double v, const Record& r){ return v + r.unit_price * r.units;}void f(const vector& vr) { double total = accumulate(vr.begin(), vr.end(), 0.0, price); // }*Stroustrup/Programming Nov'13Accumulate (what if the data is part of a record?)struct Record { int units; // number of units sold double unit_price; // };void f(const vector& vr) { double total = accumulate(vr.begin(), vr.end(), 0.0, // use a lambda [](double v, const Record& r) { return v + r.unit_price * r.units; } ); // }// Is this clearer or less clear than the price() function?*Stroustrup/Programming Nov'13Inner producttemplateT inner_product(In first, In last, In2 first2, T init) // This is the way we multiply two vectors (yielding a scalar){ while(first!=last) { init = init + (*first) * (*first2); // multiply pairs of elements and sum ++first; ++first2; } return init;} *13243412 * * * *number of units * unit priceStroustrup/Programming Nov'13Inner product example// calculate the Dow-Jones industrial index:vector dow_price; // share price for each companydow_price.push_back(81.86); dow_price.push_back(34.69);dow_price.push_back(54.45);// vector dow_weight; // weight in index for each companydow_weight.push_back(5.8549); dow_weight.push_back(2.4808);dow_weight.push_back(3.8940);// double dj_index = inner_product( // multiply (price,weight) pairs and add dow_price.begin(), dow_price.end(), dow_weight.begin(), 0.0);*Stroustrup/Programming Nov'13Inner product example// calculate the Dow-Jones industrial index:vector dow_price = { // share price for each company 81.86, 34.69, 54.45, // };vector dow_weight = { // weight in index for each company 5.8549, 2.4808, 3.8940, // };double dj_index = inner_product( // multiply (price,weight) pairs and add dow_price.begin(), dow_price.end(), dow_weight.begin(), 0.0);*Stroustrup/Programming Nov'13Inner product (generalize!)// we can supply our own operations for combining element values with“init”:templateT inner_product(In first, In last, In2 first2, T init, BinOp op, BinOp2 op2){ while(first!=last) { init = op(init, op2(*first, *first2)); ++first; ++first2; } return init;}*Stroustrup/Programming Nov'13Map (an associative array)For a vector, you subscript using an integerFor a map, you can define the subscript to be (just about) any typeint main(){ map words; // keep (word,frequency) pairs for (string s; cin>>s; ) ++words[s]; // note: words is subscripted by a string // words[s] returns an int& // the int values are initialized to 0 for (const auto& p : words) cout words; // keep (word,frequency) pairs for (string s; cin>>s; ) ++words[s]; // note: words is subscripted by a string // words[s] returns an int& // the int values are initialized to 0 for (const auto& p : words) cout fruits;*Orange 99Plum 8Kiwi 2345Apple 7Quince 0Grape 100fruits:Key firstValue secondNode* leftNode* rightMap node:Stroustrup/Programming Nov'13Map// note the similarity to vector and listtemplate class map { // using value_type = pair; // a map deals in (Key,Value) pairs using iterator = ???; // probably a pointer to a tree node using const_iterator = ???; iterator begin(); // points to first element iterator end(); // points to one beyond the last element Value& operator[ ](const Key&); // get Value for Key; creates pair if // necessary, using Value( ) iterator find(const Key& k); // is there an entry for k? void erase(iterator p); // remove element pointed to by p pair insert(const value_type&); // insert new (Key,Value) pair // // the bool is false if insert failed};*Some implementation defined typeStroustrup/Programming Nov'13Map example (build some maps)map dow; // Dow-Jones industrial index (symbol,price) , 03/31/2004 // ["MMM"] = 81.86; dow["AA"] = 34.69;dow["MO"] = 54.45;// map dow_weight; // dow (symbol,weight)dow_weight.insert(make_pair("MMM", 5.8549)); // just to show that a Map // really does hold pairsdow_weight.insert(make_pair("AA",2.4808));dow_weight.insert(make_pair("MO",3.8940)); // and to show that notation matters// map dow_name; // dow (symbol,name)dow_name["MMM"] = "3M Co."; dow_name["AA"] = "Alcoa Inc.";dow_name["MO"] = "Altria Group Inc.";// *Stroustrup/Programming Nov'13Map example (some uses)double alcoa_price = dow["AA"]; // read values from a mapdouble boeing_price = dow["BO"];if (dow.find("INTC") != dow.end()) // look in a map for an entry cout & a, const pair& b) // extract values and multiply{ return a.second * b.second;}double dj_index = inner_product(dow.begin(), dow.end(), // all companies in index dow_weight.begin(), // their weights 0.0, // initial value plus(), // add (as usual) value_product // extract values and weights ); // and multiply; then sum*Stroustrup/Programming Nov'13Containers and “almost containers”Sequence containersvector, list, dequeAssociative containersmap, set, multimap, multiset“almost containers”array, string, stack, queue, priority_queue, bitsetNew C++11 standard containersunordered_map (a hash table), unordered_set, For anything non-trivial, consult documentationOnlineSGI, RogueWave, DinkumwareOther booksStroustrup: The C++ Programming language 4th ed. (Chapters 30-33, 40.6)Austern: Generic Programming and the STLJosuttis: The C++ Standard Library*Stroustrup/Programming Nov'13AlgorithmsAn STL-style algorithmTakes one or more sequencesUsually as pairs of iteratorsTakes one or more operationsUsually as function objectsOrdinary functions also workUsually reports “failure” by returning the end of a sequence*Stroustrup/Programming Nov'13Some useful standard algorithmsr=find(b,e,v) r points to the first occurrence of v in [b,e)r=find_if(b,e,p) r points to the first element x in [b,e) for which p(x)x=count(b,e,v) x is the number of occurrences of v in [b,e) x=count_if(b,e,p) x is the number of elements in [b,e) for which p(x)sort(b,e) sort [b,e) using Out copy(In first, In last, Out res){ while (first!=last) *res++ = *first++; // conventional shorthand for: // *res = *first; ++res; ++first return res;}void f(vector& vd, list& li){ if (vd.size() oo(cout); // assigning to *oo is to write to cout *oo = "Hello, "; // meaning cout ii(cin); // reading *ii is to read a string from cin string s1 = *ii; // meaning cin>>s1 ++ii; // “get ready for the next input operation” string s2 = *ii; // meaning cin>>s2*Stroustrup/Programming Nov'13Make a quick dictionary (using a vector)int main(){ string from, to; cin >> from >> to; // get source and target file names ifstream is(from); // open input stream ofstream os(to); // open output stream istream_iterator ii(is); // make input iterator for stream istream_iterator eos; // input sentinel (defaults to EOF) ostream_iterator oo(os,"\n"); // make output iterator for stream // append "\n" each time vector b(ii,eos); // b is a vector initialized from input sort(b.begin(),b.end()); // sort the buffer unique_copy(b.begin(),b.end(),oo); // copy buffer to output, // discard replicated values}*Stroustrup/Programming Nov'13An input file (the abstract)This lecture and the next presents the STL (the containers and algorithms part of the C++ standard library). It is an extensible framework dealing with data in a C++ program. First, I present the general ideal, then the fundamental concepts, and finally examples of containers and algorithms. The key notions of sequence and iterator used to tie containers (data) together with algorithms (processing) are presented. Function objects are used to parameterize algorithms with “policies”.*Stroustrup/Programming Nov'13Part of the output(data)(processing)(theC++First,FunctionIItSTLTheThisaalgorithmsalgorithms.anandareconcepts,containersdatadealingexamplesextensiblefinallyFrameworkfundamentalgeneralideal,inisiteratorkeylecturelibrary).nextnotionsobjectsofparameterizepartpresentpresented.presentsprogram.sequencestandardthethentietotogetherusedwith“policies”.*Stroustrup/Programming Nov'13Make a quick dictionary (using a vector)We are doing a lot of work that we don’t really needWhy store all the duplicates? (in the vector)Why sort?Why suppress all the duplicates on output?Why not justPut each word in the right place in a dictionary as we read it?In other words: use a set*Stroustrup/Programming Nov'13Make a quick dictionary (using a set)int main(){ string from, to; cin >> from >> to; // get source and target file names ifstream is(from); // make input stream ofstream os(to); // make output stream istream_iterator ii(is); // make input iterator for stream istream_iterator eos; // input sentinel (defaults to EOF) ostream_iterator oo(os,"\n"); // make output iterator for stream // append "\n" each time set b(ii,eos); // b is a set initialized from input copy(b.begin(),b.end(),oo); // copy buffer to output}// simple definition: a set is a map with no values, just keys*Stroustrup/Programming Nov'13SetA set is really an ordered balanced binary treeBy default ordered by fruits;*OrangePlumKiwiAppleQuinceGrapefruits:Key firstNode* leftNode* rightset node:Stroustrup/Programming Nov'13copy_if()// a very useful algorithm (missing from the standard library):templateOut copy_if(In first, In last, Out res, Pred p) // copy elements that fulfill the predicate{ while (first!=last) { if (p(*first)) *res++ = *first; ++first; } return res;}*Stroustrup/Programming Nov'13copy_if()void f(const vector& v) // “typical use” of predicate with data // copy all elements with a value less than 6{ vector v2(v.size()); copy_if(v.begin(), v.end(), v2.begin(), [](int x) { return xBinaryplus, minus, multiplies, divides, modulusequal_to, not_equal_to, greater, less, greater_equal, less_equal, logical_and, logical_orUnarynegatelogical_notUnary (missing, write them yourself)less_than, greater_than, less_than_or_equal, greater_than_or_equal*Stroustrup/Programming Nov'13