02.md

二、标准模板库

本章将涵盖以下主题:

• STL 概述
• STL 体系结构
  • 容器
  • 迭代程序
  • 算法
  • 函子
• STL 容器
  • 顺序
  • 联合的
  • 无序的
  • 转接器，适配器；改编者

让我们在下面的章节中一个接一个地研究 STL 主题。

标准模板库体系结构

C++ 标准模板库 ( STL )提供了现成的通用容器、可应用于容器的算法以及导航容器的迭代器。STL 是用 C++ 模板实现的，模板允许用 C++ 进行泛型编程。

STL 通过将开发人员从编写低级数据结构和算法中解放出来，鼓励 C++ 开发人员专注于手头的任务。STL 是一个经过时间考验的库，允许快速应用开发。

STL 是一个有趣的作品和架构。它的秘密公式是编译时多态性。为了获得更好的性能，STL 避免了动态多态，告别了虚函数。总的来说，补充交易日志有以下四个组成部分:

• 算法
• 函子
• 迭代程序
• 容器

STL 架构将上述四个组件缝合在一起。它有许多常用的算法，并有性能保证。STL 算法的有趣之处在于，它们可以无缝工作，而不需要任何关于保存数据的容器的知识。这之所以成为可能，是因为迭代器提供了高级遍历 API，它完全抽象了容器中使用的底层数据结构。STL 非常广泛地使用了运算符重载。让我们逐一了解 STL 的主要组成部分，从概念上很好地掌握 STL。

算法

STL 算法是由 C++ 模板驱动的；因此，无论处理什么类型的数据，或者独立于容器如何组织数据，相同的算法都可以工作。有趣的是，STL 算法足够通用，可以使用模板支持内置和用户定义的数据类型。事实上，算法通过迭代器与容器交互。因此，对算法来说重要的是容器支持的迭代器。话虽如此，算法的性能取决于容器中使用的底层数据结构。因此，某些算法只在选择性容器上工作，因为 STL 支持的每个算法都需要某种类型的迭代器。

迭代程序

迭代器是一种设计模式，但有趣的是，STL 的工作在“四人帮”向软件社区发布他们的设计模式相关工作之前就已经开始了。迭代器本身是允许遍历容器来访问、修改和操作存储在容器中的数据的对象。迭代器如此神奇地做到这一点，以至于我们意识不到或者不需要知道数据是如何存储和检索的。

下图直观地表示了一个迭代器:

从上图可以理解，每个迭代器都支持begin() API，它返回第一个元素位置，end() API 返回容器中最后一个元素之后的一个位置。

STL 广泛支持以下五种类型的迭代器:

• 输入迭代器
• 输出迭代器
• 向前迭代器
• 双向迭代器
• 随机存取迭代器

容器实现了迭代器，让我们可以轻松地检索和操作数据，而无需深入研究容器的技术细节。

下表解释了五个迭代器中的每一个:

| 迭代器的类型 | 描述 | | 输入迭代器 |

• Used to point to elements from
• Read in, which is valid for single navigation. Once the end of the container is reached, the iterator will fail.
• Support before and after increment operators.
• Decreasing operator is not supported
• Support dereference
• Support == != operator and other iterators.
• Compare the istream_iterator iterator to the input iterator.

| | 输出迭代器 |

• Used to modify pointing elements.
• Valid for single navigation. Once the end of the container is reached, the iterator will fail.
• Support before and after increment operator
• Decreasing operator is not supported
• Support dereference
• The == and != operators are not supported.
• ostream_iterator back_inserter front_inserter iterator

| | 向前迭代器 |

• Support functions of input iterator and output iterator.
• Support multi-pass navigation
• Pre-increment and post-increment operators are supported
• Support dereference
• forward_list The container supports forward iterators.

| | 双向迭代器 |

• Is a forward iterator that supports bidirectional navigation.
• Allow multiple navigation
• The operator before increment and after increment is supported.
• Supports the operator of pre-subtraction and post-subtraction
• Support dereference
• Support [] operator
• list set map multiset multimap The container supports the bidirectional iterator 【 T20

| | 随机存取迭代器 |

• Elements can be accessed using any offset position.
• It supports pre-increment and post-increment operators.
• It supports pre-decrement and post-decrement operators
• It supports dereference.
• It is the most complete iterator because it supports all the functions of other iterators listed earlier.
• array vector and deque containers support random access iterators.
• A support

|

容器

STL 容器是通常动态增长和收缩的对象。容器使用复杂的数据结构将数据存储在引擎盖下，并提供高级功能来访问数据，而无需我们深入研究数据结构的复杂内部实现细节。STL 容器非常高效，并且经过时间考验。

每个容器都使用不同类型的数据结构来高效地存储、组织和操作数据。尽管许多容器看起来相似，但它们在引擎盖下的行为却不同。因此，容器的错误选择会导致应用性能问题和不必要的复杂性。

容器有以下几种口味:

• 连续的
• 联合的
• 容器适配器

存储在容器中的对象被复制或移动，而不是被引用。在接下来的章节中，我们将用简单而有趣的例子来探索每一种类型的容器。

函子

函子是行为类似常规函数的对象。好处是函子可以代替函数指针。函子是方便的对象，允许您扩展或补充 STL 函数的行为，而不会损害面向对象的编码原则。

函子易于实现；您所需要做的就是重载函数运算符。函子也被称为函子。

下面的代码将演示如何实现一个简单的函子:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

template <typename T>
class Printer {
public:
  void operator() ( const T& element ) {
    cout << element << "\t";
  }
};

int main () {
  vector<int> v = { 10, 20, 30, 40, 50 };

  cout << "\nPrint the vector entries using Functor" << endl;

  for_each ( v.begin(), v.end(), Printer<int>() );

  cout << endl;

  return 0;
}

让我们使用以下命令快速编译程序:

g++ main.cpp -std=c++ 17
./a.out

让我们检查程序的输出:

Print the vector entries using Functor
10  20  30  40  50

我们希望你意识到一个函子是多么容易和酷。

序列容器

STL 支持各种有趣的序列容器。序列容器以线性方式存储同类数据类型，可以按顺序访问。STL 支持以下序列容器:

• 数组
• 向量
• 列表
• forward_list
• 双端队列

由于存储在 STL 容器中的对象只不过是值的副本，因此 STL 期望用户定义的数据类型满足某些基本要求，以便将这些对象保存在容器中。存储在 STL 容器中的每个对象必须至少满足以下要求:

• 默认构造函数
• 复制构造函数
• 赋值运算符

让我们在下面的小节中一个接一个地探索序列容器。

排列

STL 数组容器是一个固定大小的序列容器，就像 C/C++ 内置数组一样，只是 STL 数组是大小感知的，比内置的 C/C++ 数组聪明一点。让我们用一个例子来理解一个 STL 数组:

#include <iostream>
#include <array>
using namespace std;
int main () {
  array<int,5> a = { 1, 5, 2, 4, 3 };

  cout << "\nSize of array is " << a.size() << endl;

  auto pos = a.begin();

  cout << endl;
  while ( pos != a.end() ) 
    cout << *pos++ << "\t";
  cout << endl;

  return 0;
}

可以使用以下命令编译前面的代码并查看输出:

g++ main.cpp -std=c++ 17
./a.out 

程序的输出如下:

Size of array is 5
1     5     2     4     3

代码走查

下面一行声明一个固定大小的数组(5)并用五个元素初始化该数组:

array<int,5> a = { 1, 5, 2, 4, 3 };

提到的大小一旦声明就不能更改，就像 C/C++ 内置数组一样。array::size()方法返回数组的大小，不管初始化列表中初始化了多少个整数。auto pos = a.begin()方法声明一个array<int,5>的迭代器，并指定数组的起始位置。array::end()方法指向数组中最后一个元素之后的一个位置。迭代器的行为类似于或模仿 C++ 指针，对迭代器取消引用会返回迭代器指向的值。迭代器位置可以分别通过++ pos和--pos前后移动。

数组中常用的 API

下表显示了一些常用的阵列 API:

| API | 描述 | | at( int index ) | 这将返回存储在索引引用位置的值。该索引是从零开始的索引。如果索引在数组的索引范围之外，这个应用编程接口将抛出std::out_of_range异常。 | | operator [ int index ] | 这是一个不安全的方法，因为如果索引超出数组的有效范围，它不会引发任何异常。这往往比at稍快，因为这个 API 不执行边界检查。 | | front() | 这将返回数组中的第一个元素。 | | back() | 这将返回数组中的最后一个元素。 | | begin() | 这将返回数组中第一个元素的位置 | | end() | 这将返回数组中最后一个元素之后的一个位置 | | rbegin() | 这将返回相反的开始位置，即返回数组中最后一个元素的位置 | | rend() | 这将返回反向结束位置，也就是说，它将返回数组中第一个元素之前的一个位置 | | size() | 这将返回数组的大小 |

数组容器支持随机访问；因此，给定一个索引，数组容器可以获取一个运行时复杂度为*0(1)*或恒定时间的值。

可以使用反向迭代器以反向方式访问数组容器元素:

#include <iostream>
#include <array>
using namespace std;

int main () {

    array<int, 6> a;
    int size = a.size();
    for (int index=0; index < size; ++ index)
         a[index] = (index+1) * 100;   

    cout << "\nPrint values in original order ..." << endl;

    auto pos = a.begin();
    while ( pos != a.end() )
        cout << *pos++ << "\t";
    cout << endl;

    cout << "\nPrint values in reverse order ..." << endl;

    auto rpos = a.rbegin();
    while ( rpos != a.rend() )
    cout << *rpos++ << "\t";
    cout << endl;

    return 0;
}

我们将使用以下命令获得输出:

./a.out

输出如下:

Print values in original order ...
100   200   300   400   500   600

Print values in reverse order ...
600   500   400   300   200   100

矢量

Vector 是一个非常有用的序列容器，它完全像一个数组一样工作，只是当数组的大小固定时，vector 可以在运行时增长和收缩。然而，在数组和向量中使用的数据结构是一个简单的内置 C/C++ 风格的数组。

让我们看下面的例子来更好地理解向量:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
  vector<int> v = { 1, 5, 2, 4, 3 };

  cout << "\nSize of vector is " << v.size() << endl;

  auto pos = v.begin();

  cout << "\nPrint vector elements before sorting" << endl;
  while ( pos != v.end() )
    cout << *pos++ << "\t";
  cout << endl;

  sort( v.begin(), v.end() );

  pos = v.begin();

  cout << "\nPrint vector elements after sorting" << endl;

  while ( pos != v.end() )
    cout << *pos++ << "\t";
  cout << endl;

  return 0;
}

可以使用以下命令编译前面的代码并查看输出:

g++ main.cpp -std=c++ 17
./a.out

程序的输出如下:

Size of vector is 5

Print vector elements before sorting
1     5     2     4     3

Print vector elements after sorting
1     2     3     4     5

代码走查

下面一行声明一个向量，并用五个元素初始化该向量:

vector<int> v = { 1, 5, 2, 4, 3 };

然而，向量也允许通过使用vector::push_back<data_type>( value )应用编程接口将值附加到向量的末尾。sort()算法采用两个随机访问迭代器，表示必须排序的数据范围。由于向量内部使用了内置的 C/C++ 数组，就像 STL 数组容器一样，向量也支持随机访问迭代器；因此sort()函数是一种高效算法，其运行时复杂度是对数的，即 O(N log2 (N)) 。

常用载体原料药

下表显示了一些常用的矢量应用编程接口:

| API | 描述 | | at ( int index ) | 这将返回存储在索引位置的值。如果索引无效，则抛出std::out_of_range异常。 | | operator [ int index ] | 这将返回存储在索引位置的值。它比at( int index )更快，因为该函数不执行边界检查。 | | front() | 这将返回存储在向量中的第一个值。 | | back() | 这将返回存储在向量中的最后一个值。 | | empty() | 如果向量为空，则返回 true，否则返回 false。 | | size() | 这将返回存储在向量中的值的数量。 | | reserve( int size ) | 这保留了向量的初始大小。当向量大小达到其容量时，尝试插入新值需要调整向量大小。这使得插入消耗 O(N) 运行时的复杂性。reserve()方法是上述问题的一种解决方法。 | | capacity() | 这将返回向量的总容量，而大小是存储在向量中的实际值。 | | clear() | 这将清除所有值。 | | push_back<data_type>( value ) | 这将在向量的末尾添加一个新值。 |

使用istream_iterator和ostream_iterator从矢量中读取和打印将会非常有趣和方便。下面的代码演示了向量的使用:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main () {
    vector<int> v;

    cout << "\nType empty string to end the input once you are done feeding the vector" << endl;
    cout << "\nEnter some numbers to feed the vector ..." << endl;

    istream_iterator<int> start_input(cin);
    istream_iterator<int> end_input;

    copy ( start_input, end_input, back_inserter( v ) );

    cout << "\nPrint the vector ..." << endl;
    copy ( v.begin(), v.end(), ostream_iterator<int>(cout, "\t") );
    cout << endl;

    return 0;
}

Note that the output of the program is skipped, as the output depends on the input entered by you. Feel free to try the instructions on the command line.

代码走查

基本上，复制算法接受一系列迭代器，其中前两个参数代表源，第三个参数代表目的地，恰好是向量:

istream_iterator<int> start_input(cin);
istream_iterator<int> end_input;

copy ( start_input, end_input, back_inserter( v ) );

start_input迭代器实例定义了一个从istream和cin接收输入的istream_iterator迭代器，end_input迭代器实例定义了一个文件结束分隔符，默认情况下是一个空字符串("")。因此，可以通过在命令行输入终端中键入""来终止输入。

同样，让我们理解下面的代码片段:

cout << "\nPrint the vector ..." << endl;
copy ( v.begin(), v.end(), ostream_iterator<int>(cout, "\t") );
cout << endl;

复制算法用于一次一个元素地将向量中的值复制到ostream，用制表符(\t)分隔输出。

向量的陷阱

每个 STL 容器都有自己的优缺点。没有一个单一的 STL 容器在所有场景中都能更好地工作。向量在内部使用数组数据结构，在 C/C++ 中数组的大小是固定的。因此，当您试图在向量大小已经达到其最大容量时向向量添加新值时，向量将分配新的连续位置，该位置可以容纳相邻位置中的旧值和新值。然后，它开始将旧值复制到新位置。一旦复制了所有数据元素，向量将使旧位置无效。

每当这种情况发生时，向量插入将花费 O(N) 运行时复杂度。随着向量的大小随着时间的推移而增长，根据需要， O(N) 运行时的复杂性将表现出相当糟糕的性能。如果您知道所需的最大尺寸，您可以提前预留这么多初始尺寸来克服这个问题。然而，并不是在所有情况下都需要使用向量。当然，向量支持动态大小和随机访问，这在某些场景中有性能优势，但是您正在使用的功能可能并不真正需要随机访问，在这种情况下，list、deque 或其他一些容器可能更适合您。

目录

列表 STL 容器在内部使用双向链表数据结构。因此，列表只支持顺序访问，在最坏的情况下，在列表中搜索随机值可能会增加运行时的复杂性。然而，如果你确定你只需要顺序访问，这个列表确实有它自己的好处。列表 STL 容器允许您以恒定的时间复杂度在末尾、前面或中间插入数据元素，即在最佳、平均和最坏情况下的 O(1) 运行时复杂度。

下图演示了列表 STL 使用的内部数据结构:

让我们编写一个简单的程序来获得使用列表 STL 的第一手经验:

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

int main () {

  list<int> l;

  for (int count=0; count<5; ++ count)
    l.push_back( (count+1) * 100 );

  auto pos = l.begin();

  cout << "\nPrint the list ..." << endl;
  while ( pos != l.end() )
    cout << *pos++ << "-->";
  cout << " X" << endl;

  return 0;
}

我相信现在你已经尝到了 C++ STL 的味道，它的优雅和它的力量。观察到所有 STL 容器的语法都保持不变，这不是很酷吗？您可能已经观察到，无论您使用数组、向量还是列表，语法都保持不变。相信我，当您探索其他 STL 容器时，您也会得到同样的印象。

话虽如此，前面的代码是不言自明的，因为我们对其他容器做了几乎相同的事情。

让我们尝试对列表进行排序，如以下代码所示:

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

int main () {

    list<int> l = { 100, 20, 80, 50, 60, 5 };

    auto pos = l.begin();

    cout << "\nPrint the list before sorting ..." << endl;
    copy ( l.begin(), l.end(), ostream_iterator<int>( cout, "-->" ));
    cout << "X" << endl;

    l.sort();

    cout << "\nPrint the list after sorting ..." << endl;
    copy ( l.begin(), l.end(), ostream_iterator<int>( cout, "-->" ));
    cout << "X" << endl; 

    return 0;
}

你注意到sort()方法了吗？是的，列表容器有自己的排序算法。列表容器支持自己版本的排序算法的原因是通用sort()算法需要随机访问迭代器，而列表容器不支持随机访问。在这种情况下，相应的容器将提供自己的高效算法来克服这个缺点。

有趣的是，列表支持的sort算法的运行时复杂度为 O (N log2 N) 。

列表中常用的 API

下表显示了 STL 列表中最常用的应用编程接口:

| API | 描述 | | front() | 这将返回列表中存储的第一个值 | | back() | 这将返回列表中存储的最后一个值 | | size() | 这将返回列表中存储的值的计数 | | empty() | 列表为空时返回true，否则返回false | | clear() | 这将清除列表中存储的所有值 | | push_back<data_type>( value ) | 这会在列表的末尾添加一个值 | | push_front<data_type>( value ) | 这会在列表的前面添加一个值 | | merge( list ) | 这将合并两个具有相同类型值的排序列表 | | reverse() | 这将颠倒列表 | | unique() | 这将从列表中删除重复的值 | | sort() | 这会对存储在列表中的值进行排序 |

转发列表

STL 的forward_list容器建立在单链表数据结构之上；因此，它只支持正向导航。由于forward_list在内存和运行时间方面为每个节点少消耗一个指针，因此与列表容器相比，它被认为更有效。然而，由于价格对于性能优势的额外优势，forward_list不得不放弃一些功能。

下图显示了forward_list中使用的内部数据结构:

让我们探索以下示例代码:

#include <iostream>
#include <forward_list>
#include <iterator>
#include <algorithm>
using namespace std;

int main ( ) {

  forward_list<int> l = { 10, 10, 20, 30, 45, 45, 50 };

  cout << "\nlist with all values ..." << endl;
  copy ( l.begin(), l.end(), ostream_iterator<int>(cout, "\t") );

  cout << "\nSize of list with duplicates is " << distance( l.begin(), l.end() ) << endl;

  l.unique();

  cout << "\nSize of list without duplicates is " << distance( l.begin(), l.end() ) << endl;

  l.resize( distance( l.begin(), l.end() ) );

  cout << "\nlist after removing duplicates ..." << endl;
  copy ( l.begin(), l.end(), ostream_iterator<int>(cout, "\t") );
  cout << endl;

  return 0;

}

可以使用以下命令查看输出:

./a.out

输出如下:

list with all values ...
10    10    20    30    45    45    50
Size of list with duplicates is 7

Size of list without duplicates is 5

list after removing duplicates ...
10    20   30   45   50

代码走查

下面的代码用一些唯一的值和一些重复的值声明并初始化forward_list容器:

forward_list<int> l = { 10, 10, 20, 30, 45, 45, 50 };

由于forward_list容器不支持size()功能，我们使用distance()功能来查找列表的大小:

cout << "\nSize of list with duplicates is " << distance( l.begin(), l.end() ) << endl;

下面的forward_list<int>::unique()函数删除重复的整数，只保留唯一的值:

l.unique();

转发列表容器中常用的 API

下表显示了常用的forward_list原料药:

| API | 描述 | | front() | 这将返回存储在forward_list容器中的第一个值 | | empty() | 当forward_list容器为空时返回真，否则返回假 | | clear() | 这将清除存储在forward_list中的所有值 | | push_front<data_type>( value ) | 这会在forward_list的前面增加一个值 | | merge( list ) | 这将合并两个具有相同类型值的排序的forward_list容器 | | reverse() | 这会反转forward_list容器 | | unique() | 这将从forward_list容器中删除重复的值 | | sort() | 这将对存储在forward_list中的值进行排序 |

让我们再探索一个例子，来深入了解forward_list容器:

#include <iostream>
#include <forward_list>
#include <iterator>
#include <algorithm>
using namespace std;

int main () {

    forward_list<int> list1 = { 10, 20, 10, 45, 45, 50, 25 };
    forward_list<int> list2 = { 20, 35, 27, 15, 100, 85, 12, 15 };

    cout << "\nFirst list before sorting ..." << endl;
    copy ( list1.begin(), list1.end(), ostream_iterator<int>(cout, "\t") );
    cout << endl; 

    cout << "\nSecond list before sorting ..." << endl;
    copy ( list2.begin(), list2.end(), ostream_iterator<int>(cout, "\t") );
    cout << endl;

    list1.sort();
    list2.sort();

    cout << "\nFirst list after sorting ..." << endl;
    copy ( list1.begin(), list1.end(), ostream_iterator<int>(cout, "\t") );
    cout << endl; 

    cout << "\nSecond list after sorting ..." << endl;
    copy ( list2.begin(), list2.end(), ostream_iterator<int>(cout, "\t") );
    cout << endl;    

    list1.merge ( list2 );

    cout << "\nMerged list ..." << endl;
    copy ( list1.begin(), list1.end(), ostream_iterator<int>(cout, "\t") );

    cout << "\nMerged list after removing duplicates ..." << endl;
    list1.unique(); 
    copy ( list1.begin(), list1.end(), ostream_iterator<int>(cout, "\t") );

    return 0;
}

前面的代码片段是一个有趣的例子，演示了sort()、merge()和unique() STL 算法的实际使用。

可以使用以下命令查看输出:

./a.out

程序的输出如下:

First list before sorting ...
10   20   10   45   45   50   25
Second list before sorting ...
20   35   27   15   100  85   12   15

First list after sorting ...
10   10   20   25   45   45   50
Second list after sorting ...
12   15   15   20   27   35   85   100

Merged list ...
10   10   12   15   15   20   20   25   27   35   45   45  50   85  100
Merged list after removing duplicates ...
10   12   15   20   25   27   35   45   50   85  100

输出和程序都很容易理解。

双端队列

deque 容器是一个双端队列，使用的数据结构可以是动态数组或向量。在一个德格中，可以在前面和后面都插入一个元素，时间复杂度为 O(1) ，不像向量，在后面插入一个元素的时间复杂度为 O(1) ，而在前面插入一个元素的时间复杂度为 O(N) 。德格没有向量遇到的重新分配问题。然而，与矢量相比，矢量的所有优点都存在于 deque 中，只是 deque 在性能方面稍好一些，因为每行有几行动态数组或矢量。

下图显示了 deque 容器中使用的内部数据结构:

让我们编写一个简单的程序来测试 deque 容器:

#include <iostream>
#include <deque>
#include <algorithm>
#include <iterator>
using namespace std;

int main () {
  deque<int> d = { 10, 20, 30, 40, 50 };

  cout << "\nInitial size of deque is " << d.size() << endl;

  d.push_back( 60 );
  d.push_front( 5 );

  cout << "\nSize of deque after push back and front is " << d.size() << endl;

  copy ( d.begin(), d.end(), ostream_iterator<int>( cout, "\t" ) );
  d.clear();

  cout << "\nSize of deque after clearing all values is " << d.size() <<
endl;

  cout << "\nIs the deque empty after clearing values ? " << ( d.empty()
? "true" : "false" ) << endl;

return 0;
}

可以使用以下命令查看输出:

./a.out

程序的输出如下:

Intitial size of deque is 5

Size of deque after push back and front is 7

Print the deque ...
5  10  20  30  40  50  60
Size of deque after clearing all values is 0

Is the deque empty after clearing values ? true

一个文件中常用的应用接口

下表显示了常用的 deque APIs:

| API | 描述 | | at ( int index ) | 这将返回存储在索引位置的值。如果索引无效，则抛出std::out_of_range异常。 | | operator [ int index ] | 这将返回存储在索引位置的值。它比at( int index )更快，因为该函数不执行边界检查。 | | front() | 这将返回存储在 deque 中的第一个值。 | | back() | 这将返回存储在 deque 中的最后一个值。 | | empty() | 如果德格为空，则返回true，否则返回false。 | | size() | 这将返回存储在 deque 中的值的数量。 | | capacity() | 这将返回德格的总容量，而size()将返回德格中存储的实际值数。 | | clear() | 这将清除所有值。 | | push_back<data_type>( value ) | 这会在 deque 的末尾添加一个新值。 |

关联容器

与序列容器不同，关联容器以排序的方式存储数据。因此，关联容器不会保留数据插入的顺序。关联容器在搜索运行时复杂度为 O( log n ) 的值时非常高效。每当一个新的值被添加到容器中时，如果需要，容器将对内部存储的值重新排序。

STL 支持以下类型的关联容器:

• 一组
• 地图
• 多组
• 多点触控
• 无序集
• 无序多集
• 无序地图
• 无序多重映射

关联容器将数据组织为键值对。数据将根据密钥进行排序，以便随机和更快地访问。联合容器有两种风格:

• 整齐的
• 无序的

以下关联容器属于有序容器，因为它们是以特定方式排序的。有序关联容器一般使用某种形式的二叉查找树(BST)；通常，红黑树用于存储数据:

• 一组
• 地图
• 多组
• 多点触控

以下关联容器属于无序容器，因为它们不以任何特定方式排序，并且使用哈希表:

• 无序集
• 无序地图
• 无序多集
• 无序多重映射

让我们通过以下小节中的示例来理解前面提到的容器。

一组

集合容器只以排序的方式存储唯一的值。集合使用值作为关键字来组织值。集合容器是不可变的，即存储在集合中的值不能被修改；但是，这些值可以删除。集合通常使用红黑树数据结构，这是一种平衡的 BST 形式。集合运算的时间复杂度保证为 O ( log N ) 。

让我们用一个集合编写一个简单的程序:

#include <iostream>
#include <set>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

int main( ) {
    set<int> s1 = { 1, 3, 5, 7, 9 };
    set<int> s2 = { 2, 3, 7, 8, 10 };

    vector<int> v( s1.size() + s2.size() );

    cout << "\nFirst set values are ..." << endl;
    copy ( s1.begin(), s1.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl;

    cout << "\nSecond set values are ..." << endl;
    copy ( s2.begin(), s2.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl;

    auto pos = set_difference ( s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin() ); 
    v.resize ( pos - v.begin() );

    cout << "\nValues present in set one but not in set two are ..." << endl;
    copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl; 

    v.clear();

    v.resize ( s1.size() + s2.size() );

    pos = set_union ( s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin() );

    v.resize ( pos - v.begin() );

    cout << "\nMerged set values in vector are ..." << endl;
    copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl; 

    return 0;
}

可以使用以下命令查看输出:

./a.out

程序的输出如下:

First set values are ...
1   3   5   7   9

Second set values are ...
2   3   7   8   10

Values present in set one but not in set two are ...
1   5   9

Merged values of first and second set are ...
1   2   3   5   7   8   9  10

代码走查

下面的代码声明并初始化了两组，s1和s2:

set<int> s1 = { 1, 3, 5, 7, 9 };
set<int> s2 = { 2, 3, 7, 8, 10 };

下一行将确保向量有足够的空间来存储结果向量中的值:

vector<int> v( s1.size() + s2.size() );

以下代码将打印s1和s2中的值:

cout << "\nFirst set values are ..." << endl;
copy ( s1.begin(), s1.end(), ostream_iterator<int> ( cout, "\t" ) );
cout << endl;

cout << "\nSecond set values are ..." << endl;
copy ( s2.begin(), s2.end(), ostream_iterator<int> ( cout, "\t" ) );
cout << endl;

set_difference()算法将用仅出现在集合s1中而不出现在s2中的值填充向量v。迭代器pos将指向向量中的最后一个元素；因此，向量resize将确保移除向量中的额外空格:

auto pos = set_difference ( s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin() ); 
v.resize ( pos - v.begin() );

以下代码将打印向量v中填充的值:

cout << "\nValues present in set one but not in set two are ..." << endl;
copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, "\t" ) );
cout << endl;

set_union()算法将集合s1和s2的内容合并到向量中，然后调整向量的大小以仅适合合并的值:

pos = set_union ( s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin() );
v.resize ( pos - v.begin() );

以下代码将打印向量v中填充的合并值:

cout << "\nMerged values of first and second set are ..." << endl;
copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, "\t" ) );
cout << endl;

集合中常用的应用编程接口

下表描述了常用的应用编程接口集:

| API | 描述 | | insert( value ) | 这将在集合中插入一个值 | | clear() | 这将清除集合中的所有值 | | size() | 这将返回集合中存在的条目总数 | | empty() | 如果设置为空，将打印true，否则返回false | | find() | 这会找到具有指定键的元素，并返回迭代器位置 | | equal_range() | 这将返回与特定键匹配的元素范围 | | lower_bound() | 这会返回一个不小于给定键的第一个元素的迭代器 | | upper_bound() | 这会返回一个迭代器到大于给定键 的第一个元素 |

地图

地图存储按键组织的值。与集合不同，地图每个值都有一个专用键。地图通常使用红黑树作为内部数据结构，这是一个平衡的 BST，保证了在地图中搜索或定位值的 O( log N ) 运行时效率。存储在地图中的值使用红黑树根据关键字进行排序。地图中使用的键必须是唯一的。地图不会保留输入序列，因为它会根据关键点重新组织值，也就是说，红黑树将被旋转以平衡红黑树的高度。

让我们编写一个简单的程序来理解地图的用法:

#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>
using namespace std;

int main ( ) {

  map<string, long> contacts;

  contacts["Jegan"] = 123456789;
  contacts["Meena"] = 523456289;
  contacts["Nitesh"] = 623856729;
  contacts["Sriram"] = 993456789;

  auto pos = contacts.find( "Sriram" );

  if ( pos != contacts.end() )
    cout << pos->second << endl;

  return 0;
}

让我们编译并检查程序的输出:

g++ main.cpp -std=c++ 17
./a.out

输出如下:

Mobile number of Sriram is 8901122334

代码走查

下面一行声明了一个以string名称为关键字，以long手机号码为存储在地图中的值的地图:

map< string, long > contacts;

下面的代码片段添加了四个按姓名组织的联系人作为关键字:

 contacts[ "Jegan" ] = 1234567890;
 contacts[ "Meena" ] = 5784433221;
 contacts[ "Nitesh" ] = 4567891234;
 contacts[ "Sriram" ] = 8901122334;

下面一行将尝试在联系人地图中定位名为Sriram的联系人；如果找到Sriram，那么find()函数将返回指向键值对位置的迭代器；否则返回contacts.end()位置:

 auto pos = contacts.find( "Sriram" );

下面的代码验证迭代器pos是否已经到达contacts.end()并打印联系号码。因为地图是一个关联容器，它存储一对key=>value；因此，pos->first表示键，pos->second表示值:

 if ( pos != contacts.end() )
 cout << "\nMobile number of " << pos->first << " is " << pos->second << endl;
 else
 cout << "\nContact not found." << endl;

地图中常用的应用编程接口

下表显示了常用的地图应用编程接口:

| API | 描述 | | at ( key ) | 如果找到相应的键，则返回该键的值；否则会抛出std::out_of_range异常 | | operator[ key ] | 如果找到相应的键，这将更新该键的现有值；否则，它将添加一个新条目，并提供相应的key=>value | | empty() | 如果地图为空，则返回true，否则返回false | | size() | 这会返回存储在地图中的key=>value对的计数 | | clear() | 这将清除存储在地图中的条目 | | count() | 这将返回与给定键匹配的元素数量 | | find() | 这会找到具有指定键的元素 |

多组

多集容器的工作方式类似于集合容器，只是集合只允许存储唯一的值，而多集允许存储重复的值。如您所知，在集合和多集合容器的情况下，值本身被用作组织数据的键。多集容器就像一个集合；它不允许修改存储在 multiset 中的值。

让我们使用多集编写一个简单的程序:

#include <iostream>
#include <set>
#include <iterator>
#include <algorithm>
using namespace std;

int main() {
  multiset<int> s = { 10, 30, 10, 50, 70, 90 };

  cout << "\nMultiset values are ..." << endl;

  copy ( s.begin(), s.end(), ostream_iterator<int> ( cout, "\t" ) );
  cout << endl;

  return 0;
}

可以使用以下命令查看输出:

./a.out

程序的输出如下:

Multiset values are ...
10 30 10 50 70 90

有趣的是，在前面的输出中，您可以看到多集包含重复的值。

多点触控

多重映射完全像映射一样工作，除了多重映射容器允许用同一个键存储多个值。

让我们用一个简单的例子来探索 multimap 容器:

#include <iostream>
#include <map>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

int main() {
  multimap< string, long > contacts = {
    { "Jegan", 2232342343 },
    { "Meena", 3243435343 },
    { "Nitesh", 6234324343 },
    { "Sriram", 8932443241 },
    { "Nitesh", 5534327346 }
  };

  auto pos = contacts.find ( "Nitesh" );
  int count = contacts.count( "Nitesh" );
  int index = 0;

  while ( pos != contacts.end() ) {
    cout << "\nMobile number of " << pos->first << " is " <<
    pos->second << endl;
    ++ index;
    if ( index == count )
      break;
  }

  return 0;
}

可以使用以下命令编译程序并查看输出:

g++ main.cpp -std=c++ 17

./a.out

程序的输出如下:

Mobile number of Nitesh is 6234324343
Mobile number of Nitesh is 5534327346

无序集

无序集的工作方式类似于集合，只是这些容器的内部行为不同。一个集合使用红黑树，而一个无序集合使用散列表。集合运算的时间复杂度为 O( log N) ，而无序集合运算的时间复杂度为O(1)；因此，无序集往往比有序集快。

存储在无序集中的值没有以任何特定的方式组织，这与以排序方式存储值的集合不同。如果性能是标准，那么无序集合是一个很好的选择；但是，如果需要以排序的方式迭代值，那么 set 是一个不错的选择。

无序地图

无序地图的工作方式类似于地图，只是这些容器的内部行为不同。地图使用红黑树，而无序地图使用散列表。地图操作的时间复杂度为 O( log N) ，而无序地图操作的时间复杂度为*O(1)；*因此，无序地图往往比地图更快。

存储在无序映射中的值没有以任何特定的方式进行组织，这与按键对值进行排序的映射不同。

无序多集

无序多集的工作方式类似于多集，只是这些容器的内部行为不同。多集利用红黑树，而无序多集利用散列表。多集运算的时间复杂度为 O( log N) ，而无序多集运算的时间复杂度为 O(1) 。因此，无序多集往往比多集更快。

存储在无序多集合中的值没有以任何特定的方式组织，不像存储在有序多集合中的值。如果性能是标准，无序多集是一个很好的选择；然而，如果需要以排序的方式迭代值，那么 multiset 是一个不错的选择。

无序多重映射

无序多映射的工作方式类似于多映射，只是这些容器的内部行为不同。多映射利用红黑树，而无序的多映射利用散列表。多 ap 操作的时间复杂度为 O( log N) ，而无序多 ap 操作的时间复杂度为O(1)；因此，无序多映射往往比多映射更快。

存储在无序多映射中的值没有以任何特定的方式组织，不像在多映射中，值是按键排序的。如果性能是标准，那么无序的多重映射是一个很好的选择；然而，如果需要以排序的方式迭代值，那么 multimap 是一个不错的选择。

容器适配器

容器适配器调整现有容器以提供新容器。简单来说，STL 扩展是通过组合而不是继承来完成的。

STL 容器不能通过继承来扩展，因为它们的构造函数不是虚拟的。在整个 STL 中，您可以观察到，虽然静态多态性在运算符重载和模板方面都有使用，但出于性能原因，动态多态性被有意避免。因此，通过子类化现有的容器来扩展 STL 不是一个好主意，因为它会导致内存泄漏，因为容器类的行为不像基类。

STL 支持以下容器适配器:

• 堆
• 长队
• 优先级队列

让我们在下面的小节中探讨容器适配器。

堆

堆栈不是新容器；这是一个模板适配器类。适配器容器包装现有容器并提供高级功能。堆栈适配器容器提供堆栈操作，同时隐藏与堆栈无关的不必要功能。默认情况下，STL 堆栈使用一个 deque 容器；但是，我们可以指示堆栈在堆栈实例化期间使用任何满足堆栈要求的现有容器。

deq、lists 和 vectors 满足堆栈适配器的要求。

堆栈按照后进先出 ( 后进先出)的原则运行。

堆栈中常用的 API

下表显示了常用的堆栈 API:

| API | 描述 | | top() | 这将返回堆栈中最上面的值，即最后添加的值 | | push<data_type>( value ) | 这将把提供的值推到栈顶 | | pop() | 这将从堆栈中移除最上面的值 | | size() | 这将返回堆栈中存在的值的数量 | | empty() | 如果堆栈为空，则返回true；否则返回false |

是时候弄脏我们的手了；让我们编写一个简单的程序来使用堆栈:

#include <iostream>
#include <stack>
#include <iterator>
#include <algorithm>
using namespace std;

int main ( ) {

  stack<string> spoken_languages;

  spoken_languages.push ( "French" );
  spoken_languages.push ( "German" );
  spoken_languages.push ( "English" );
  spoken_languages.push ( "Hindi" );
  spoken_languages.push ( "Sanskrit" );
  spoken_languages.push ( "Tamil" );

  cout << "\nValues in Stack are ..." << endl;
  while ( ! spoken_languages.empty() ) {
              cout << spoken_languages.top() << endl;
        spoken_languages.pop();
  }
  cout << endl;

  return 0;
}

使用以下命令可以编译程序并查看输出:

g++ main.cpp -std=c++ 17

./a.out

程序的输出如下:

Values in Stack are ...
Tamil
Kannada
Telugu
Sanskrit
Hindi
English
German
French

从前面的输出中，我们可以看到堆栈的后进先出行为。

长队

队列基于先进先出 ( 先进先出原则工作。队列不是新的容器；它是一个模板化的适配器类，包装现有的容器，提供队列操作所需的高级功能，同时隐藏与队列无关的不必要功能。默认情况下，STL 队列使用一个 deque 容器；但是，我们可以指示队列在队列实例化期间使用任何满足队列要求的现有容器。

在队列中，新值可以在后面添加，也可以从前面删除。去 q、列表和向量满足队列适配器的要求。

队列中常用的应用编程接口

下表显示了常用的队列 API:

| API | 描述 | | push() | 这将在队列的后面追加一个新值 | | pop() | 这将删除队列前面的值 | | front() | 这将返回队列前面的值 | | back() | 这将返回队列后面的值 | | empty() | 当队列为空时，返回true；否则返回false | | size() | 这将返回队列中存储的值的数量 |

让我们在下面的程序中使用队列:

#include <iostream>
#include <queue>
#include <iterator>
#include <algorithm>
using namespace std;

int main () {
  queue<int> q;

  q.push ( 100 );
  q.push ( 200 );
  q.push ( 300 );

  cout << "\nValues in Queue are ..." << endl;
  while ( ! q.empty() ) {
    cout << q.front() << endl;
    q.pop();
  }

  return 0;
}

可以使用以下命令编译程序并查看输出:

g++ main.cpp -std=c++ 17

./a.out

程序的输出如下:

Values in Queue are ...
100
200
300

从前面的输出中，您可以观察到值是按照推入的相同顺序弹出的，即先进先出。

优先队列

优先级队列不是新的容器；它是一个模板化的适配器类，包装现有的容器，提供优先级队列操作所需的高级功能，同时隐藏与优先级队列无关的不必要功能。默认情况下，优先级队列使用向量容器；然而，deque 容器也满足优先级队列的要求。因此，在优先级队列实例化期间，您可以指示优先级队列也使用一个 deque。

优先级队列以最高优先级值最先出现的方式组织数据；换句话说，这些值是按降序排序的。

deque 和 vector 满足优先级队列适配器的要求。

优先级队列中常用的应用编程接口

下表显示了常用的优先级队列 API:

| API | 描述 | | push() | 这将在优先级队列的后面追加一个新值 | | pop() | 这将删除优先级队列前面的值 | | empty() | 当优先级队列为空时，返回true；否则返回false | | size() | 这将返回优先级队列中存储的值的数量 | | top() | 这将返回优先级队列前面的值 |

让我们写一个简单的程序来理解priority_queue:

#include <iostream>
#include <queue>
#include <iterator>
#include <algorithm>
using namespace std;

int main () {
  priority_queue<int> q;

  q.push( 100 );
  q.push( 50 );
  q.push( 1000 );
  q.push( 800 );
  q.push( 300 );

  cout << "\nSequence in which value are inserted are ..." << endl;
  cout << "100\t50\t1000\t800\t300" << endl;
  cout << "Priority queue values are ..." << endl;

  while ( ! q.empty() ) {
    cout << q.top() << "\t";
    q.pop();
  }
  cout << endl;

  return 0;
}

使用以下命令可以编译程序并查看输出:

g++ main.cpp -std=c++ 17

./a.out

程序的输出如下:

Sequence in which value are inserted are ...
100   50   1000  800   300

Priority queue values are ...
1000  800   300   100   50

从前面的输出中，您可以观察到priority_queue是一种特殊类型的队列，它以最高值最先出现的方式对输入进行重新排序。

摘要

在本章中，您学习了现成的泛型容器、函子、迭代器和算法。您还学习了集合、映射、多集合和多映射关联容器、它们的内部数据结构以及可以应用于它们的常见算法。此外，您还学习了如何通过实际操作代码示例来使用各种容器。

在下一章中，您将学习模板编程，这有助于您掌握模板的要领。