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

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

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

For example:• begin() and end() give iterators to the first and one-beyond-the-last elements, respectively.• push_back() can be used (efficiently) to add elements to the end of a vector, forward_list, list,and other containers.• size() returns the number of elements.This notational and semantic uniformity enables programmers to provide new container types thatcan be used in a very similar manner to the standard ones. The range-checked vector, Vector(§2.3.2, §2.4.3.1), is an example of that. The uniformity of container interfaces also allows us tospecify algorithms independently of individual container types.

However, each has strengths andweaknesses. For example, subscripting and traversing a vector is cheap and easy. On the otherhand, vector elements are moved when we insert or remove elements; list has exactly the oppositeproperties. Please note that a vector is usually more efficient than a list for short sequences of smallelements (even for insert() and erase()). I recommend the standard-library vector as the default typefor sequences of elements: you need a reason to choose another.4.5 AlgorithmsA data structure, such as a list or a vector, is not very useful on its own.

To use one, we need operations for basic access such as adding and removing elements (as is provided for list and vector).Furthermore, we rarely just store objects in a container. We sort them, print them, extract subsets,remove elements, search for objects, etc. Consequently, the standard library provides the mostcommon algorithms for containers in addition to providing the most common container types. Forexample, the following sorts a vector and places a copy of each unique vector element on a list:bool operator<(const Entry& x, const Entry& y)// less than{return x.name<y.name;// order Entrys by their names}void f(vector<Entry>& vec, list<Entry>& lst){sort(vec.begin(),vec.end());unique_copy(vec.begin(),vec.end(),lst.begin());}// use < for order// don’t copy adjacent equal elementsThe standard algorithms are described in Chapter 32. They are expressed in terms of sequences ofelements.

A sequence is represented by a pair of iterators specifying the first element and the onebeyond-the-last element:Section 4.5Algorithmsiterators:begin()103end()elements:In the example, sort() sorts the sequence defined by the pair of iterators vec.begin() and vec.end() –which just happens to be all the elements of a vector. For writing (output), you need only to specifythe first element to be written.

If more than one element is written, the elements following that initial element will be overwritten. Thus, to avoid errors, lst must have at least as many elements asthere are unique values in vec.If we wanted to place the unique elements in a new container, we could have written:list<Entry> f(vector<Entry>& vec){list<Entry> res;sort(vec.begin(),vec.end());unique_copy(vec.begin(),vec.end(),back_inserter(res)); // append to resreturn res;}A back_inserter() adds elements at the end of a container, extending the container to make room forthem (§33.2.2).

Thus, the standard containers plus back_inserter()s eliminate the need to use errorprone, explicit C-style memory management using realloc() (§31.5.1). The standard-library list hasa move constructor (§3.3.2, §17.5.2) that makes returning res by value efficient (even for lists ofthousands of elements).If you find the pair-of-iterators style of code, such as sort(vec.begin(),vec.end()), tedious, you candefine container versions of the algorithms and write sort(vec) (§4.5.6).4.5.1 Use of IteratorsWhen you first encounter a container, a few iterators referring to useful elements can be obtained;begin() and end() are the best examples of this.

In addition, many algorithms return iterators. Forexample, the standard algorithm find looks for a value in a sequence and returns an iterator to theelement found:bool has_c(const string& s, char c){auto p = find(s.begin(),s.end(),c);if (p!=s.end())return true;elsereturn false;}// does s contain the character c?Like many standard-library search algorithms, find returns end() to indicate ‘‘not found.’’ An equivalent, shorter, definition of has_c() is:104A Tour of C++: Containers and AlgorithmsChapter 4bool has_c(const string& s, char c)// does s contain the character c?{return find(s.begin(),s.end(),c)!=s.end();}A more interesting exercise would be to find the location of all occurrences of a character in astring. We can return the set of occurrences as a vector of string iterators. Returning a vector isefficient because of vector provides move semantics (§3.3.1). Assuming that we would like tomodify the locations found, we pass a non-const string:vector<string::iterator> find_all(string& s, char c){vector<string::iterator> res;for (auto p = s.begin(); p!=s.end(); ++p)if (∗p==c)res.push_back(p);return res;}// find all occurrences of c in sWe iterate through the string using a conventional loop, moving the iterator p forward one elementat a time using ++ and looking at the elements using the dereference operator ∗.

We could testfind_all() like this:void test(){string m {"Mary had a little lamb"};for (auto p : find_all(m,'a'))if (∗p!='a')cerr << "a bug!\n";}That call of find_all() could be graphically represented like this:find_all(m,’a’):m:M aryh a dalittlela m bIterators and standard algorithms work equivalently on every standard container for which their usemakes sense.

Consequently, we could generalize find_all():template<typename C, typename V>vector<typename C::iterator> find_all(C& c, V v){vector<typename C::iterator> res;for (auto p = c.begin(); p!=c.end(); ++p)if (∗p==v)res.push_back(p);return res;}// find all occurrences of v in cSection 4.5.1Use of Iterators105The typename is needed to inform the compiler that C’s iterator is supposed to be a type and not avalue of some type, say, the integer 7.

We can hide this implementation detail by introducing a typealias (§3.4.5) for Iterator:template<typename T>using Iterator<T> = typename T::iterator;template<typename C, typename V>vector<Iterator<C>> find_all(C& c, V v)// find all occurrences of v in c{vector<Iterator<C>> res;for (auto p = c.begin(); p!=c.end(); ++p)if (∗p==v)res.push_back(p);return res;}We can now write:void test(){string m {"Mary had a little lamb"};for (auto p : find_all(m,'a'))if (∗p!='a')cerr << "string bug!\n";// p is a string::iteratorlist<double> ld {1.1, 2.2, 3.3, 1.1};for (auto p : find_all(ld,1.1))if (∗p!=1.1)cerr << "list bug!\n";vector<string> vs { "red", "blue", "green", "green", "orange", "green" };for (auto p : find_all(vs,"green"))if (∗p!="green")cerr << "vector bug!\n";for (auto p : find_all(vs,"green"))∗p = "vert";}Iterators are used to separate algorithms and containers.

An algorithm operates on its data throughiterators and knows nothing about the container in which the elements are stored. Conversely, acontainer knows nothing about the algorithms operating on its elements; all it does is to supply iterators upon request (e.g., begin() and end()). This model of separation between data storage andalgorithm delivers very general and flexible software.4.5.2 Iterator TypesWhat are iterators really? Any particular iterator is an object of some type.

There are, however,many different iterator types, because an iterator needs to hold the information necessary for doing106A Tour of C++: Containers and AlgorithmsChapter 4its job for a particular container type. These iterator types can be as different as the containers andthe specialized needs they serve. For example, a vector’s iterator could be an ordinary pointer,because a pointer is quite a reasonable way of referring to an element of a vector:iterator:pvector:PietHeinAlternatively, a vector iterator could be implemented as a pointer to the vector plus an index:iterator:(start == p, position == 3)vector:PietHeinUsing such an iterator would allow range checking.A list iterator must be something more complicated than a simple pointer to an element becausean element of a list in general does not know where the next element of that list is.

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

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