9.3. Sequence Container Operations

9.3. 每种顺序容器都提供了一组有用的类型定义以及以下操作：

Each sequential container defines a set of useful typedefs and supports operations that let us

每种顺序容器都提供了一组有用的类型定义以及以下操作：

• Add elements to the container

  在容器中添加元素。

• Delete elements from the container

  在容器中删除元素。

• Determine the size of the container

  设置容器大小。

• Fetch the first and last elements from the container, if any

  （如果有的话）获取容器内的第一个和最后一个元素。

9.3.1. Container Typedefs

9.3.1. 容器定义的类型别名

We've used three of the container-defined types: size_type, iterator, and const_iterator. Each container defines these types, along with several others shown in Table 9.5.

在前面的章节里，我们已经使用过三种由容器定义的类型：size_type、iterator 和 const_iterator。所有容器都提供这三种类型以及表 9.5 所列出的其他类型。

Table 9.5. Container-Defined Typedefs

表 9.5. 容器定义的类型别名

We'll have more to say about reverse iterators in Section 11.3.3 (p. 412), but briefly, a reverse iterator is an iterator that goes backward through a container and inverts the iterator operations: For example, saying ++ on a reverse iterator yields the previous element in the container.

我们将在第 11.3.3 节中详细介绍逆序迭代器。简单地说，逆序迭代器从后向前遍历容器，并反转了某些相关的迭代器操作：例如，在逆序迭代器上做 ++ 运算将指向容器中的前一个元素。

The last three types in Table 9.5 on the facing page let us use the type of the elements stored in a container without directly 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. The utility of these element-related typedefs will be more apparent when we define our own generic programs in Chapter 16.

表 9.5 的最后三种类型使程序员无须直接知道容器元素的真正类型，就能使用它。需要使用元素类型时，只要用 value_type 即可。如果要引用该类型，则通过 reference 和 const_reference 类型实现。在程序员编写自己的泛型程序（第十六章）时，这些元素相关类型的定义非常有用。

Expressions that use a container-defined type can look intimidating:

使用容器定义类型的表达式看上去非常复杂：

     // iter is the iterator type defined by list<string>
     list<string>::iterator iter;

     // cnt is the difference_type type defined by vector<int>
     vector<int>::difference_type cnt;

The declaration of iter uses the scope operator to say that we want the name on the right-hand side of the :: from the scope of the left-hand side. The effect is to declare that iter has whatever type is defined for the iterator member from the list class that holds elements of type string.

iter 所声明使用了作用域操作符，以表明此时所使用的符号 :: 右边的类型名字是在符号 iter 左边指定容器的作用域内定义的。其效果是将 iter 声明为 iterator 类型，而 iterator 是存放 string 类型元素的 list 类的成员。

9.3.2. begin and end Members

9.3.2. begin 和 end 成员

The begin and end operations yield iterators that refer to the first and one past the last element in the container. These iterators are most often used to form an iterator range that encompasses all the elements in the container.

begin 和 end 操作产生指向容器内第一个元素和最后一个元素的下一位置的迭代器，如表 9.6 所示。这两个迭代器通常用于标记包含容器中所有元素的迭代器范围。

Table 9.6. Container begin and end Operations

表 9.6. 容器的 begin 和 end 操作

There are two different versions of each of these operations: One is a const member (Section 7.7.1, p. 260) and the other is nonconst. The return type of these operations varies on whether the container is const. In each case, if the container is nonconst, then the result's type is iterator or reverse_iterator. If the object is const, then the type is prefixed by const_, that is, const_iterator or const_reverse_iterator. We cover reverse iterators in Section 11.3.3 (p. 412).

上述每个操作都有两个不同版本：一个是 const 成员（第 7.7.1 节），另一个是非 const 成员。这些操作返回什么类型取决于容器是否为 const。如果容器不是 const，则这些操作返回 iterator 或 reverse_iterator 类型。如果容器是 const，则其返回类型要加上 const_ 前缀，也就是 const_iterator 和 const_reverse_iterator 类型。我们将在第 11.3.3 节中详细介绍逆序迭代器。

9.3.3. Adding Elements to a Sequential Container

9.3.3. 在顺序容器中添加元素

In Section 3.3.2 (p. 94) we saw one way to add elements: push_back. Every sequential container supports push_back, which appends an element to the back of the container. The following loop reads one string at a time into text_word:

第 3.3.2 节介绍了添加元素的一种方法：push_back。所有顺序容器都支持 push_back 操作（表 9.7），提供在容器尾部插入一个元素的功能。下面的循环每次读入一个 string 类型的值，并存放在 text_word: 对象中：

     // read from standard input putting each word onto the end of container
     string text_word;
     while (cin >> text_word)
         container.push_back(text_word);

The call to push_back creates a new element at the end of container, increasing the size of container by one. The value of that element is a copy of text_word. The type of container can be any of list, vector, or deque.

调用 push_back 函数会在容器 container 尾部创建一个新元素，并使容器的长度加 1。新元素的值为 text_word 对象的副本，而 container 的类型则可能是 list、vector 或 deque。

In addition to push_back, the list and deque containers support an analogous operation named push_front. This operation inserts a new element at the front of the container. For example,

除了 push_back 运算，list 和 deque 容器类型还提供了类似的操作：push_front。这个操作实现在容器首部插入新元素的功能。例如：

     list<int> ilist;
     // add elements at the end of ilist
     for (size_t ix = 0; ix != 4; ++ix)
         ilist.push_back(ix);

uses push_back to add the sequence 0, 1, 2, 3 to the end of ilist.

使用 push_back 操作在容器 ilist 尾部依次添加元素 0、1、2、3。

Alternatively, we could use push_front

然后，我们选择用 push_front 操作再次在 ilist 中添加元素：

     // add elements to the start of ilist
     for (size_t ix = 0; ix != 4; ++ix)
         ilist.push_front(ix);

to add the elements 0, 1, 2, 3 to the beginning of ilist. Because each element is inserted at the new beginning of the list, they wind up in reverse order. After executing both loops, ilist holds the sequence 3,2,1,0,0,1,2,3.

此时，元素 0、1、2、3 则被依次添加在 ilist 的开始位置。由于每个元素都在 list 的新起点插入，因此它们在容器中以逆序排列，循环结束后，ilist 内的元素序列为：3、2、1、0、0、1、2、3。

Table 9.7. Operations that Add Elements to a Sequential Container

表 9.7 在顺序容器中添加元素的操作

Adding Elements at a Specified Point in the Container

在容器中指定位置添加元素

The push_back and push_front operations provide convenient ways to insert a single element at the end or beginning of a sequential container. More generally, insert allows us to insert elements at any particular point in the container. There are three versions of insert. The first takes an iterator and an element value. The iterator refers to the position at which to insert the value. We could use this version of insert to insert an element at the beginning of a container:

使用 push_back 和 push_front 操作可以非常方便地在顺序容器的尾部或首部添加单个元素。而 insert 操作则提供了一组更通用的插入方法，实现在容器的任意指定位置插入新元素。insert 操作有三个版本（表 9.7）。第一个版本需要一个迭代器和一个元素值参数，迭代器指向插入新元素的位置。下面的程序就是使用了这个版本的 insert 函数在容器首部插入新元素：

     vector<string> svec;
     list<string> slist;
     string spouse("Beth");

     // equivalent to calling slist.push_front (spouse);
     slist.insert(slist.begin(), spouse);

     // no push_front on vector but we can insert before begin()
     // warning: inserting anywhere but at the end of a vector is an expensive operation
     svec.insert(svec.begin(), spouse);

The value is inserted before the position referred to by the iterator. The iterator can refer to any position in the container, including one past the end of the container. Because the iterator might refer to a nonexistent element off the end of the container, insert inserts before the position rather than after it. This code

新元素是插入在迭代器指向的位置之前。迭代器可以指向容器的任意位置，包括超出末端的下一位置。由于迭代器可能指向超出容器末端的下一位置，这是一个不存在的元素，因此 insert 函数是在其指向位置之前而非其后插入元素。代码

     slist.insert(iter, spouse); // insert spouse just before iter

inserts a copy of spouse just before the element referred to by iter.

就在 iter 指向的元素前面插入 spouse 的副本。

This version of insert returns an iterator referring to the newly inserted element. We could use the return value to repeatedly insert elements at a specified position in the container:

这个版本的 insert 函数返回指向新插入元素的迭代器。可使用该返回值在容器中的指定位置重复插入元素：

     list<string> lst;
     list<string>::iterator iter = lst.begin();
     while (cin >> word)
        iter = lst.insert(iter, word); // same as calling push_front

要彻底地理解上述循环是如何执行的，这一点非常重要——特别是要明白我们为什么说上述循环等效于调用 push_front 函数。

Before the loop, we initialize iter to lst.begin(). Because the list is empty, lst.begin() and lst.end() are equal, so iter refers one past the end of the (empty) list. The first call to insert puts the element we just read in front of the element referred to by iter. The value returned by insert is an iterator referring to this new element, which is now the first, and only, element in lst. We assign that iterator to iter and repeat the while, reading another word. As long as there are words to insert, each trip through the while inserts a new element ahead of iter and reassigns to iter the value of the newly inserted element. That element is always the first element, so each iteration inserts an element ahead of the first element in the list.

循环前，将 iter 初始化为 lst.begin()。此时，由于该 list 对象是空的，因此 lst.begin() 与 lst.end() 相等，于是 iter 指向该（空）容器的超出末端的下一位置。第一次调用 insert 函数时，将刚读入的元素插入到 iter 所指向位置的前面，容器 lst 得到第一个也是唯一的元素。然后 insert 函数返回指向这个新元素的迭代器，并赋给 iter，接着重复 while 循环，读入下一个单词。只要有单词要插入，每次 while 循环都将新元素插入到 iter 前面，然后重置 iter 指向新插入元素。新插入的元素总是容器中的第一个元素，因此，每次迭代器都将元素插入在该 list 对象的第一元素前面。

Inserting a Range of Elements

插入一段元素

A second form of insert adds a specified number of identical elements at an indicated position:

insert 函数的第二个版本提供在指定位置插入指定数量的相同元素的功能：

     svec.insert(svec.end(), 10, "Anna");

This code inserts ten elements at the end of svec and initializes each of those elements to the string "Anna".

上述代码在容器 svec 的尾部插入 10 个元素，每个新元素都初始化为 "Anna"。

The final form of insert adds a range of elements denoted by an iterator pair into the container. For example, given the following array of strings

insert 函数的最后一个版本实现在容器中插入由一对迭代器标记的一段范围内的元素。例如，给出以下 string 类型的数组：

     string sarray[4] = {"quasi", "simba", "frollo", "scar"};

we can insert all or a subset of the array elements into our list of strings:

可将该数组中所有的或其中一部分元素插入到 string 类型的 list 容器中：

     // insert all the elements in sarray at end of slist
     slist.insert(slist.end(), sarray, sarray+4);
     list<string>::iterator slist_iter = slist.begin();
     // insert last two elements of sarray before slist_iter
     slist.insert(slist_iter, sarray+2, sarray+4);

Inserting Elements Can Invalidate Iterators

添加元素可能会使迭代器失效

As we'll see in Section 9.4 (p. 330), adding elements to a vector can cause the entire container to be relocated. If the container is relocated, then all iterators into the container are invalidated. Even if the vector does not have to be relocated, any iterator to an element after the one inserted is invalidated.

正如我们在第 9.4 节中了解的一样，在 vector 容器中添加元素可能会导致整个容器的重新加载，这样的话，该容器涉及的所有迭代器都会失效。即使需要重新加载整个容器，指向新插入元素后面的那个元素的迭代器也会失效。

Iterators may be invalidated after doing any insert or push operation on a vector or deque. When writing loops that insert elements into a vector or a deque, the program must ensure that the iterator is refreshed on each trip through the loop. 任何 insert 或 push 操作都可能导致迭代器失效。当编写循环将元素插入到 vector 或 deque 容器中时，程序必须确保迭代器在每次循环后都得到更新。

Avoid Storing the Iterator Returned from end

避免存储 end 操作返回的迭代器

When we add elements to a vector or deque, some or all of the iterators may be invalidated. It is safest to assume that all iterators are invalid. This advice is particularly true for the iterator returned by end. That iterator is always invalidated by any insertion anywhere in the container.

在 vector 或 deque 容器中添加元素时，可能会导致某些或全部迭代器失效。假设所有迭代器失效是最安全的做法。这个建议特别适用于由 end 操作返回的迭代器。在容器的任何位置插入任何元素都会使该迭代器失效。

As an example, consider a loop that reads each element, processes it and adds a new element following the original. We want the loop to process each original element. We'll use the form of insert that takes a single value and returns an iterator to the element that was just inserted. After each insertion, we'll increment the iterator that is returned so that the loop is positioned to operate on the next original element. If we attempt to "optimize" the loop, by storing an iterator to the end(), we'll have a disaster:

例如，考虑一个读取容器中每个元素的循环，对读出元素做完处理后，在原始元素后面插入一个新元素。我们希望该循环可以处理每个原始元素，然后使用 insert 函数插入新元素，并返回指向刚插入元素的迭代器。在每次插入操作完成后，给返回的迭代器自增 1，以使循环定位在下一个要处理的原始元素。如果我们尝试通过存储 end() 操作返回的迭代器来“优化”该循环，将导致灾难性错误：

     vector<int>::iterator first = v.begin(),
                           last = v.end(); // cache end iterator
     // diaster: behavior of this loop is undefined
     while (first != last) {
         // do some processing
         // insert new value and reassign first, which otherwise would be invalid
         first = v.insert(first, 42);
         ++first;  // advance first just past the element we added
      }

The behavior of this code is undefined. On many implementations, we'll get an infinite loop. The problem is that we stored the value returned by the end operation in a local variable named last. In the body of the loop, we add an element. Adding an element invalidates the iterator stored in last. That iterator neither refers to an element in v nor any longer refers to one past the last element in v.

上述代码的行为未定义。在很多实现中，该段代码将导致死循环。问题在于这个程序将 end 操作返回的迭代器值存储在名为 last 的局部变量中。循环体中实现了元素的添加运算，添加元素会使得存储在 last 中的迭代器失效。该迭代器既没有指向容器 v 的元素，也不再指向 v 的超出末端的下一位置。

Don't cache the iterator returned from end. Inserting or deleting elements in a deque or vector will invalidate the cached iterator. 不要存储 end 操作返回的迭代器。添加或删除 deque 或 vector 容器内的元素都会导致存储的迭代器失效。

Rather than storing the end iterator, we must recompute it after each insertion:

为了避免存储 end 迭代器，可以在每次做完插入运算后重新计算 end 迭代器值：

     // safer: recalculate end on each trip whenever the loop adds/erases elements
     while (first != v.end()) {
         // do some processing
         first = v.insert(first, 42); // insert new value
         ++first; // advance first just past the element we added
     }

9.3.4. Relational Operators

9.3.4. 关系操作符

Each container supports the relational operators (Section 5.2, p. 152) that can be used to compare two containers. The containers must be the same kind of container and must hold elements of the same type. We can compare a vector<int> only with another vector<int>. We cannot compare a vector<int> with a list<int> or a vector<double>.

所有的容器类型都支持用关系操作符（第 5.2 节）来实现两个容器的比较。显比较的容器必须具有相同的容器类型，而且其元素类型也必须相同。例如，vector<int> 容器只能与 vector<int> 容器比较，而不能与 list<int> 或 vector<int> 容器比较，而不能与 list<int> 或 vector<double> 类型的容器比较。

Comparing two containers is based on a pairwise comparison of the elements of the containers. The comparison uses the same relational operator as defined by the element type: Comparing two containers using != uses the != operator for the element type. If the element type doesn't support the operator, then the containers cannot be compared using that operator.

容器的比较是基于容器内元素的比较。容器的比较使用了元素类型定义的同一个关系操作符：两个容器做 != 比较使用了其元素类型定义的 != 操作符。如果容器的元素类型不支持某种操作符，则该容器就不能做这种比较运算。

These operators work similarly to the string relationals (Section 3.2.3, p. 85):

下面的操作类似于 string 类型的关系运算（第 3.2.3 节）：

• If both containers are the same size and all the elements are equal, then the two containers are equal; otherwise, they are unequal.

  如果两个容器具有相同的长度而且所有元素都相等，那么这两个容器就相等；否则，它们就不相等。

• If the containers have different sizes but every element of the shorter one is equal to the corresponding element of the longer one, then the shorter one is considered to be less than the other.

  如果两个容器的长度不相同，但较短的容器中所有元素都等于较长容器中对应的元素，则称较短的容器小于另一个容器。

• If neither container is an initial subsequence of the other, then the comparison depends on comparing the first unequal elements.

  如果两个容器都不是对文的初始子序列，则它们的比较结果取决于所比较的第一个不相等的元素。

The easiest way to understand these operators is by studying examples:

理解上述操作的最简单方法是研究例程：

     /*
                  ivec1: 1 3 5 7 9 12
                  ivec2: 0 2 4 6 8 10 12
                  ivec3: 1 3 9
                  ivec4: 1 3 5 7
                  ivec5: 1 3 5 7 9 12
     */
     // ivec1 and ivec2 differ at element[0]: ivec1 greater than ivec2
     ivec1 < ivec2 // false
     ivec2 < ivec1 // true

     // ivec1 and ivec3 differ at element[2]: ivec1 less than ivec3
     ivec1 < ivec3 // true

     // all elements equal, but ivec4 has fewer elements, so ivec1 is greater than ivec4
     ivec1 < ivec4 // false

     ivec1 == ivec5 // true; each element equal and same number of elements
     ivec1 == ivec4 // false; ivec4 has fewer elements than ivec1
     ivec1 != ivec4 // true; ivec4 has fewer elements than ivec1

Relational Operators Use Their Element's Relational Operator

使用元素提供的关系操作符实现容器的关系运算

We can compare two containers only if the same relational operator defined for the element types. C++ 语言只允许两个容器做其元素类型定义的关系运算。

Each container relational operator executes by comparing pairs of elements from the two containers:

所有容器都通过比较其元素对来实现关系运算：

     ivec1 < ivec2

Assuming ivec1 and ivec2 are vector<int>, then this comparison uses the built-in int less-than operator. If the vectors held strings, then the string less-than operator would be used.

假设 ivec1 和 ivec2 都是 vector<int> 类型的容器，则上述比较使用了内置 int 型定义的小于操作符。如果这两个 vector 容器存储的是 strings 对象，则使用 string 类型的小于操作符。

If the vectors held objects of the Sales_item type that we used in Section 1.5 (p. 20), then the comparison would be illegal. We did not define the relational operators for Sales_item. If we have two containers of Sales_items, we could not compare them:

如果上述 vector 容器存储 第 1.5 节定义的 Sales_item 类型的对象，则该比较运算不合法。因为 Sales_item 类型没有定义关系运算，所以不能比较存放 Sales_items 对象的容器：

     vector<Sales_item> storeA;
     vector<Sales_item> storeB;

     if (storeA < storeB) // error: Sales_item has no less-than operator

9.3.5. Container Size Operations

9.3.5. 容器大小的操作

Each container type supports four size-related operations. We used size and empty in Section 3.2.3 (p. 83): size returns the number of elements in the container; empty returns a bool that is true if size is zero and false otherwise.

所有容器类型都提供四种与容器大小相关的操作（表 9.8）第 3.2.3 节已经使用了 size 和 empty 函数：size 操作返回容器内元素的个数：empty 操作则返回一个布尔值，当容器的大小为 0 时，返回值为 true，否则为 false。

Table 9.8. Sequential Container Size Operations

表 9.8. 顺序容器的大小操作

The resize operation changes the number of elements in the container. If the current size is greater than the new size, then elements are deleted from the back of the container. If the current size is less than the new size, then elements are added to the back of the container:

容器类型提供 resize 操作来改变容器所包含的元素个数。如果当前的容器长度大于新的长度值，则该容器后部的元素会被删除；如果当前的容器长度小于新的长度值，则系统会在该容器后部添加新元素：

     list<int> ilist(10, 42);   // 10 ints: each has value 42

     ilist.resize(15);          // adds 5 elements of value 0 to back of ilist

     ilist.resize(25, -1);      // adds 10 elements of value -1 to back of ilist

     ilist.resize(5);           // erases 20 elements from the back of ilist

The resize operation takes an optional element-value argument. If this argument is present, then any newly added elements receive this value. If this argument is absent, then any new elements are value initialized (Section 3.3.1, p. 92).

resize 操作可带有一个可选的元素值形参。如果在调用该函数时提供了这个参数，则所有新添加的元素都初始化为这个值。如果没有这个参数，则新添加的元素采用值初始化（第 3.3.1 节）。

resize can invalidate iterators. A resize operation on a vector or deque potentially invalidates all iterators. resize 操作可能会使迭代器失效。在 vector 或 deque 容器上做 resize 操作有可能会使其所有的迭代器都失效。

For any container type, if resize shrinks the container, then any iterator to an element that is deleted is invalidated.

对于所有的容器类型，如果 resize 操作压缩了容器，则指向已删除的元素迭代器失效。

9.3.6. Accessing Elements

9.3.6. 访问元素

If a container is not empty, then the front and back members return references bound to the first or last elements in the container:

如果容器非空，那么容器类型的 front 和 back 成员（表 9.9）将返回容器内第一个或最后一个元素的引用：

     // check that there are elements before dereferencing an iterator
     // or calling front or back
     if (!ilist.empty()) {
         // val and val2 refer to the same element
         list<int>::reference val = *ilist.begin();
         list<int>::reference val2 = ilist.front();

         // last and last2 refer to the same element
         list<int>::reference last = *--ilist.end();
         list<int>::reference last2 = ilist.back(); }

Table 9.9. Operations to Access Elements in a Sequential Container

表 9.9. 访问顺序容器内元素的操作

This program uses two different approaches to fetch a reference to the first and last elements in ilist. The direct approach is to call front or back. Indirectly, we can obtain a reference to the same element by dereferencing the iterator returned by begin or the element one before the iterator returned by end. Two things are noteworthy in this program: The end iterator refers "one past the end" of the container so to fetch the last element we must first decrement that iterator. The other important point is that before calling front or back or dereferencing the iterators from begin or end we check that ilist isn't empty. If the list were empty all of the operations in the if would be undefined.

这段程序使用了两种不同的方法获取时 ilist 中的第一个和最后一个元素的引用。直接的方法是调用 front 或 back 函数。间接的方法是，通过对 begin 操作返回的迭代器进行解引用，或对 end 操作返回的迭代器的前一个元素位置进行解引用，来获取对同一元素的引用。在这段程序中，有两个地方值得注意：end 迭代器指向容器的超出末端的下一位置，因此必须先对其减 1 才能获取最后一个元素；另一点是，在调用 front 或 back 函数之前，或者在对 begin 或 end 返回的迭代器进行解引用运算之前，必须保证　ilist 容器非空。如果该 list 容器为空，则 if 语句内所有的操作都没有定义。

When we introduced subscripting in Section 3.3.2 (p. 94), we noted that the programmer must ensure that an element exists at the indicated subscript location. The subscript operator itself does not check. The same caution applies to using the front or back operations. If the container is empty, these operations yield an undefined result. If the container has only one element, then front and back each return a reference to that element.

第 3.3.2 节介绍了下标运算，我们注意到程序员必须保证在指定下标位置上的元素确实存在。下标操作符本身不会做相关的检查。使用 front 或 back 运算时，必须注意同样的问题。如果容器为空，那么这些操作将产生未定义的结果。如果容器内只有一个元素，则 front 和 back 操作都返回对该元素的引用。

Using a subscript that is out-of-range or calling front or back on an empty container are serious programming errors. 使用越界的下标，或调用空容器的 front 或 back 函数，都会导致程序出现严重的错误。

An alternative to subscripting is to use the at member. This function acts like the subscript operation but if the index is invalid, at throws an out_of_range exception (Section 6.13, p. 215):

使用下标运算的另一个可选方案是 at 成员函数（表 9.9）。这个函数的行为和下标运算相似，但是如果给出的下标无效，at 函数将会抛出 out_of_range 异常（第 6.13 节）：

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

9.3.7. Erasing Elements

9.3.7. 删除元素

Recall that there is both a general insert operation that inserts anywhere in the container and specific push_front and push_back operations to add elements only at the front or back. Similarly, there is a general erase and specific pop_front and pop_back operations to remove elements.

回顾前面的章节，我们知道容器类型提供了通用的 insert 操作在容器的任何位置插入元素，并支持特定的 push_front 和 push_back 操作在容器首部或尾部插入新元素。类似地，容器类型提供了通用的 erase 操作和特定的 pop_front 和 pop_back 操作来删除容器内的元素（表 9.10）。

Table 9.10. Operations to Remove Elements from a Sequential Container

表 9.10. 删除顺序容器内元素的操作

Removing the First or Last Element

删除第一个或最后一个元素

The pop_front and pop_back functions remove the first and last elements in the container. There is no pop_front operation for vectors. These operations remove the indicated element and return void.

pop_front 和 pop_back 函数用于删除容器内的第一个和最后一个元素。但 vector 容器类型不支持 pop_front 操作。这些操作删除指定的元素并返回 void。

One common use of pop_front is to use it together with front to process a container as a stack:

pop_front 操作通常与 front 操作配套使用，实现以栈的方式处理容器：

     while (!ilist.empty()) {
         process(ilist.front()); // do something with the current top of ilist
         ilist.pop_front();      // done; remove first element
     }

This loop is pretty simple: We use front to get a value to operate on and then call pop_front to remove that element from the list.

这个循环非常简单：使用 front 操作获取要处理的元素，然后调用 pop_front 函数从容器 list 中删除该元素。

The pop_front and pop_back return void; they do not return the value of the element popped. To examine that value, it is necessary to call front or back prior to popping the element. pop_front 和 pop_back 函数的返回值并不是删除的元素值，而是 void。要获取删除的元素值，则必须在删除元素之前调用 notfront 或 back 函数。

Removing an Element From within the Container

删除容器内的一个元素

The more general way to remove an element, or range of elements, is through erase. There are two versions of erase: We can delete a single element referred to by an iterator or a range of elements marked by a pair of iterators. Both forms of erase return an iterator referring to the location after the element or range that was removed. That is, if element j is the element immediately after i and we erase element i from the container, then the iterator returned will refer to j.

删除一个或一段元素更通用的方法是 erase 操作。该操作有两个版本：删除由一个迭代器指向的单个元素，或删除由一对迭代器标记的一段元素。erase 的这两种形式都返回一个迭代器，它指向被删除元素或元素段后面的元素。也就是说，如果元素 j 恰好紧跟在元素 i 后面，则将元素 i 从容器中删除后，删除操作返回指向 j 的迭代器。

As usual, the erase operations don't check their argument(s). It is up to the programmer to ensure that the iterator or iterator range is valid. 如同其他操作一样，erase 操作也不会检查它的参数。程序员必须确保用作参数的迭代器或迭代器范围是有效的。

The erase operation is often used after finding an element that should be removed from the container. The easiest way to find a given element is to use the library find algorithm. We'll see more about find in Section 11.1 (p. 392). To use find or any other generic algorithm, we must include the algorithm header. The find function takes a pair of iterators that denote a range in which to look, and a value to look for within that range. find returns an iterator referring to the first element with that value or the off-the-end iterator:

通常，程序员必须在容器中找出要删除的元素后，才使用 erase 操作。寻找一个指定元素的最简单方法是使用标准库的 find 算法。我们将在第 11.1 节中进一步讨论 find 算法。为了使用 find 函数或其他泛型算法，在编程时，必须将 algorithm 头文件包含进来。find 函数需要一对标记查找范围的迭代器以及一个在该范围内查找的值作参数。查找完成后，该函数返回一个迭代器，它指向具有指定值的第一个元素，或超出末端的下一位置。

     string searchValue("Quasimodo");
     list<string>::iterator iter =
            find(slist.begin(), slist.end(), searchValue);

     if (iter != slist.end())
          slist.erase(iter);

Note that we check that the iterator is not the end iterator before erasing the element. When we ask erase to erase a single element, the element must existthe behavior of erase is undefined if we ask it to erase an off-the-end iterator.

注意，在删除元素之前，必须确保迭代器是不是 end 迭代器。使用 erase 操作删除单个必须确保元素确实存在——如果删除指向超出末端的下一位置的迭代器，那么 erase 操作的行为未定义。

Removing All the Elements in a Container

删除容器内所有元素

To delete all the elements in a container, we could either call clear or pass the iterators from begin and end to erase:

要删除容器内所有的元素，可以调用 clear 函数，或将 begin 和 end 迭代器传递给 erase 函数。

     slist.clear(); // delete all the elements within the container
     slist.erase(slist.begin(), slist.end()); // equivalent

The iterator-pair version of erase lets us delete a subrange of elements:

erase 函数的迭代器对版本提供了删除一部分元素的功能：

     // delete range of elements between two values
     list<string>::iterator elem1, elem2;

     // elem1 refers to val1
     elem1 = find(slist.begin(), slist.end(), val1);

     // elem2 refers to the first occurrence of val2 after val1
     elem2 = find(elem1, slist.end(), val2);

     // erase range from val1 up to but not including val2
     slist.erase(elem1, elem2);

This code starts by calling find twice to obtain iterators to two elements. The iterator elem1 refers to the first occurrence of val1 or to the off-the-end iterator if val1 is not present in the list. The iterator elem2 refers to the first occurrence of val2 that appears after val1 if that element exists, otherwise, elem2 is an off the-end iterator. The call to erase removes the elements starting from the referred to by elem1 up to but not including elem2.

这段代码首先调用了 find 函数两次，以获得指向特定元素的两个迭代器。迭代器 elem1 指向第一个具有 val1 值的元素，如果容器 list 中不存在值为 val1 的元素，则该迭代器指向超出末端的下一位置。如果在 val1 元素后面存在值为 val2 的元素，那么迭代器 elem2 就指向这段范围内第一个具有 val2 值的元素，否则，elem2 就是一个超出末端的迭代器。最后，调用 erase 函数删除从迭代器 elem1 开始一直到 elem2 之间的所有元素，但不包括 elem2 指向的元素。

The erase, pop_front, and pop_back functions invalidate any iterators that refer to the removed elements. For vectors, iterators to elements after the erasure point are also invalidated. For deque, if the erase does not include either the first or last element, all iterators into the deque are invalidated. erase、pop_front 和 pop_back 函数使指向被删除元素的所有迭代器失效。对于 vector 容器，指向删除点后面的元素的迭代器通常也会失效。而对于 deque 容器，如果删除时不包含第一个元素或最后一个元素，那么该 deque 容器相关的所有迭代器都会失效。

9.3.8. Assignment and swap

9.3.8. 赋值与 swap

The assignment-related operators act on the entire container. Except for swap, they can be expressed in terms of erase and insert operations. The assignment operator erases the entire range of elements in the left-hand container and then inserts the elements of the right-hand container object into the left-hand container:

与赋值相关的操作符都作用于整个容器。除 swap 操作外，其他操作都可以用 erase 和 insert 操作实现（表 9.11）。赋值操作符首先 erases 其左操作数容器中的所有元素，然后将右操作数容器的所有元素 inserts 到左边容器中：

     c1 = c2; // replace contents of c1 with a copy of elements in c2
     // equivalent operation using erase and insert
     c1.erase(c1.begin(), c1.end()); // delete all elements in c1
     c1.insert(c1.begin(), c2.begin(), c2.end()); // insert c2

After the assignment, the left- and right-hand containers are equal: Even if the containers had been of unequal size, after the assignment both containers have the size of the right-hand operand.

赋值后，左右两边的容器相等：尽管赋值前两个容器的长度可能不相等，但赋值后两个容器都具有右操作数的长度。

Assignment and the assign operations invalidate all iterators into the left-hand container. swap does not invalidate iterators. After swap, iterators continue to refer to the same elements, although those elements are now in a different container. 赋值和 assign 操作使左操作数容器的所有迭代器失效。swap 操作则不会使迭代器失效。完成 swap 操作后，尽管被交换的元素已经存放在另一容器中，但迭代器仍然指向相同的元素。

Table 9.11. Sequential Container Assignment Operations

表 9.11. 顺序容器的赋值操作

Using assign

使用 assign

The assign operation deletes all the elements in the container and then inserts new elements as specified by the arguments. Like the constructor that copies elements from a container, the assignment operator (=) can be used to assign one container to another only if the container and element type are the same. If we want to assign elements of a different but compatible element type and/or from a different container type, then we must use the assign operation. For example, we could use assign to assign a range of char* values from a vector into a list of string.

assign 操作首先删除容器中所有的元素，然后将其参数所指定的新元素插入到该容器中。与复制容器元素的构造函数一样，如果两个容器类型相同，其元素类型也相同，就可以使用赋值操作符（=）将一个容器赋值给另一个容器。如果在不同（或相同）类型的容器内，元素类型不相同但是相互兼容，则其赋值运算必须使用 assign 函数。例如，可通过 assign 操作实现将 vector 容器中一段 char* 类型的元素赋给 string 类型 list 容器。

Because the original elements are deleted, the iterators passed to assign must not refer to elements in the container on which assign is called. 由于 assign 操作首先删除容器中原来存储的所有元素，因此，传递给 assign 函数的迭代器不能指向调用该函数的容器内的元素。

The arguments to assign determine how many elements are inserted and what values the new elements will have. This statement:

assign 函数的参数决定了要插入多少个元素以及新元素的值是什么。语句

     // equivalent to slist1 = slist2
     slist1.assign(slist2.begin(), slist2.end());

uses the version of assign that takes a pair of iterators. After deleting the elements in slist1, the function copies the elements in the range denoted by the iterators into slist2. Thus, this code is equivalent to assigning slist2 to slist1.

使用了带一对迭代器参数的 assign 函数版本。在删除 slist1 的元素后，该函数将 slist2 容器内一段指定的元素复制到 slist2 中。于是，这段代码行等效于将 slist1 赋给 slist1。

The assign operator that takes an iterator pair lets us assign elements of one container type to another. 带有一对迭代器参数的 assign 操作允许我们将一个容器的元素赋给另一个不同类型的容器。

A second version of assign takes an integral value and an element value. It replaces the elements in the container by the specified number of elements, each of which has the specified element value

assign 运算的第二个版本需要一个整型数值和一个元素值做参数，它将容器重置为存储指定数量的元素，并且每个元素的值都为指定值：

     // equivalent to: slist1.clear();
     // followed by slist1.insert(slist1.begin(), 10, "Hiya!");
     slist1.assign(10, "Hiya!"); // 10 elements; each one is Hiya!

After executing this statement, slist1 has 10 elements, each of which has the value Hiya!.

执行了上述语句后，容器 slist1 有 10 个元素，每个元素的值都是 Hiya!。

Using swap to Avoid the Cost of Deleting Elements

使用 swap 操作以节省删除元素的成本

The swap operation swaps the values of its two operands. The types of the containers must match: The operands must be the same kind of container, and they must hold values of the same type. After the call to swap, the elements that had been in the right-hand operand are in the left, and vice versa:

swap 操作实现交换两个容器内所有元素的功能。要交换的容器的类型必须匹配：操作数必须是相同类型的容器，而且所存储的元素类型也必须相同。调用了 swap 函数后，右操作数原来存储的元素被存放在左操作数中，反之亦然。

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

After the swap, svec1 contains 24 string elements and svec2 contains 10.

执行 swap 后，容器 svec1 中存储 24 个 string 类型的元素，而 svec2 则存储 10 个元素。

The important thing about swap is that it does not delete or insert any elements and is guaranteed to run in constant time. No elements are moved, and so iterators are not invalidated. 关于 swap 的一个重要问题在于：该操作不会删除或插入任何元素，而且保证在常量时间内实现交换。由于容器内没有移动任何元素，因此迭代器不会失效。

The fact that elements are not moved means that iterators 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 container. For example, had iter referred to the string at position svec1[3] before the swap it will refer to the element at position svec2[3] after the swap.

没有移动元素这个事实意味着迭代器不会失效。它们指向同一元素，就像没作 swap 运算之前一样。虽然，在 swap 运算后，这些元素已经被存储在不同的容器之中了。例如，在做 swap 运算之前，有一个迭代器 iter 指向 svec1[3] 字符串；实现 swap 运算后，该迭代器则指向 svec2[3] 字符串（这是同一个字符串，只是存储在不同的容器之中而已）。