Skip to content

Latest commit

 

History

History
807 lines (548 loc) · 38.6 KB

57.md

File metadata and controls

807 lines (548 loc) · 38.6 KB
Raw

五十七、容器

到目前为止，您使用的唯一标准容器是vector和map。我在探索 9 和探索 46 中提到过array但从未深入。这个探索介绍了剩余的容器，并讨论了容器的一般性质。当第三方库实现附加容器时，它们通常遵循标准库设置的模式，并使它们的容器遵循相同的要求。

容器的属性

容器类型实现了熟悉的数据结构，比如树、列表、数组等等。它们都有一个共同的目的，即在一个容器对象中存储一组相似的对象。您可以将容器视为单个实体:比较、复制、分配等等。您还可以访问容器中的单个项目。一种容器类型与另一种容器类型的区别在于容器在其中存储项目的方式，这反过来会影响访问和修改容器中项目的速度。

标准容器分为两大类:顺序容器和关联容器。不同之处在于，您可以控制序列容器中的项目顺序，但不能控制关联容器中的项目顺序。因此，关联容器为访问和修改其内容提供了改进的性能。标准的序列容器有array(固定大小)deque(双端队列)forward_list(单链表)list(双链表)vector(变长数组)。forward_list类型的工作方式不同于其他容器(由于单链表的性质),它是专门用于特殊用途的。本书不涉及forward_list，但你可以在任何 C++ 参考资料中找到。

关联容器有两个子类别:有序的和无序的。有序容器按照数据相关的顺序存储键，这是由<操作符或调用者提供的仿函数给出的。尽管该标准没有指定任何特定的实现，但复杂性要求很大程度上要求有序关联容器作为平衡二叉树来实现。无序容器将键存储在哈希表中，因此顺序对您的代码来说并不重要，并且会随着您向容器中添加项而发生变化。

划分关联容器的另一种方法是划分为集合和贴图。集合就像数学集合:它们有成员，并且可以测试成员资格。映射就像存储键/值对的集合。集合和映射可能需要唯一的关键字，也可能允许重复的关键字。集合类型有set(唯一键，已排序)multiset(重复键，已排序)unordered_set和unordered_multiset。映射类型有map、multimap、unordered_map和unordered_multimap。

不同的容器有不同的特性。例如，vector允许快速访问任何项目，但在中间插入会很慢。另一方面，list提供了对任何项目的快速插入和删除，但只提供双向迭代器，不提供随机访问。

C++ 标准根据复杂性来定义容器特征，复杂性是用 big-O 符号写的。请记住，在你的算法入门课程中， O (1)是常量复杂度，但没有任何常量可能是什么的指示。 O ( n )是线性复杂度:如果容器有 n 个项目，执行一次 O ( n )操作所花费的时间与 n 成正比。对排序数据的操作往往是对数的: O (log n )。

表 57-1 总结了所有的容器及其特性。插入、删除和查找列显示了这些操作的平均复杂度，其中 N 是容器中元素的数量。查找序列容器意味着查找特定索引处的项目。对于关联容器，这意味着通过值查找特定的项。“否”表示容器根本不支持该操作。

表 57-1。

集装箱及其特征概述

|

类型

|

页眉

|

插入

|

抹去

|

检查

|

迭代程序

| | --- | --- | --- | --- | --- | --- | | array | <array> | 不 | 不 | O① | 接触的 | | deque | <deque> | O ( N )* | O ( N )* | O① | 随机存取 | | forward_list | <forward_list> | O① | O① | O ( N | 向前 | | list | <list> | O① | O① | O ( N | 双向的 | | map | <map> | O (日志 N | O (日志 N | O (日志 N | 双向的 | | multimap | <map> | O (日志 N | O (日志 N | O (日志 N | 双向的 | | multiset | <set> | O (日志 N | O (日志 N | O (日志 N | 双向的 | | set | <set> | O (日志 N | O (日志 N | O (日志 N | 双向的 | | unordered_map | <unordered_map> | O① | O① | O① | 向前 | | unordered_multimap | <unordered_map> | O① | O① | O① | 向前 | | unordered_multiset | <unordered_set> | O① | O① | O① | 向前 | | unordered_set | <unordered_set> | O① | O① | O① | 向前 | | vector | <vector> | O ( N )* | O ( N )* | O① | 接触的 |

*** 复杂度在容器中间插入和擦除为 O(N)但在容器末端为 O(1)，当在许多操作中摊销时。deque 还允许在容器的开头进行摊销的 O(1)插入和擦除。

成员类型

每个容器都提供了许多有用的类型和类型定义作为容器的成员。本节经常使用其中的几个:

值类型

这是容器存储的类型的同义词。例如，vector<double>的value_type是double，std::list<char>::value_type是char。使用标准成员类型使得编写和读取容器代码更加容易。本探索的其余部分广泛使用了value_type。

映射的容器存储键/值对，所以map<Key, T>(以及multimap、unordered_map和unordered_multimap)的value_type是std::pair<const Key, T>。关键字类型是const，因为在向关联容器添加一个项目后，您不能更改关键字。容器的内部结构取决于键，因此更改键会违反排序约束。

密钥类型

关联容器将key_type声明为第一个模板参数的 typedef 例如，map<int, double>::key_type是int。对于器械包类型，key_type和value_type相同。

参考

这是引用value_type的同义词。除了极少数情况，reference与value_type&相同。

常量 _ 引用

const_reference是引用const value_type的同义词。除了极少数情况，const_reference与value_type const&完全相同。

迭代程序

这是迭代器类型。它可能是 typedef，但更有可能是一个类，其定义是依赖于实现的。重要的是这种类型满足迭代器的要求。每个容器类型实现一个特定的迭代器类别，如表 57-1 所述。

常量迭代器

const_iterator是const项的迭代器类型。它可能是 typedef，但更有可能是一个类，其定义是依赖于实现的。重要的是这种类型符合const项的迭代器的要求。每个容器类型实现一个特定的迭代器类别，如表 57-1 所述。

尺寸 _ 类型

size_type是内置整数类型之一的 typedef(具体是哪种取决于实现)。它表示序列容器或容器大小的索引。

什么可以放进集装箱

为了在容器中存储项目，项目的类型必须满足一些基本要求。您必须能够复制或移动项目，并使用复制或移动来指定它。对于内置类型，这是自动的。对于一个类类型，你通常有这个能力。编译器甚至为您编写了构造器和赋值操作符。到目前为止，本书中的所有类都满足基本要求；在探索之前，你不必关心不一致的类。

序列容器本身不必比较项目是否相等；他们只是根据需要复制或移动元素。当他们不得不复印时，他们认为复印件和原件是一样的。

有序关联容器需要一个排序函子。默认情况下，它们使用一个名为std::less<key_type>的标准仿函数，该仿函数又使用<操作符。你可以提供一个定制的仿函数，只要它实现了严格弱排序，它由以下需求定义:

  • 如果 a < b 和b<T6】c，那么 a < c 。

  • 一个 <一个一个总是假的。

  • 项目存储在容器中后，顺序不会改变。

新 C++ 程序员的一个常见错误是违反规则 2，通常是通过实现<=而不是<。违反严格的弱排序规则会导致未定义的行为。一些库有一个调试模式，检查你的仿函数以确保它是有效的。如果你的库有这样的模式，使用它。

无序关联容器需要一个散列函子和一个相等函子。默认的哈希函子是std::hash<key_type>(在<functional>中声明)。标准库为内置类型和string提供了特化。如果你在一个无序的容器中存储一个定制类，你必须提供你自己的散列函子。最简单的方法就是特化hash。清单 57-1 展示了如何将hash特化为rational类型。您只需提供函数调用操作符，该操作符必须返回类型std::size_t(一个实现定义的整数类型)。

import <functional>;
import rational;
namespace std {

template<class T>
class hash<rational<T>>
{
public:
  std::size_t operator()(rational<T> const& r)
  const
  {
    return hasher_(r.numerator() * r.denominator());
  }
private:
  std::hash<T> hasher_;
};
} // end of std

Listing 57-1.Specializing the hash Template for the rational Type

尽管标准库为所有内置类型提供了一个std::hash<>特化，但它没有提供任何有效的方法来组合多个哈希值。清单 57-1 中显示的方法没有给出好的结果。(例如，1/2 和 2 共享相同的哈希值。)但是编写有效的哈希函数不在本书的讨论范围之内；有关编写更好的散列函数的信息，请访问该书的网站。

默认的等式仿函数是std::equal_to<T>(在<functional>中声明)，它使用了==操作符。如果两个项目相等，它们的哈希值也必须相等(但反过来就不一定了)。

当您在容器中插入项目时，容器会保留该项目的副本，或者您可以将对象移动到容器中。当您抹掉一个项目时，容器会销毁该项目。当你破坏一个容器时，它破坏了它的所有元素。下一节将详细讨论插入和擦除。

插入和擦除

我已经展示了一些在矢量和映射中插入和删除元素的例子。本节将更深入地探讨这个主题。除了array和forward_list之外，容器类型遵循一些基本模式。array类型的大小是固定的，所以它不提供插入或擦除功能。而forward_list有自己的做法，因为单链表不能直接插入或擦除项。所有其他容器都遵循本节中描述的规范。

在序列容器中插入

您可以选择几个成员函数来将项目插入到序列容器中。最基本的函数是emplace，它在容器中构造一个条目。它具有以下形式:

  • 迭代器就位(此处 const_iterator，args...)

  • 将一个新构造的项插入到集合中的位置here之前，并返回一个指向新添加项的迭代器。args可以是零个或多个传递给value_type构造器的参数。如果here是end()，则在容器的末尾构造项目。

  • 参考就位 _ 返回(args...)

  • 将新构造的项追加到集合中，并返回对该构造项的引用。args可以是零个或多个传递给value_type构造器的参数。允许快速插入集装箱前端的集装箱(deque、list)还有emplace_front()。

如果有已经构造好的对象，调用insert，它有四种重载形式:

  • 迭代器插入(这里是 const_iterator，value_type item)

  • 通过将item复制或移动到集合中紧靠位置here之前的位置来插入它，并返回一个引用新添加的项的迭代器。如果here是end()，那么item被追加到容器的末尾。

  • 迭代器插入(这里是 const_iterator，size_type n，value_type const &项)

  • 在here引用的位置之前插入item的副本n。如果here是end()，则项目被追加到容器的末尾。返回第一个插入项的迭代器。

  • 迭代器插入(这里是 const_iterator，STD::initializer _ listbrace _ enclosed _ list)

  • 初始化列表是花括号中的值列表。编译器构造一个值范围，这个函数将这些值复制到容器中，从紧接在here之前的位置开始。返回第一个插入项的迭代器。

  • 模板<类输入器>T1】

    迭代器插入(这里是 const_iterator，首先是 InputIterator，最后是 input iterator)

  • 从紧接在here之前的位置开始，将范围first、last中的值复制到容器中。返回第一个插入项的迭代器。

从序列容器中擦除

函数的作用是擦除或删除容器中的项目。序列容器实现了两种形式的erase:

  • 迭代器擦除(const_iterator pos)

  • 删除pos引用的项目，并返回一个引用后续项目的迭代器。如果最后一项被删除，则返回end()。如果你试图删除end()或者pos是一个不同容器对象的迭代器，行为是未定义的。

  • 迭代器擦除(const_iterator first，const_iterator last)

  • 删除范围[ first，last]中的所有项，并返回一个迭代器，该迭代器指向紧跟在最后一个被删除项之后的项。如果容器中的最后一项被删除，则返回end()。如果迭代器顺序错误或者引用了不同的容器对象，则行为是未定义的。

函数从容器中删除所有元素。除了基本的擦除功能，序列容器还提供pop_front来擦除集合的第一个元素，提供pop_back来擦除集合的最后一个元素。只有当容器能够以恒定的复杂性实现这两个功能时，它才能实现这两个功能。哪些序列容器实现了 pop_back ？

哪些序列容器实现了 pop_front ？

与就位功能一样，vector提供pop_back,list和deque同时提供pop_back和pop_front。

在关联容器中插入

关联容器的所有插入函数都遵循返回类型的通用模式。重复键容器(multimap、multiset、unordered_multimap、unordered_multiset)为新添加的项返回一个迭代器。唯一键容器(map、set、unordered_map、unordered_set)返回一个pair<iterator, bool>:迭代器引用容器中的项目，如果项目被添加，则bool为 true，如果项目已经存在，则bool为 false。在本节中，返回类型显示为返回。如果该项目已经存在，则现有项目保持不变，新项目被忽略。

通过调用两个定位函数之一，在关联容器中构造一个新项:

  • 返回 emplace(args...)

  • 在容器中的正确位置构造一个新元素，将args传递给value_type构造器。

  • iterator emplace_hint(iterator hint, args...)

  • 构造一个尽可能靠近hint的新元素，将args传递给value_type构造器。

  • 对于有序容器，如果该项的位置紧接在hint之后，则该项以恒定的复杂度添加。否则复杂度是对数的。如果您必须在一个有序容器中存储许多项，并且这些项已经按顺序排列，那么您可以通过使用最近插入的项的位置作为提示来节省一些时间。

与序列容器一样，您也可以调用insert函数来插入到关联容器中。与序列容器的一个关键区别是，您不必提供位置(有一种形式允许您提供位置作为提示)。

  • 返回 插入(value_type 项)

  • 将item移动或复制到容器中。

  • 迭代器插入(const_iterator 提示，value_type 项)

  • 将item移动或复制到尽可能靠近hint的容器中，如前面关于emplace_hint的描述。

  • 模板<类输入器>T1】

    void insert(先输入，后输入)

  • 将范围[ first，last]中的值复制到容器中。对于有序容器，如果范围[ first，last]已经排序，您将获得最佳性能。同样，没有范围形式的插入。

写一个程序，从标准输入中读取一串字符串到一组字符串中。使用emplace_hint功能。保存返回值，以便在插入下一项时作为提示传递。找到一个大的字符串列表作为输入。将列表复制两份，一份按排序顺序，一份按随机顺序。(如果您需要帮助查找或准备输入文件，请访问本书的网站。)比较你的程序读取两个输入文件的性能。

编写相同程序的另一个版本，这次使用简单的单参数 emplace function **。**再次用两个输入文件运行程序。比较所有四种变体的性能:有提示的和无提示的插入，排序的和未排序的输入。

清单 57-2 显示了使用emplace_hint的程序的简单形式。

import <iostream>;
import <set>;
import <string>;

int main()
{
  std::set<std::string> words{};

  std::set<std::string>::iterator hint{words.begin()};
  std::string word{};
  while(std::cin >> word)
    hint = words.emplace_hint(hint, std::move(word));

  std::cout << "stored " << words.size() << " unique words\n";
}

Listing 57-2.Using a Hint Position when Inserting into a Set

当我用一个超过 200，000 字的文件运行程序时，带有排序输入的提示程序在大约 1.6 秒内执行。未打印的表格需要 2.2 秒。在随机输入的情况下，两个程序的运行时间约为 2.3 秒。正如您所看到的，当输入已经排序时，提示会产生影响。细节取决于库的实现；您的里程可能会有所不同。

基于节点的容器(set、map、list、multiset和multimap)允许您从一个容器中提取节点，并将它们添加到另一个容器中。有关这些高级功能的详细信息，请参考语言参考。

从关联容器中擦除

函数的作用是擦除或删除容器中的项目。关联容器实现了三种形式的erase:

  • 迭代器擦除(const_iterator pos)

  • 删除pos所指的项目；复杂性是不变的，可能会分摊到许多调用中。返回一个引用后继值的迭代器(或end())。如果pos不是容器的有效迭代器，那么行为是未定义的。

  • 迭代器擦除(const_iterator first，const_iterator last)

  • 擦除范围[ first、last]中的所有项目。返回一个迭代器，该迭代器指向最后一个被擦除项之后的项。如果容器中的最后一项被删除，则返回end()。如果[ first，last]不是容器的有效迭代器范围，则行为未定义。

  • 迭代器擦除(value_type const &值)

  • 从容器中删除所有出现的value。返回擦除的项目数，可以为零。

与序列容器一样，clear()删除容器中的所有元素。

例外

如果抛出异常，容器会尽力保持秩序。异常有两个潜在的来源:容器本身和容器中的项目。大多数成员函数不会抛出无效参数的异常，所以如果容器内存不足，无法插入新项，容器本身的异常最常见的来源是std::bad_alloc。

如果您尝试将单个项插入到容器中，并且操作失败(可能是因为该项的复制构造器引发了异常，或者容器内存不足)，则容器保持不变。

如果您尝试插入多个项，并且其中一个项在插入容器时引发异常(例如，该项的复制构造器引发异常)，大多数容器不会回滚更改。只有list和forward_list类型回滚到它们的原始状态。其他容器以有效状态离开容器，并且已经成功插入的项目保留在容器中。

当删除一个或多个项目时，容器本身不会抛出异常，但是它们可能必须移动(或者在有序容器的情况下，比较)项目；如果一个项目的移动构造器抛出异常(极不可能的事件)，擦除可能是不完整的。但是，无论如何，容器都保持有效状态。

为了使这些保证保持有效，析构函数不能抛出异常。

Tip

永远不要从析构函数中抛出异常。

迭代器和引用

使用容器时，我还没有提到的一个要点是迭代器和引用的有效性。问题是，当您在容器中插入或删除项目时，该容器的部分或全部迭代器可能会无效，并且对容器中项目的引用可能会无效。哪些迭代器和引用无效以及在什么情况下无效的细节取决于容器。

迭代器和引用失效反映了容器的内部结构。例如，vector将其元素存储在一个连续的内存块中。因此，插入或删除任何元素都会移动更高索引处的所有元素，这将使更高索引处的所有迭代器和对这些元素的引用无效。随着一个vector的增长，它可能不得不分配一个新的内部数组，这将使那个vector的所有现存迭代器和引用失效。您永远不知道什么时候会发生这种情况，所以在向vector添加项目时，最安全的做法是永远不要保留vector的迭代器或引用。(但是如果您必须保留这些迭代器和引用，请在库引用中查找reserve成员函数。)

另一方面，list实现了一个双向链表。插入或删除一个元素只是插入或删除一个节点，对迭代器和对其他节点的引用没有影响。对于所有容器，如果你删除一个迭代器引用的节点，这个迭代器必然会失效，就像对被删除元素的引用必然会失效一样。

实际上，插入和删除元素时必须小心。这些函数通常返回迭代器，您可以用它们来帮助维护程序的逻辑。清单 57-3 显示了一个函数模板erase_unsorted，它遍历一个容器并为任何大于其前面值的元素调用erase。它是一个函数模板，可以处理任何满足序列容器要求的类。

template<class Container>
void erase_unsorted(Container& cont)
{
  auto prev{cont.end()};
  auto next{cont.begin()};
  while (next != cont.end())
  {
    // invariant: std::is_sorted(cont.begin(), prev);
    if (prev != cont.end() and *next < *prev)
      next = cont.erase(next);
    else
    {
      prev = next;
      ++next;
    }
  }
}

Listing 57-3.Erasing Elements from a Sequence Container

注意erase_less如何在容器中移动迭代器iter。prev迭代器引用前一项(或者container.end()，当循环第一次开始并且没有前一项时)。只要*prev小于*iter，就通过将prev设置为iter并增加iter来推进循环。如果容器按升序排列，则不会发生任何变化。然而，如果项目不在适当的位置，则*prev < *iter为假，并且位置iter处的项目被擦除。erase返回的值是一个迭代器，该迭代器引用了iter被擦除之前的项。这正是我们想要iter指向的地方，所以我们只需将iter设置为返回值，并让循环继续。

编写一个测试程序，看看 erase_unsorted **如何处理一个列表和一个向量。确保它适用于升序数据、降序数据和混合数据。**清单 57-4 显示了我的简单测试程序。

import <algorithm>;
import <iostream>;
import <initializer_list>;
import <iterator>;
import <ranges>;
import <vector>;

import erase_unsorted; // Listing 57-3

/// Print items from a container to the standard output.
template<class Container>
requires std::ranges::range<Container>
void print(std::string const& label, Container const& container)
{
  std::cout << label;
  using value_type = std::ranges::range_value_t<Container>;
  std::ranges::copy(container,
       std::ostream_iterator<value_type>(std::cout, " "));
  std::cout << '\n';
}

/// Test erase_unsorted by extracting integers from a string into a container
/// and calling erase_unsorted. Print the container before and after.
/// Double-check that the same results obtain with a list and a vector.
void test(std::initializer_list<int> numbers)
{
  std::vector<int> data{numbers};
  erase_unsorted(data);
  if (not std::is_sorted(data.begin(), data.end()))
      print("FAILED", data);
}

int main()
{
  test({2, 3, 7, 11, 13, 17, 23, 29, 31, 37});
  test({37, 31, 29, 23, 17, 13, 11, 7, 3, 2});
  test({});
  test({42});
  test({10, 30, 20, 40, 0, 50});
}

Listing 57-4.Testing the erase_unsorted Function Template

erase_unsorted函数的净效果是让容器保持有序。所以test()函数调用std::is_sorted来验证这个函数确实被排序了。如果没有，它会打印一条消息和一个用于调试的数字列表。这些测试包括已经按顺序排列的数字序列(包括一元序列和空序列)、逆序序列和混合序列。

序列容器

在本书中，容器最常见的用法是在vector的末尾添加条目。然后，程序可能会使用标准算法来改变顺序，比如按升序排序、按随机顺序洗牌等等。除了vector，其他的序列容器还有array、deque和list。

序列容器的主要区别在于它们的复杂性特征。如果你经常需要从序列中间插入和删除，你可能需要list。如果只需插入和擦除一端，使用vector。如果容器的大小是一个固定的编译时常量，使用array。如果序列的元素必须连续存储(在单个内存块中)，使用array或vector。

以下各节包括了关于每种容器类型的更多细节。每个部分都提供了相同的程序进行比较。该程序构建一副扑克牌，然后随机选择一张牌给自己，一张牌给你。价值最高的牌获胜。程序播放十次，然后退出。该程序无需替换即可玩，也就是说，它不会在每次游戏结束后将用过的牌放回牌堆。为了随机挑选一张牌，程序使用了清单 45-5 中的randomint类。将类别定义保存在名为randomint.hpp的文件中，或者从书籍网站下载该文件。清单 57-5 显示了示例程序使用的card类。关于完整的类定义，请从该书的网站下载card.hpp。

export module cards;
import <iosfwd>;

/// Represent a standard western playing card.
export class card
{
public:
  using suit = char;
  static constexpr suit const spades   {4};
  static constexpr suit const hearts   {3};
  static constexpr suit const clubs    {2};
  static constexpr suit const diamonds {1};

  using rank = char;
  static constexpr rank const ace   {14};
  static constexpr rank const king  {13};
  static constexpr rank const queen {12};
  static constexpr rank const jack  {11};

  constexpr card() : rank_{0}, suit_{0} {}
  constexpr card(rank r, suit s) : rank_{r}, suit_{s} {}

  constexpr void assign(rank r, suit s);
  constexpr suit get_suit() const { return suit_; }
  constexpr rank get_rank() const { return rank_; }
private:
  rank rank_;
  suit suit_;
};

export bool operator==(card a, card b);
export bool operator!=(card a, card b);
export std::ostream& operator<<(std::ostream& out, card c);
export std::istream& operator>>(std::istream& in, card& c);

/// In some games, Aces are high. In other Aces are low. Use different
/// comparison functors depending on the game.
export bool acehigh_less(card a, card b);
export bool acelow_less(card a, card b);

/// Generate successive playing cards, in a well-defined order,
/// namely, 2-10, J, Q, K, A. Diamonds first, then Clubs, Hearts, and Spades.
/// Roll-over and start at the beginning again after generating 52 cards.
export class card_generator
{
public:
  card_generator();
  card operator()();
private:
  card card_;
}

;

Listing 57-5.The card Class, to Represent a Playing Card

数组类模板

array类型是固定大小的容器，所以不能调用insert或erase。要使用array，请将基本类型和大小指定为编译时常量表达式，如下所示:

std::array<double, 5> five_elements;

如果用比数组大小更少的值初始化数组，剩余的值将被初始化为零。如果完全省略了初始值设定项，如果值类型是类类型，编译器将调用默认初始值设定项；否则，它保持数组元素未初始化。因为一个数组不能改变大小，所以你不能在玩完牌后简单地把牌擦掉。为了保持代码简单，程序会在每次游戏结束后将卡片放回卡片组。清单 57-6 显示了替换的大牌程序。

import <algorithm>;
import <array>;
import <iostream>;

import card;
import randomint; // Listing 45-5

int main()
{
  std::array<card, 52> deck;
  std::ranges::generate(deck, card_generator{});

  randomint picker{0, deck.size() - 1};
  for (int i{0}; i != 10; ++i)
  {
    card const& computer_card{deck.at(picker())};
    std::cout << "I picked " << computer_card << '\n';

    card const& user_card{deck.at(picker())};
    std::cout << "You picked " << user_card << '\n';

    if (acehigh_less(computer_card, user_card))
      std::cout << "You win.\n";
    else
      std::cout << "I win.\n";
  }
}

Listing 57-6.Playing High-Card with array

deque 类模板

一个deque(读作“deck”)代表一个双端队列。从开头或结尾插入和删除速度很快，但是如果必须在其他地方插入或删除，复杂度是线性的。大多数时候，你可以像使用vector一样使用deque，所以应用你使用 vector **的经验来编写大牌程序。**不替换玩法:即每局游戏结束后，通过将两张牌从容器中擦除的方式将其丢弃。清单 57-7 展示了我如何使用deque编写大牌程序。

import <algorithm>;
import <deque>;
import <iostream>;

import card;
import randomint;

int main()
{
  std::deque<card> deck(52);
  std::ranges::generate(deck, card_generator{});

  for (int i{0}; i != 10; ++i)
  {
    auto pick{deck.begin() + randomint{0, deck.size()-1}()};
    card computer_card{*pick};
    deck.erase(pick);

    std::cout << "I picked " << computer_card << '\n';

    pick = deck.begin() + randomint{0, deck.size() - 1}();
    card user_card{*pick};
    deck.erase(pick);

    std::cout << "You picked " << user_card << '\n';

    if (acehigh_less(computer_card, user_card))
      std::cout << "You win.\n";
    else
      std::cout << "I win.\n";
  }
}

Listing 57-7.Playing High-Card with a deque

列表类模板

一个list代表一个双向链表。在列表中的任何点插入和擦除都很快，但不支持随机访问。因此，high-card 程序使用迭代器和advance函数(探索 46 )。编写高卡程序使用 list 。将你的解决方案与清单 57-8 中我的解决方案进行比较。

import <algorithm>;
import <iostream>;
import <list>;

import card;
import randomint;

int main()
{
  std::list<card> deck(52);
  std::ranges::generate(deck, card_generator{});

  for (int i{0}; i != 10; ++i)
  {
    auto pick{deck.begin()};
    std::advance(pick, randomint{0, deck.size() - 1}());
    card computer_card{*pick};
    deck.erase(pick);

    std::cout << "I picked " << computer_card << '\n';

    pick = std::next(deck.begin(), randomint{0, deck.size() - 1}());
    card user_card{*pick};
    deck.erase(pick);

    std::cout << "You picked " << user_card << '\n';

    if (acehigh_less(computer_card, user_card))
      std::cout << "You win.\n";
    else
      std::cout << "I win.\n";
  }
}

Listing 57-8.Playing High-Card with a list

deque类型支持随机访问迭代器，所以它可以给begin()加一个整数来挑选一张牌。但是list使用双向迭代器，所以必须调用advance()或者next()；清单 57-8 展示了这两者。注意，您也可以为deque s 调用advance()或next()，并且实现仍然使用加法。

vector 类模板

vector是一个可以在运行时改变大小的数组。追加到末尾或从末尾擦除速度很快，但在矢量中的任何其他位置插入或擦除时，复杂度是线性的。对比 deque 和 list 版本的高卡程序。选择您喜欢的一个并修改它以与 vector 一起工作。清单 57-9 中显示了我的程序版本。

import <algorithm>;
import <iostream>;
import <vector>;

import card;
import randomint;

int main()
{
  std::vector<card> deck(52);
  std::ranges::generate(deck, card_generator{});

  for (int i{0}; i != 10; ++i)
  {
    auto pick{deck.begin() + randomint{0, deck.size()-1}()};
    card computer_card{*pick};
    deck.erase(pick);

    std::cout << "I picked " << computer_card << '\n';

    pick = deck.begin() + randomint{0, deck.size() - 1}();
    card user_card{*pick};
    deck.erase(pick);

    std::cout << "You picked " << user_card << '\n';

    if (acehigh_less(computer_card, user_card))
      std::cout << "You win.\n";
    else
      std::cout << "I win.\n";
  }
}

Listing 57-9.Playing High-Card with vector

注意你如何改变程序来使用vector而不是deque，仅仅通过改变类型名。它们的用法非常相似。一个关键的区别是deque在容器的开头提供快速(恒定复杂度)插入，这是vector所缺乏的。另一个关键区别是vector支持连续迭代器，而 deque 使用随机访问迭代器。这两个因素在这里都不重要。

关联容器

关联容器通过控制容器中元素的顺序来提供快速插入、删除和查找。有序关联容器将元素存储在树中，由比较仿函数(默认为std::less，它使用<)排序，因此插入、删除和查找以对数复杂度发生。无序容器使用哈希表(根据调用者提供的哈希函子和等式函子)进行访问，在一般情况下具有恒定的复杂性，但在最坏情况下具有线性复杂性。有关树和散列表的更多信息，请查阅任何关于数据结构和算法的教科书。

设置存储键，并映射存储键/值对。多重集和多重映射允许重复键。所有等价密钥都存储在容器中的相邻位置。普通集合和映射需要唯一的键。如果您尝试插入容器中已经存在的密钥，则不会插入新密钥。请记住，有序容器中的等价仅由调用比较函子来确定:compare(a, b)为假，compare(b, a)为假意味着a和b等价。

无序容器调用它们的相等函子来确定一个键是否重复。默认为std::equal_to(在<functional>中声明)，使用==操作符。

因为关联数组存储键的顺序取决于键的内容，所以不能修改存储在关联容器中的键的内容。这意味着你不能使用关联容器的迭代器作为输出迭代器。因此，如果您想使用关联容器实现 high-card 程序，您可以使用inserter函数创建一个填充容器的输出迭代器。清单 57-10 展示了如何使用set来实现高卡程序。

import <algorithm>;
import <iostream>;
import <iterator>;
import <set>;
import <utility>;

import card;
import randomint;

int main()
{
  using cardset = std::set<card, std::function<bool(card, card)>>;
  cardset deck(acehigh_less);
  std::generate_n(std::inserter(deck, deck.begin()), 52, card_generator{});

  for (int i{0}; i != 10; ++i)
  {
    auto pick{deck.begin()};
    std::advance(pick, randomint{0, deck.size() - 1}());
    card computer_card{*pick};
    deck.erase(pick);

    std::cout << "I picked " << computer_card << '\n';

    pick = deck.begin();
    std::advance(pick, randomint{0, deck.size() - 1}());
    card user_card{*pick};
    deck.erase(pick);

    std::cout << "You picked " << user_card << '\n';

    if (acehigh_less(computer_card, user_card))
      std::cout << "You win.\n";
    else
      std::cout << "I win.\n";
  }
}

Listing 57-10.Playing High-Card with set

使用关联容器时，当您使用自定义比较仿函数(对于有序容器)或自定义相等和散列仿函数(对于无序容器)时，可能会遇到一些困难。您必须将函子类型指定为模板参数。构造容器对象时，将仿函数作为参数传递给构造器。函子必须是您在模板特化中指定的类型的实例。

例如，清单 57-10 使用了acehigh_less函数，并将其传递给deck的构造器。因为acehigh_less是一个函数，所以必须指定一个函数类型作为模板参数。声明函数类型最简单的方法是使用std::function模板。模板参数看起来有点像一个无名的函数头—提供返回类型和参数类型:

std::function<bool(card, card)>

另一种方法是特化类型card的std::less类模板。显式特化将实现函数调用操作符来调用acehigh_less。利用特化，您可以使用默认的模板参数和构造器参数。遵循<functional>标题中的函子模式。函子应该提供一个函数调用操作符，该操作符使用参数和返回类型，并为容器实现严格的弱排序函数。清单 57-11 展示了另一个版本的大牌程序，这次使用了less的特化。唯一真正的区别是如何初始化甲板。

import <algorithm>;
import <functional>;
import <iostream>;
import <iterator>;
import <set>;

import card;
import randomint;

namespace std
{
  template<>
  class less<card>
  {
  public:
    bool operator()(card a, card b) const { return acehigh_less(a, b); }
  };
}

int main()
{
  using cardset = std::set<card>;
  cardset deck{};
  std::generate_n(std::inserter(deck, deck.begin()), 52, card_generator{});

  for (int i{0}; i != 10; ++i)
  {
    auto pick{deck.begin()};
    std::advance(pick, randomint{0, deck.size() - 1}());
    card computer_card{*pick};
    deck.erase(pick);

    std::cout << "I picked " << computer_card << '\n';

    pick = deck.begin();
    std::advance(pick, randomint{0, deck.size() - 1}());
    card user_card{*pick};
    deck.erase(pick);

    std::cout << "You picked " << user_card << '\n';

    if (acehigh_less(computer_card, user_card))
      std::cout << "You win.\n";
    else
      std::cout << "I win.\n";
  }
}

Listing 57-11.Playing High-Card Using an Explicit Specialization of std::less

要使用无序容器，必须编写一个显式的std::hash<card>特化。清单 57-1 应该能帮上忙。卡模块已经为卡声明了operator==，所以你要准备好最后一次重写高卡程序，这次是为 unordered_set **。**将您的解决方案与清单 57-12 进行比较。尽管容器类型不同，但所有这些程序都非常相似，这是通过明智地使用迭代器、算法和函子而实现的。

import <algorithm>;
import <functional>;
import <iostream>;
import <iterator>;
import <unordered_set>;

import card;
import randomint;

namespace std
{
  template<>
  class hash<card>
  {
  public:
    std::size_t operator()(card a)
    const
    {
      return hash<int>{}(a.get_suit() * 64 + a.get_rank());
    }
  };
} // namespace std

int main()
{
  using cardset = std::unordered_set<card>;
  cardset deck{};
  std::generate_n(std::inserter(deck, deck.begin()), 52, card_generator{});

  for (int i(0); i != 10; ++i)
  {
    auto pick{deck.begin()};
    std::advance(pick, randomint{0, deck.size() - 1}());
    card computer_card{*pick};
    deck.erase(pick);

    std::cout << "I picked " << computer_card << '\n';

    pick = deck.begin();
    std::advance(pick, randomint{0, deck.size() - 1}());
    card user_card{*pick};
    deck.erase(pick);

    std::cout << "You picked " << user_card << '\n';

    if (acehigh_less(computer_card, user_card))
      std::cout << "You win.\n";
    else
      std::cout << "I win.\n";
  }
}

Listing 57-12.Playing High-Card with unordered_set

在接下来的探索中，你将踏上一个完全不同的旅程，一个涉及到异国情调的地方，当地人说异国情调的语言，使用异国情调的字符集的世界旅行。这个旅程还涉及到模板的新的有趣的用途。