Chapter 9. Sequential Containers

C++primer C++ 课程学习 所有文稿

A container holds a collection of objects of a specified type. The sequential containers 顺序容器 let the programmer control the order in which the elements are stored and accessed. That order does not depend on the values of the elements. Instead, the order corresponds to the position at which elements are put into the container. By contrast, the ordered and unordered associative containers, which we cover in Chapter 11, store their elements based on the value of a key.

The library also provides three container adaptors 配适器, each of which adapts a container type by defining a different interface 接口 to the container’s operations. We cover the adaptors at the end of this chapter.

9.1 Overview of the Sequential Containers

The sequential containers all provide fast sequential access to their elements. However, these containers offer different performance tradeoffs 性能折中 relative to:

• The costs to add or delete elements to the container
• The costs to perform nonsequential access 非顺序访问 to elements of the container

string and vector hold their elements in contiguous memory. Because elements are contiguous, it is fast to compute the address of an element from its index. However, adding or removing elements in the middle of one of these containers takes time:

The list and forward_list containers are designed to make it fast to add or remove an element anywhere in the container. An element can accessed only by iterating 遍历 through the container. The memory overhead 额外内存开销 for these containers is often substantial.

As with string and vector, adding or removing elements in the middle of a deque is a (potentially) expensive operation. However, adding or removing elements at either end of the deque is a fast operation, comparable to adding an element to a list or forward_list.

An array is a safer, easier-to-use alternative to built-in arrays.

A forward_list is intended to be comparable to the best handwritten, singly linked list. Consequently, forward_list does not have the size operation because storing or computing its size would entail overhead compared to a handwritten list. For the other containers, size is guaranteed to be a fast, constant-time operation 快速的常量时间的操作.

The new library containers are dramatically faster than in previous releases. Modern C++ programs should use the library containers rather than more primitive structures like arrays.

Deciding Which Sequential Container to Use

Tip
Ordinarily, it is best to use vector unless there is a good reason to prefer another container.

The details are a bit complicated. So I coped the whole paragraph.

• If space overhead matters, don’t use list or forward_list.
• Random access to elements, use a vector or a deque.
• Insert or delete elements in the middle of the container, use a list or forward_list.
• Insert or delete elements at the front and the back, but not in the middle, use a deque.
• Insert elements in the middle of the container only while reading input, and subsequently needs random access to the elements:
  
  • First, decide whether you actually need to add elements in the middle of a container. It is often easier to append to a vector and then call the library sort function to reorder the container when you’re done with input.
  • If you must insert into the middle, consider using a list for the input phase. Once the input is complete, copy the list into a vector.
• Random access and insert and delete elements in the middle of the container. This decision will depend on the relative cost of accessing the elements in a list or forward_list versus the cost of inserting or deleting elements in a vector or deque. In general, the predominant operation 占主导地位的操作 of the application (whether it does more access or more insertion or deletion) will determine the choice of container type. In such cases, performance testing the application using both containers will probably be necessary.

Best Practices
If you’re not sure which container to use, write your code so that it uses only operations common to both vectors and lists: Use iterators, not subscripts, and avoid random access to elements. That way it will be easy to use either a vector or a list as necessary

9.2 Container Library Overview

In general, each container is defined in a header file with the same name as the type. That is, deque is in the deque header, list in the list header, and so on. The containers are class templates 容器均定义为模板类.

Constraints on Types That a Container Can Hold

Almost any type can be used as the element type of a sequential container. In particular, we can define a container whose element type is itself another container.

Although we can store almost any type in a container, some container operations impose requirements of their own on the element type 某些容器操作对元素类型有其自己的特殊要求.

The operations on the container types can be seen in tables in the book, which will not be listed here.

Container Operations

9.2.1 Iterators

As with the containers, iterators have a common interface 公共接口: If an iterator provides an operation, then the operation is supported in the same way for each iterator that supplies that operation.

The container iterators support all the operations listed in table 3.6 in the book. One exception is that The forward_list iterators do not support the decrement -- operator. The iterator arithmetic operations listed in Table 3.7 apply only to iterators for string, vector, deque and array.

Iterator Ranges

The concept of an iterator range is fundamental to the standard library.

An **iterator range 迭代器范围**is denoted by a pair of iterators each of which refers to an element, or to one past the last element, in the same container. These two iterators, often referred to as begin and end—or (somewhat misleadingly) as first and last—mark a range of elements from the container.

The elements in the range include the element denoted by first and every element from first up to but not including last. This element range is called a left-inclusive interval 左闭合区间. The standard mathematical notation for such a range is [ begin, end).

Programming Implications 编程假定 of Using Left-Inclusive Ranges

The library uses left-inclusive ranges because such ranges have three convenient properties. Assuming begin and end denote a valid iterator range, then

• If begin equals end, the range is empty
• If begin is not equal to end, there is at least one element in the range, and begin refers to the first element in that range
• We can increment begin some number of times until begin == end

These properties mean that we can safely write loops such as the following to process a range of elements.

9.2.2 Container Type Members 容器类型成员

size_type, iterator and const_iterator are three of container-defined types. Provided by most containers, a reverse iterator 反向迭代器 is an iterator that goes backward through a container and inverts the meaning of the iterator operations.

The remaining type aliases 类型别名 let us use the type of the elements stored in a container without knowing what that type is. If we need the element type, we refer to the container’s value_type. If we need a reference to that type, we use reference or const_reference. These element-related type aliases are most useful in generic programs 泛型编程. (I don't understand what this paragraph is talking about. Problems remain unsolved. -2019.1.26)

To use one of these types, we must name the class of which they are a member 显式使用其类型名:

// iter is the iterator type defined by list<string>
list<string>::iterator iter;
// count is the difference_type type defined by vector<int>
vector<int>::difference_type count;
/*use the scope operator to say that we want the iterator member of the list<string> class and the difference_type defined by vector<int>*/

9.2.3 begin and end Members

The functions that do not begin with a c are overloaded 重载. That is, there are actually two members named begin. One is a const member that returns the container’s const_iterator type. The other is nonconst and returns the container’s iterator type. Similarly for rbegin, end and rend. As with pointers and references to const, we can convert a plain iterator to the corresponding const_iterator, but not vice versa 反之.

// iterator or const_iterator depending on a's type of a
auto it7 = a.begin(); // const_iterator only if a is const
auto it8 = a.cbegin(); // it8 is const_iterator

Best Practices
When write access 写操作 is not needed, use cbegin and cend.

9.2.4 Defining and Initializing a Container

Every container type defines a default constructor (§ 7.1.4, p. 263). Haven't learned yet. -2019.1.27 With the exception of array, the default constructor creates an empty container of the specified type. Again excepting array, the other constructors take arguments that specify the size of the container and initial values for the elements. Don't understand.

Initializing a Container as a Copy of Another Container

To create a container as a copy of another container, the container and element types must match. When we pass iterators (denoting a range of elements to be copied), there is no requirement that the container types be identical. Moreover, the element types in the new and original containers can differ as long as it is possible to convert the elements we’re copying to the element type of the container we are initializing.

// each container has three elements, initialized from the given initializers
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};
list<string> list2(authors); // ok: types match
deque<string> authList(authors); // error: container types don't match
vector<string> words(articles); // error: element types must match
// ok: converts const char* elements to string
forward_list<string> words(articles.begin(), articles.end());
// copies up to but not including the element denoted by it
deque<string> authList(authors.begin(), it);

List Initialization

Under the new standard C++11, we can list initialize 列表初始化a container. The container will have as many elements as there are initializers.

Sequential Container Size-Related Constructors 大小相关的构造函数

In addition to the constructors that sequential containers have in common with associative containers(??????), we can also initialize the sequential containers (other than array) from a size and an (optional) element initializer. If we do not supply an element initializer, the library creates a value-initialized one 值初始化器 for us.

vector<int> ivec(10, -1); // ten int elements, each initialized to -1
list<string> svec(10, "hi!"); // ten strings; each element is "hi!"
forward_list<int> ivec(10); // ten elements, each initialized to 0
deque<string> svec(10); // ten elements, each an empty string

We can use the constructor that takes a size argument if the element type is a built-in type or a class type that has a default constructor (§ 9.2, p. 329)???????. If the element type does not have a default constructor, then we must specify an explicit element initializer along with the size.

Note
The constructors that take a size are valid only for sequential containers; they are not supported for the associative containers

Library arrays Have Fixed Size

array<int, 42> // type is: array that holds 42 ints
array<string, 10> // type is: array that holds 10 strings
/*To use an array type we must specify both the element type and the size*/
array<int, 10>::size_type i; // array type includes element type and size
array<int>::size_type j; // error: array<int> is not a type

The elements are default initialized just as are elements in a built-in array. When we list initialize an array, if there are fewer initializers than the size of the array, the initializers are used for the first elements and any remaining elements are value initialized 值初始化. In this cases, if the element type is a class type, the class must have a default constructor in order to permit value initialization:

array<int, 10> ia1; // ten default-initialized ints
array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; // list initialization
array<int, 10> ia3 = {42}; // ia3[0] is 42, remaining elements are 0

Although we cannot copy or assign objects of built-in array types, there is no such restriction on array.

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; // error: no copy or assignment for built-in arrays
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits; // ok: so long as array types match

9.2.5 Assignment and swap

If the containers had been of unequal size, after the assignment both containers would have the size of the right-hand operand.

WARNING

Assignment related operations invalidate 无效化 iterators, references and pointers into the left-hand container. Aside from string they remain valid after a swap and (excepting arrays) the containers to which they refer are swapped. 将容器内容交换不会导致失效

Unlike built-in arrays, the library array type does allow assignment. The left-and right-hand operands must have the same type. Because the size of the right-hand operand might differ from the size of the left-hand operand, the array type does not support assign and it does not allow assignment from a braced list of values.

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0}; // elements all have value 0
a1 = a2; // replaces elements in a1
a2 = {0}; // error: cannot assign to an array from a braced list

Using assign (Sequential Containers Only)

The sequential containers (except array) also define a member named assign that lets us assign from a different but compatible type, or assign from a subsequence 子序列 of a container. The assign operation replaces all the elements in the left-hand container with (copies of) the elements specified by its arguments.

list<string> names;
vector<const char*> oldstyle;
names = oldstyle; // error: container types don't match
// ok: can convert from const char*to string
names.assign(oldstyle.cbegin(), oldstyle.cend());

The arguments to assign determine how many elements and what values the container will have.

Warning
Because the existing elements are replaced, the iterators passed to assign must not refer to the container on which assign is called.

// equivalent to slist1.clear();
// followed by slist1.insert(slist1.begin(), 10, "Hiya!");
list<string> slist1(1); // one element, which is the empty string
slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya !

Using swap

vector<string> svec1(10); // vector with ten elements
vector<string> svec2(24); // vector with 24 elements
swap(svec1, svec2);

With the exception of arrays, swapping two containers is guaranteed to be fast—the elements themselves are not swapped; internal data structures are swapped. Excepting array, swap does not copy, delete, or insert any elements and is guaranteed to run in constant time. The fact that elements are not moved means that, with the exception of string, iterators, references, and pointers into the containers are not invalidated. They refer to the same elements as they did before the swap. However, after the swap, those elements are in a different contain. For example, had iter denoted the string at position svec1 [3] before the swap, it will denote the element at position svec2[3] after the swap. Differently from the containers, a call to swap on a string may invalidate iterators, references and pointers.

Unlike how swap behaves for the other containers, swapping two arrays does exchange the elements. As a result, swapping two arrays requires time proportional 正比 to the number of elements in the array. After the swap, pointers, references, and iterators remain bound to the same element they denoted before the swap. Of course, the value of that element has been swapped with the corresponding element in the other array.

9.2.6 Container Size Operations

With one exception, the container types have three size-related operations. The size member returns the number of elements in the container; empty returns a bool that is true if size is zero and false otherwise; and max_size returns a number that is greater than or equal to the number of elements a container of that type can contain. For reasons we’ll explain in the next section, forward_list provides max_size and empty, but not size.

9.2.7 Relational Operators

The right- and left-hand operands must be the same kind of container and must hold elements of the same type.

Comparing two containers performs a pairwise comparison of the elements. These operators work similarly to the string relationals :

• equal if same size and all the elements are equal
• different sizes but every element is equal, then the smaller one is less than the other.
• If neither container is an initial subsequence of the other, compard the first unequal elements.

Note
We can use a relational operator to compare two containers only if the appropriate comparison operator is defined for the element type.

For example, the Sales_data type that we defined in Chapter 7 does not define either the == or the < operation. Therefore, we cannot compare two containers that hold Sales_data elements.

9.3 Sequential Container Operations

The sequential and associative containers differ in how they organize their elements. These differences affect how elements are stored, accessed, added, and removed.

9.3.1 Adding Elements to a Sequential Container

These operations are not supported by array.

forward_list has special versions of insert and emplace. (9.3.4)

push_back and emplace_back are not valid for forward_list.

push_front and emplace_front are not valid for vector or string.

WARNING

Adding eles to a vector, string or deque potentially invalidate all existing iterators, references and pointers into the container.

The containers use different strategies for allocating elements and that these strategies affect performance. Adding elements anywhere but at the end of a vector or string, or anywhere but the
beginning or end of a deque, requires elements to be moved. Moreover, adding elements to a vector or a string may cause the entire object to be reallocated.

Using push_back

For string is a container of characters, we can use push_back to add characters to the end of the string.

void pluralize(size_t cnt, string &word)
{
    if (cnt > 1)
        word.push_back('s'); // same as word += 's'
} 

Key Concept: Container Elements Are Copies
When we use an object to initialize a container, or insert an object into a container, a copy of that object’s value is placed in the container, not the object itself. Just as when we pass an object to a nonreference parameter (§ 6.2.1, p. 209), there is no relationship between the element in the container and the object from which that value originated. Subsequent changes to the element in the container have no effect on the original object, and vice versa.

Using push_front

A deque guarantees constant-time insert and delete of elements at the beginning and end of the container. As withvector, inserting elements other than at the front or back of a deque is a potentially expensive operation.

Adding Elements at a Specified Point in the Container

Even though some containers do not have a push_front operation, there is no similar constraint on insert. We can insert elements at the beginning of a container without worrying about whether the container has push_front.

Warning
It is legal to insert anywhere in a vector, deque, or string. However, doing so can be an expensive operation.

Inserting a Range of Elements

When we pass a pair of iterators, those iterators may not refer to the same container as the one to which we are adding elements.

Under the new standard C++11, the versions of insert that take a count or a range return an iterator to the first element that was inserted. (In prior versions of the library, these operations returned void.) If the range is empty, no elements are inserted, and the operation returns its first parameter.

Using the Return from insert

We can use the value returned by insert to repeatedly insert elements at a specified
position in the container.

list<string> 1st;
auto iter = 1st.begin();
while (cin >> word)
    iter = 1st.insert(iter, word); // same as calling push_front

Using the Emplace Operations
The new standard C++11 introduced three new members—emplace_front, emplace, and emplace_back—that construct rather than copy elements.

When we call an emplace member, we pass arguments to a constructor 构造函数 for the element type. The emplace members use those arguments to construct an element directly in space managed by the container.

// construct a Sales_data object at the end of c
// uses the three-argument Sales_data constructor
c.emplace_back("978-0590353403", 25, 15.99);
// error: there is no version of push_back that takes three arguments
c.push_back("978-0590353403", 25, 15.99);
// ok: we create a temporary Sales_data object to pass to push_back
c.push_back(Sales_data("978-0590353403", 25, 15.99));

The call to emplace_back and the second call to push_back both create new Sales_data objects. In the call to emplace_back, that object is created directly in space managed by the container. The call to push_back creates a local temporary object that is pushed onto the container.

Note
The emplace functions construct elements in the container. The arguments to these functions must match a constructor for the element type.

9.3.2 Accessing Elements

// check that there are elements before dereferencing an iterator or calling front or
back
if (!c.empty()) {...}

The Access Members Return References

If the container is a const object, the return is a reference to const. If the container is not const, the return is an ordinary reference that we can use to change the value of the fetched element.

if (!c.empty()) {
    c.front() = 42; // assigns 42 to the first element in c
    auto &v = c.back(); // get a reference to the last element
    v = 1024; // changes the element in c
    auto v2 = c.back(); // v2 is not a reference; it's a copy of c.back()
    v2 = 0; // no change to the element in c
}

As usual, if we use auto to store the return from one of these functions and we want to use that variable to change the element, we must remember to define our variable as a reference type.

Subscripting and Safe Random Access

vector<string> svec; // empty vector
cout << svec[0]; // run-time error: there are no elements in svec!
cout << svec.at(0); // throws an out_of_range exception

9.3.3 Erasing Elements

Not supported by array.

forward_list has a special version of erase and doesn't support pop_back.

pop_front not valid for vector and string.

Warning
The members that remove elements do not check their argument(s). The programmer must ensure that element(s) exist before removing them.

Removing eles anywhere but the beginning or end of a deque invalidates all iterators, references and pointers.

Iterators, references and pointers to eles after the erasure point in a vector or string are invalidated.

The pop_front and pop_back Members

Just as there is no push_front for vector and string, there is also no pop_front for those types. Similarly, forward_list does not have pop_back.

Removing an Element from within the Container

if j is the element following i, then erase(i) will return an iterator referring to j.

9.3.4 Specialized forward_list Operations

To add or remove an element, we need access to its predecessor 前驱 in order to update that element’s links. However, forward_list is a singly linked list. In a singly linked list there is no easy way to get to an element’s predecessor. For this reason, the operations to add or remove elements in a forward_list operate by changing the element after the given element. That way, we always have access to the elements that are affected by the change.

To support these operations, forward_list also defines before_begin, which returns an off-the-beginning 首前 iterator.

9.3.5 Resizing a Container

9.3.6 Container Operations May Invalidate Iterators

9.4 How a vector Grows

9.5 Additional string Operations

9.5.1 Other Ways to Construct strings

9.5.2 Other Ways to Change a string

9.5.3 string Search Operations

9.5.4 The compare Functions

9.5.5 Numeric Conversions

9.6 Container Adaptors

施工开始 -2019.1.26

暂停施工，进度已完成9.3.4 -2019.1.31