B. Stroustrup - The C++ Programming Language (794319), страница 27
Текст из файла (страница 27)
The vector memberfunction size() gives the number of elements.The elements of a vector constitute a range, so we can use a range-for loop (§2.2.5):void print_book(const vector<Entry>& book){for (const auto& x : book)// for "auto" see §2.2.2cout << x << '\n';}When we define a vector, we give it an initial size (initial number of elements):vector<int> v1 = {1, 2, 3, 4};vector<string> v2;vector<Shape∗> v3(23);vector<double> v4(32,9.9);// size is 4// size is 0// size is 23; initial element value: nullptr// size is 32; initial element value: 9.9An explicit size is enclosed in ordinary parentheses, for example, (23), and by default the elementsare initialized to the element type’s default value (e.g., nullptr for pointers and 0 for numbers). Ifyou don’t want the default value, you can specify one as a second argument (e.g., 9.9 for the 32 elements of v4).The initial size can be changed.
One of the most useful operations on a vector is push_back(),which adds a new element at the end of a vector, increasing its size by one. For example:void input(){for (Entry e; cin>>e;)phone_book.push_back(e);}This reads Entrys from the standard input into phone_book until either the end-of-input (e.g., theend of a file) is reached or the input operation encounters a format error. The standard-libraryvector is implemented so that growing a vector by repeated push_back()s is efficient.A vector can be copied in assignments and initializations.
For example:vector<Entry> book2 = phone_book;Section 4.4.1vector97Copying and moving of vectors are implemented by constructors and assignment operators asdescribed in §3.3. Assigning a vector involves copying its elements. Thus, after the initializationof book2, book2 and phone_book hold separate copies of every Entry in the phone book. When avector holds many elements, such innocent-looking assignments and initializations can be expensive.
Where copying is undesirable, references or pointers (§7.2, §7.7) or move operations (§3.3.2,§17.5.2) should be used.4.4.1.1 ElementsLike all standard-library containers, vector is a container of elements of some type T, that is, avector<T>. Just about any type qualifies as an element type: built-in numeric types (such as char,int, and double), user-defined types (such as string, Entry, list<int>, and Matrix<double,2>), and pointers (such as const char∗, Shape∗, and double∗).
When you insert a new element, its value is copiedinto the container. For example, when you put an integer with the value 7 into a container, theresulting element really has the value 7. The element is not a reference or a pointer to some objectcontaining 7.
This makes for nice compact containers with fast access. For people who care aboutmemory sizes and run-time performance this is critical.4.4.1.2 Range CheckingThe standard-library vector does not guarantee range checking (§31.2.2). For example:void silly(vector<Entry>& book){int i = book[ph.size()].number;// ...}// book.size() is out of rangeThat initialization is likely to place some random value in i rather than giving an error. This isundesirable, and out-of-range errors are a common problem. Consequently, I often use a simplerange-checking adaptation of vector:template<typename T>class Vec : public std::vector<T> {public:using vector<T>::vector; // use the constructors from vector (under the name Vec); see §20.3.5.1T& operator[](int i){ return vector<T>::at(i); }const T& operator[](int i) const{ return vector<T>::at(i); }// range check// range check const objects; §3.2.1.1};inherits everything from vector except for the subscript operations that it redefines to do rangechecking.
The at() operation is a vector subscript operation that throws an exception of typeout_of_range if its argument is out of the vector’s range (§2.4.3.1, §31.2.2).Vec98A Tour of C++: Containers and AlgorithmsChapter 4For Vec, an out-of-range access will throw an exception that the user can catch. For example:void checked(Vec<Entry>& book){try {book[book.size()] = {"Joe",999999};// ...}catch (out_of_range) {cout << "range error\n";}}// will throw an exceptionThe exception will be thrown, and then caught (§2.4.3.1, Chapter 13). If the user doesn’t catch anexception, the program will terminate in a well-defined manner rather than proceeding or failing inan undefined manner.
One way to minimize surprises from uncaught exceptions is to use a main()with a try-block as its body. For example:int main()try {// your code}catch (out_of_range) {cerr << "range error\n";}catch (...) {cerr << "unknown exception thrown\n";}This provides default exception handlers so that if we fail to catch some exception, an error message is printed on the standard error-diagnostic output stream cerr (§38.1).Some implementations save you the bother of defining Vec (or equivalent) by providing a rangechecked version of vector (e.g., as a compiler option).4.4.2 listThe standard library offers a doubly-linked list called list:list:4linkslinkslinkslinksWe use a list for sequences where we want to insert and delete elements without moving other elements.
Insertion and deletion of phone book entries could be common, so a list could be appropriate for representing a simple phone book. For example:list<Entry> phone_book = {{"David Hume",123456},Section 4.4.2list99{"Karl Popper",234567},{"Bertrand Arthur William Russell",345678}};When we use a linked list, we tend not to access elements using subscripting the way we commonly do for vectors. Instead, we might search the list looking for an element with a given value.To do this, we take advantage of the fact that a list is a sequence as described in §4.5:int get_number(const string& s){for (const auto& x : phone_book)if (x.name==s)return x.number;return 0; // use 0 to represent "number not found"}The search for s starts at the beginning of the list and proceeds until s is found or the end ofphone_book is reached.Sometimes, we need to identify an element in a list.
For example, we may want to delete it orinsert a new entry before it. To do that we use an iterator: a list iterator identifies an element of alist and can be used to iterate through a list (hence its name). Every standard-library container provides the functions begin() and end(), which return an iterator to the first and to one-past-the-lastelement, respectively (§4.5, §33.1.1). Using iterators explicitly, we can – less elegantly – write theget_number() function like this:int get_number(const string& s){for (auto p = phone_book.begin(); p!=phone_book.end(); ++p)if (p−>name==s)return p−>number;return 0; // use 0 to represent "number not found"}In fact, this is roughly the way the terser and less error-prone range-for loop is implemented by thecompiler. Given an iterator p, ∗p is the element to which it refers, ++p advances p to refer to thenext element, and when p refers to a class with a member m, then p−>m is equivalent to (∗p).m.Adding elements to a list and removing elements from a list is easy:void f(const Entry& ee, list<Entry>::iterator p, list<Entry>::iterator q){phone_book.insert(p,ee);// add ee before the element referred to by pphone_book.erase(q);// remove the element referred to by q}For a more complete description of insert() and erase(), see §31.3.7.These list examples could be written identically using vector and (surprisingly, unless youunderstand machine architecture) perform better with a small vector than with a small list.
Whenall we want is a sequence of elements, we have a choice between using a vector and a list. Unlessyou have a reason not to, use a vector. A vector performs better for traversal (e.g., find() andcount()) and for sorting and searching (e.g., sort() and binary_search()).100A Tour of C++: Containers and AlgorithmsChapter 44.4.3 mapWriting code to look up a name in a list of (name,number) pairs is quite tedious. In addition, a linear search is inefficient for all but the shortest lists.
The standard library offers a search tree (a redblack tree) called map:map:links4linkskey:value:linkslinksIn other contexts, a map is known as an associative array or a dictionary. It is implemented as a balanced binary tree.The standard-library map (§31.4.3) is a container of pairs of values optimized for lookup. Wecan use the same initializer as for vector and list (§4.4.1, §4.4.2):map<string,int> phone_book {{"David Hume",123456},{"Karl Popper",234567},{"Bertrand Arthur William Russell",345678}};When indexed by a value of its first type (called the key), a map returns the corresponding value ofthe second type (called the value or the mapped type).
For example:int get_number(const string& s){return phone_book[s];}In other words, subscripting a map is essentially the lookup we called get_number(). If a key isn’tfound, it is entered into the map with a default value for its value. The default value for an integertype is 0; the value I just happened to choose represents an invalid telephone number.If we wanted to avoid entering invalid numbers into our phone book, we could use find() andinsert() instead of [] (§31.4.3.1).4.4.4 unordered_mapThe cost of a map lookup is O(log(n)) where n is the number of elements in the map. That’s prettygood. For example, for a map with 1,000,000 elements, we perform only about 20 comparisonsand indirections to find an element. However, in many cases, we can do better by using a hashedlookup rather than comparison using an ordering function, such as <. The standard-library hashedSection 4.4.4unordered_map101containers are referred to as ‘‘unordered’’ because they don’t require an ordering function:unordered_map:rephash table:For example, we can use an unordered_map from <unordered_map> for our phone book:unordered_map<string,int> phone_book {{"David Hume",123456},{"Karl Popper",234567},{"Bertrand Arthur William Russell",345678}};As for a map, we can subscript an unordered_map:int get_number(const string& s){return phone_book[s];}The standard-library unordered_map provides a default hash function forcan provide your own (§31.4.3.4).strings.If necessary, you4.4.5 Container OverviewThe standard library provides some of the most general and useful container types to allow the programmer to select a container that best serves the needs of an application:Standard Container Summaryvector<T>list<T>forward_list<T>deque<T>set<T>multiset<T>map<K,V>multimap<K,V>unordered_map<K,V>unordered_multimap<K,V>unordered_set<T>unordered_multiset<T>A variable-size vector (§31.4)A doubly-linked list (§31.4.2)A singly-linked list (§31.4.2)A double-ended queue (§31.2)A set (§31.4.3)A set in which a value can occur many times (§31.4.3)An associative array (§31.4.3)A map in which a key can occur many times (§31.4.3)A map using a hashed lookup (§31.4.3.2)A multimap using a hashed lookup (§31.4.3.2)A set using a hashed lookup (§31.4.3.2)A multiset using a hashed lookup (§31.4.3.2)The unordered containers are optimized for lookup with a key (often a string); in other words, theyare implemented using hash tables.102A Tour of C++: Containers and AlgorithmsChapter 4The standard containers are described in §31.4.
The containers are defined in namespace stdand presented in headers <vector>, <list>, <map>, etc. (§4.1.2, §30.2). In addition, the standardlibrary provides container adaptors queue<T> (§31.5.2), stack<T> (§31.5.1), deque<T> (§31.4), andpriority_queue<T> (§31.5.3). The standard library also provides more specialized container-liketypes, such as a fixed-size array array<T,N> (§34.2.1) and bitset<N> (§34.2.2).The standard containers and their basic operations are designed to be similar from a notationalpoint of view. Furthermore, the meanings of the operations are equivalent for the various containers. Basic operations apply to every kind of container for which they make sense and can be efficiently implemented.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
