B. Stroustrup - The C++ Programming Language (794319), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

Thus, a list iterator might be a pointer to a link:iterator:plist:elements:linkPlinkilinkelinkt...What is common for all iterators is their semantics and the naming of their operations. For example, applying ++ to any iterator yields an iterator that refers to the next element. Similarly, ∗ yieldsthe element to which the iterator refers. In fact, any object that obeys a few simple rules like theseis an iterator (§33.1.4). Furthermore, users rarely need to know the type of a specific iterator; eachcontainer ‘‘knows’’ its iterator types and makes them available under the conventional names iterator and const_iterator.

For example, list<Entry>::iterator is the general iterator type for list<Entry>.We rarely have to worry about the details of how that type is defined.4.5.3 Stream IteratorsIterators are a general and useful concept for dealing with sequences of elements in containers.However, containers are not the only place where we find sequences of elements. For example, aninput stream produces a sequence of values, and we write a sequence of values to an output stream.Consequently, the notion of iterators can be usefully applied to input and output.To make an ostream_iterator, we need to specify which stream will be used and the type ofobjects written to it.

For example:Section 4.5.3Stream Iteratorsostream_iterator<string> oo {cout};107// write strings to coutThe effect of assigning to ∗oo is to write the assigned value to cout. For example:int main(){∗oo = "Hello, ";++oo;∗oo = "world!\n";}// meaning cout<<"Hello, "// meaning cout<<"world!\n"This is yet another way of writing the canonical message to standard output. The ++oo is done tomimic writing into an array through a pointer.Similarly, an istream_iterator is something that allows us to treat an input stream as a read-onlycontainer.

Again, we must specify the stream to be used and the type of values expected:istream_iterator<string> ii {cin};Input iterators are used in pairs representing a sequence, so we must provide anindicate the end of input. This is the default istream_iterator:istream_iteratortoistream_iterator<string> eos {};Typically, istream_iterators and ostream_iterators are not used directly. Instead, they are provided asarguments to algorithms. For example, we can write a simple program to read a file, sort the wordsread, eliminate duplicates, and write the result to another file:int main(){string from, to;cin >> from >> to;// get source and target file namesifstream is {from};istream_iterator<string> ii {is};istream_iterator<string> eos {};// input stream for file "from"// input iterator for stream// input sentinelofstream os{to};ostream_iterator<string> oo {os,"\n"};// output stream for file "to"// output iterator for streamvector<string> b {ii,eos};sort(b.begin(),b.end());// b is a vector initialized from input [ii:eos)// sor t the bufferunique_copy(b.begin(),b.end(),oo);// copy buffer to output, discard replicated valuesreturn !is.eof() || !os;// return error state (§2.2.1, §38.3)}An ifstream is an istream that can be attached to a file, and an ofstream is an ostream that can beattached to a file.

The ostream_iterator’s second argument is used to delimit output values.Actually, this program is longer than it needs to be. We read the strings into a vector, then wesort() them, and then we write them out, eliminating duplicates. A more elegant solution is not to108A Tour of C++: Containers and AlgorithmsChapter 4store duplicates at all. This can be done by keeping the strings in a set, which does not keep duplicates and keeps its elements in order (§31.4.3). That way, we could replace the two lines using avector with one using a set and replace unique_copy() with the simpler copy():set<string> b {ii,eos};copy(b.begin(),b.end(),oo);// collect strings from input// copy buffer to outputWe used the names ii, eos, and oo only once, so we could further reduce the size of the program:int main(){string from, to;cin >> from >> to;ifstream is {from};ofstream os {to};// get source and target file names// input stream for file "from"// output stream for file "to"set<string> b {istream_iterator<string>{is},istream_iterator<string>{}}; // read inputcopy(b.begin(),b.end(),ostream_iterator<string>{os,"\n"});// copy to outputreturn !is.eof() || !os;// return error state (§2.2.1, §38.3)}It is a matter of taste and experience whether or not this last simplification improves readability.4.5.4 PredicatesIn the examples above, the algorithms have simply ‘‘built in’’ the action to be done for each element of a sequence.

However, we often want to make that action a parameter to the algorithm. Forexample, the find algorithm (§32.4) provides a convenient way of looking for a specific value. Amore general variant looks for an element that fulfills a specified requirement, a predicate (§3.4.2).For example, we might want to search a map for the first value larger than 42. A map allows us toaccess its elements as a sequence of (key,value) pairs, so we can search a map<string,int>’s sequencefor a pair<const string,int> where the int is greater than 42:void f(map<string,int>& m){auto p = find_if(m.begin(),m.end(),Greater_than{42});// ...}Here, Greater_than is a function object (§3.4.3) holding the value (42) to be compared against:struct Greater_than {int val;Greater_than(int v) : val{v} { }bool operator()(const pair<string,int>& r) { return r.second>val; }};Alternatively, we could use a lambda expression (§3.4.3):int cxx = count_if(m.begin(), m.end(), [](const pair<string,int>& r) { return r.second>42; });Section 4.5.4Predicates1094.5.5 Algorithm OverviewA general definition of an algorithm is ‘‘a finite set of rules which gives a sequence of operationsfor solving a specific set of problems [and] has five important features: Finiteness ...

Definiteness ...Input ... Output ... Effectiveness’’ [Knuth,1968,§1.1]. In the context of the C++ standard library, analgorithm is a function template operating on sequences of elements.The standard library provides dozens of algorithms. The algorithms are defined in namespacestd and presented in the <algorithm> header. These standard-library algorithms all take sequencesas inputs (§4.5). A half-open sequence from b to e is referred to as [b:e). Here are a few I havefound particularly useful:Selected Standard Algorithmsp=find(b,e,x)p=find_if(b,e,f)n=count(b,e,x)n=count_if(b,e,f)replace(b,e,v,v2)replace_if(b,e,f,v2)p=copy(b,e,out)p=copy_if(b,e,out,f)p=unique_copy(b,e,out)sort(b,e)sort(b,e,f)(p1,p2)=equal_range(b,e,v)p=merge(b,e,b2,e2,out)is the first p in [b:e) so that ∗p==xis the first p in [b:e) so that f(∗p)==trueis the number of elements ∗q in [b:e) so that ∗q==xis the number of elements ∗q in [b:e) so that f(∗q,x)Replace elements ∗q in [b:e) so that ∗q==v by v2Replace elements ∗q in [b:e) so that f(∗q) by v2Copy [b:e) to [out:p)Copy elements ∗q from [b:e) so that f(∗q) to [out:p)Copy [b:e) to [out:p); don’t copy adjacent duplicatesSort elements of [b:e) using < as the sorting criterionSort elements of [b:e) using f as the sorting criterion[p1:p2) is the subsequence of the sorted sequence [b:e)with the value v; basically a binary search for vMerge two sorted sequences [b:e) and [b2:e2) into [out:p)ppnnThese algorithms, and many more (see Chapter 32), can be applied to elements of containers,strings, and built-in arrays.4.5.6 Container AlgorithmsA sequence is defined by a pair of iterators [begin:end).

This is general and flexible, but most often,we apply an algorithm to a sequence that is the contents of a container. For example:sort(v.begin(),v.end());Why don’t we just say sort(v)? We can easily provide that shorthand:namespace Estd {using namespace std;template<class C>void sort(C& c){sort(c.begin(),c.end());}110A Tour of C++: Containers and AlgorithmsChapter 4template<class C, class Pred>void sort(C& c, Pred p){sort(c.begin(),c.end(),p);}// ...}I put the container versions of sort() (and other algorithms) into their own namespace(‘‘extended std’’) to avoid interfering with other programmers’ uses of namespace std.4.6 Advice[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17]Don’t reinvent the wheel; use libraries; §4.1.When you have a choice, prefer the standard library over other libraries; §4.1.Do not think that the standard library is ideal for everything; §4.1.Remember to #include the headers for the facilities you use; §4.1.2.Remember that standard-library facilities are defined in namespace std; §4.1.2.Prefer strings over C-style strings (a char∗; §2.2.5); §4.2, §4.3.2.iostreams are type sensitive, type-safe, and extensible; §4.3.Prefer vector<T>, map<K,T>, and unordered_map<K,T> over T[]; §4.4.Know your standard containers and their tradeoffs; §4.4.Use vector as your default container; §4.4.1.Prefer compact data structures; §4.4.1.1.If in doubt, use a range-checked vector (such as Vec); §4.4.1.2.Use push_back() or back_inserter() to add elements to a container; §4.4.1, §4.5.Use push_back() on a vector rather than realloc() on an array; §4.5.Catch common exceptions in main(); §4.4.1.2.Know your standard algorithms and prefer them over handwritten loops; §4.5.5.If iterator use gets tedious, define container algorithms; §4.5.6.Estd5A Tour of C++: Concurrency and UtilitiesWhen you wish to instruct,be brief.– Cicero•••••••IntroductionResource Managementunique_ptr and shared_ptrConcurrencyTasks and threads; Passing Arguments; Returning Results; Sharing Data; CommunicatingTasksSmall Utility ComponentsTime; Type Functions; pair and tupleRegular ExpressionsMathMathematical Functions and Algorithms; Complex Numbers; Random Numbers; VectorArithmetic; Numeric LimitsAdvice5.1 IntroductionFrom an end-user’s perspective, the ideal standard library would provide components directly supporting essentially every need.

Характеристики

Список файлов книги