我们将在本章介绍以下食谱:
- 使用矢量作为默认容器
- 将位集用于固定大小的位序列
- 将向量用于可变大小的位序列
- 查找范围内的元素
- 对范围进行排序
- 初始化范围
- 对范围使用集合运算
- 使用迭代器在容器中插入新元素
- 编写自己的随机访问迭代器
- 具有非成员函数的容器访问
标准库提供了存储对象集合的各种类型的容器；该库包括序列容器(如vector、array或list)、有序和无序关联容器(如set和map)以及不存储数据但提供面向序列容器的适配接口(如stack和queue)的容器适配器。所有这些都实现为类模板，这意味着它们可以用于任何类型(只要它满足容器要求)。虽然您应该始终使用最适合特定问题的容器(它不仅在插入、删除、元素访问和内存使用的速度方面提供了良好的性能，而且使代码易于阅读和维护)，但默认选择应该是vector。在这个食谱中，我们将看到为什么vector应该是容器的首选，以及vector最常见的操作是什么。
读者应该熟悉 C 类数组，包括静态和动态分配的。
类模板vector在<vector>头中的std命名空间中可用。
要初始化std::vector类模板，您可以使用以下任何方法，但不限于这些方法:
- 从初始化列表初始化:
std::vector<int> v1 { 1, 2, 3, 4, 5 };- 从类 C 数组初始化:
int arr[] = { 1, 2, 3, 4, 5 };
std::vector<int> v2(arr, arr + 5); // { 1, 2, 3, 4, 5 }- 从另一个容器初始化:
std::list<int> l{ 1, 2, 3, 4, 5 };
std::vector<int> v3(l.begin(), l.end()); //{ 1, 2, 3, 4, 5 }- 从计数和值初始化:
std::vector<int> v4(5, 1); // {1, 1, 1, 1, 1}要修改std::vector的内容，可以使用以下任何一种方法，但不仅限于这些:
- 用
push_back()在向量末尾添加一个元素:
std::vector<int> v1{ 1, 2, 3, 4, 5 };
v1.push_back(6); // v1 = { 1, 2, 3, 4, 5, 6 }- 用
pop_back()从向量的末端移除一个元素:
v1.pop_back();- 用
insert()插入向量中的任意位置:
int arr[] = { 1, 2, 3, 4, 5 };
std::vector<int> v2;
v2.insert(v2.begin(), arr, arr + 5); // v2 = { 1, 2, 3, 4, 5 }- 通过用
emplace_back()在向量的末尾创建元素来添加元素:
struct foo
{
int a;
double b;
std::string c;
foo(int a, double b, std::string const & c) :
a(a), b(b), c(c) {}
};
std::vector<foo> v3;
v3.emplace_back(1, 1.0, "one"s);
// v3 = { foo{1, 1.0, "one"} }- 使用
emplace()在向量中的任意位置创建元素来插入元素:
v3.emplace(v3.begin(), 2, 2.0, "two"s);
// v3 = { foo{2, 2.0, "two"}, foo{1, 1.0, "one"} }要修改矢量的全部内容，请使用以下任一方法，但不限于这些方法:
- 用
operator=从另一个向量赋值；这将替换容器中的内容:
std::vector<int> v1{ 1, 2, 3, 4, 5 };
std::vector<int> v2{ 10, 20, 30 };
v2 = v1; // v1 = { 1, 2, 3, 4, 5 }- 使用
assign()方法从开始和结束迭代器定义的另一个序列赋值；这将替换容器中的内容:
int arr[] = { 1, 2, 3, 4, 5 };
std::vector<int> v3;
v3.assign(arr, arr + 5); // v3 = { 1, 2, 3, 4, 5 }- 用
swap()方法交换两个向量的内容:
std::vector<int> v4{ 1, 2, 3, 4, 5 };
std::vector<int> v5{ 10, 20, 30 };
v4.swap(v5); // v4 = { 10, 20, 30 }, v5 = { 1, 2, 3, 4, 5 }- 用
clear()方法去除所有元素:
std::vector<int> v6{ 1, 2, 3, 4, 5 };
v6.clear(); // v6 = { }- 使用
erase()方法移除一个或多个元素(需要一个迭代器或一对迭代器来定义要移除的向量的元素范围):
std::vector<int> v7{ 1, 2, 3, 4, 5 };
v7.erase(v7.begin() + 2, v7.begin() + 4); // v7 = { 1, 2, 5 }要获取向量中第一个元素的地址，通常是将向量的内容传递给类似 C 的 API，请使用以下任一方法:
- 使用
data()方法，该方法返回指向第一个元素的指针，提供对存储向量元素的底层连续内存序列的直接访问；这仅在 C++ 11:
void process(int const * const arr, int const size)
{ /* do something */ }
std::vector<int> v{ 1, 2, 3, 4, 5 };
process(v.data(), static_cast<int>(v.size()));- 获取第一个元素的地址:
process(&v[0], static_cast<int>(v.size()));- 获取
front()方法引用的元素地址:
process(&v.front(), static_cast<int>(v.size()));- 获取
begin()返回的迭代器指向的元素的地址:
process(&*v.begin(), static_cast<int>(v.size()));std::vector类被设计成与类 C 数组最相似且可相互操作的 C++ 容器。向量是可变大小的元素序列，保证连续存储在内存中，这使得向量的内容可以很容易地传递给 C 类函数，该函数接受指向数组元素的指针，通常还接受大小。使用向量代替类似 C 的数组有很多好处，这些好处包括:
- 不需要开发人员进行直接的内存管理，因为容器在内部进行内存分配、重新分配和释放。
Note that a vector is intended for storing object instances. If you need to store pointers, do not store raw pointers but smart pointers. Otherwise, you need to handle the lifetime management of the pointed objects.
- 两个向量的简单赋值或连接。
- 两个向量的直接比较。
vector类是一个非常高效的容器，所有的实现都提供了许多优化，而大多数开发人员无法用 C 类数组做到这一点。对其元素的随机访问以及在向量末尾的插入和移除是一个常数 O(1) 运算(前提是不需要重新分配)，而在其他地方的插入和移除是一个线性的 O(n) 运算。
与其他标准容器相比，该载体具有多种优势:
- 兼容类 C 数组和类 APIs 其他容器的内容(除了
std::array)需要复制到一个向量，然后传递到一个期待数组的类 API。 - 它可以最快地访问所有容器的元素。
- 它没有存储元素的每元素内存开销，因为元素存储在一个连续的空间中，就像一个 C 数组(不像其他容器，如
list需要指向其他元素的额外指针，或关联容器需要哈希值)。
std::vector在语义上与类 C 数组非常相似，但大小可变。向量的大小可以增加和减少。定义向量大小有两个属性:
- 容量是向量在不执行额外内存分配的情况下可以容纳的元素数量；这由
capacity()方法表示。 - 大小是向量中元素的实际数量；这由
size()方法表示。
大小总是小于或等于容量。当大小等于容量并且需要添加新元素时，需要修改容量，以便向量有空间容纳更多元素。在这种情况下，向量分配一个新的内存块，并将以前的内容移动到新的位置，然后释放以前分配的内存。虽然这听起来很耗时(而且确实如此)，但实现会成倍增加容量，每次需要更改时都会翻倍。因此，平均而言，向量的每个元素只需要移动一次(这是因为在容量增加期间，向量的所有元素都会移动，但是如果在向量的末尾执行插入，则可以添加相同数量的元素，而不会导致更多的移动)。
如果事先知道向量中要插入多少元素，可以先调用reserve()方法将容量增加到至少指定的数量(如果指定的大小小于当前容量，该方法不做任何事情)，然后再插入元素。
另一方面，如果需要释放额外的保留内存，可以使用shrink_to_fit()方法请求，但是否释放任何内存是一个实现决定。自 C++ 11 以来，这种非绑定方法的一种替代方法是用一个临时的空向量进行交换:
std::vector<int> v{ 1, 2, 3, 4, 5 };
std::vector<int>().swap(v); // v.size = 0, v.capacity = 0调用clear()方法只会移除向量中的所有元素，但不会释放任何内存。
应该注意的是，该向量实现了特定于其他类型容器的操作:
stack:末尾加push_back()``emplace_back()，末尾去掉pop_back()。请记住pop_back()不会返回最后一个被移除的元素。如果有必要，您需要显式地访问它，例如，在移除元素之前使用back()方法。list:用insert()和emplace()在序列中间添加元素，用erase()从序列的任何地方移除元素。
The rule of thumb for C++ containers is: use std::vector as the default container unless you have good reasons to use another one.
- 将位集用于固定大小的位序列
- 使用向量<布尔>用于可变大小的位序列
开发人员使用位标志进行操作并不少见；这可能是因为它们与通常用 C 编写的操作系统 API 一起工作，这些 API 采用位标志形式的各种类型的参数(如选项或样式)，也可能是因为它们与做类似事情的库一起工作，或者仅仅是因为某些类型的问题自然会用位标志来解决。可以考虑使用位和位操作的替代方法，例如定义每个选项/标志都有一个元素的数组，或者定义一个具有成员和函数的结构来模拟位标志，但是这些方法通常更复杂，如果需要将表示位标志的数值传递给函数，仍然需要将数组或结构转换为位序列。为此，C++ 标准为固定大小的位序列提供了一个名为std::bitset的容器。
对于这个方法，您必须熟悉按位运算(and、or、xor、not 和 shift)。
bitset类在<bitset>头中的std命名空间中可用。位集表示固定大小的位序列，其大小在编译时定义。为了方便起见，在这个配方中，所有的例子都是 8 位的位组。
要构造一个std::bitset对象，使用一个可用的构造函数:
- 所有位都设置为 0 的空位集:
std::bitset<8> b1; // [0,0,0,0,0,0,0,0]- 数值中的一个位组:
std::bitset<8> b2{ 10 }; // [0,0,0,0,1,0,1,0]- 由一串
'0'和'1'组成的位组:
std::bitset<8> b3{ "1010"s }; // [0,0,0,0,1,0,1,0]- 包含任意两个代表
'0'和'1'字符的字符串中的一个位组；在这种情况下，我们必须指定哪个字符代表 0，哪个字符代表 1:
std::bitset<8> b4
{ "ooooxoxo"s, 0, std::string::npos, 'o', 'x' };
// [0,0,0,0,1,0,1,0]要针对特定值测试集合中的单个位或整个集合，请使用任何可用的方法:
count()将位数设置为 1:
std::bitset<8> bs{ 10 };
std::cout << "has " << bs.count() << " 1s" << std::endl;any()检查是否至少有一位设置为 1:
if (bs.any()) std::cout << "has some 1s" << std::endl;all()检查是否所有位都设置为 1:
if (bs.all()) std::cout << "has only 1s" << std::endl;none()检查是否所有位都设置为 0:
if (bs.none()) std::cout << "has no 1s" << std::endl;test()检查单个位的值:
if (!bs.test(0)) std::cout << "even" << std::endl;operator[]要访问和测试单个位:
if(!bs[0]) std::cout << "even" << std::endl;要修改位集的内容，请使用以下任一方法:
- 成员运算符
|=、&=、^=和~执行二进制或、与、异或和非运算，或非成员运算符|、&和^:
std::bitset<8> b1{ 42 }; // [0,0,1,0,1,0,1,0]
std::bitset<8> b2{ 11 }; // [0,0,0,0,1,0,1,1]
auto b3 = b1 | b2; // [0,0,1,0,1,0,1,1]
auto b4 = b1 & b2; // [0,0,0,0,1,0,1,0]
auto b5 = b1 ^ b2; // [1,1,0,1,1,1,1,0]
auto b6 = ~b1; // [1,1,0,1,0,1,0,1]- 执行换档操作的成员操作员
<<=、<<、>>=、>>:
auto b7 = b1 << 2; // [1,0,1,0,1,0,0,0]
auto b8 = b1 >> 2; // [0,0,0,0,1,0,1,0]flip()将整组或单个位从 0 切换到 1 或从 1 切换到 0:
b1.flip(); // [1,1,0,1,0,1,0,1]
b1.flip(0); // [1,1,0,1,0,1,0,0]set()将整组或单个位更改为true或指定值:
b1.set(0, true); // [1,1,0,1,0,1,0,1]
b1.set(0, false); // [1,1,0,1,0,1,0,0]reset()将整组或单个位更改为假:
b1.reset(2); // [1,1,0,1,0,0,0,0]要将位集转换为数值或字符串值，请使用以下方法:
to_ulong()和to_ullong()转换为unsigned long或unsigned long long:
std::bitset<8> bs{ 42 };
auto n1 = bs.to_ulong(); // n1 = 42UL
auto n2 = bs.to_ullong(); // n2 = 42ULLto_string()转换为std::basic_string；默认情况下，结果是包含'0'和'1'的字符串，但是您可以为这两个值指定不同的字符:
auto s1 = bs.to_string(); // s1 = "00101010"
auto s2 = bs.to_string('o', 'x'); // s2 = "ooxoxoxo"如果您曾经使用过 C 或类似 C 的 API，那么很有可能您已经编写或至少已经看到了操作位来定义样式、选项或其他类型的值的代码。这通常涉及操作，例如:
- 定义位标志；这些可以是枚举、类中的静态常量，也可以是用 C 风格的
#define引入的宏。通常，有一个标志表示没有值(样式、选项等)。因为这些应该是位标志，所以它们的值是 2 的幂。 - 从集合中添加和移除标志(即数值)。添加位标志用位或运算符(
value |= FLAG)完成，移除位标志用位和运算符完成，取反标志(value &= ~FLAG)完成。 - 测试一个标志是否被添加到集合中(
value & FLAG == FLAG)。 - 以标志作为参数调用函数。
下面显示了一个简单的标志示例，用于定义控件的边框样式，该控件可以在左侧、右侧、顶部或底部有边框，也可以是它们的任意组合，包括没有边框:
#define BORDER_NONE 0x00
#define BORDER_LEFT 0x01
#define BORDER_TOP 0x02
#define BORDER_RIGHT 0x04
#define BORDER_BOTTOM 0x08
void apply_style(unsigned int const style)
{
if (style & BORDER_BOTTOM) { /* do something */ }
}
// initialize with no flags
unsigned int style = BORDER_NONE;
// set a flag
style = BORDER_BOTTOM;
// add more flags
style |= BORDER_LEFT | BORDER_RIGHT | BORDER_TOP;
// remove some flags
style &= ~BORDER_LEFT;
style &= ~BORDER_RIGHT;
// test if a flag is set
if ((style & BORDER_BOTTOM) == BORDER_BOTTOM) {}
// pass the flags as argument to a function
apply_style(style);标准的std::bitset类旨在作为这种类似于 C 的工作风格的 C++ 替代，具有多组位。它使我们能够编写更健壮和更安全的代码，因为它用成员函数抽象了位操作，尽管我们仍然需要识别集合中的每个位代表什么:
- 添加和删除标志是通过
set()和reset()方法完成的，这两种方法将由位置指示的位的值设置为 1 或 0(或true和false)；或者，我们可以出于同样的目的使用 index 运算符。 - 使用
test()方法测试是否设置了一个位。 - 从整数或字符串的转换是通过构造函数完成的，而到整数或字符串的转换是通过成员函数完成的，因此位集中的值可以用在需要整数的地方(例如函数的参数)。
除了上面提到的这些操作之外，bitset类还有额外的方法，用于对位执行按位操作、移位、测试，以及前面部分中显示的其他操作。
从概念上讲，std::bitset是一个数值的表示，使您能够访问和修改单个位。但是，在内部，一个位集有一个整数值数组，它在这个数组上执行位操作。位集的大小不限于数字类型的大小；它可以是任何东西，只是它是一个编译时常数。
上一节中带有控件边框样式的示例可以使用std::bitset以下列方式编写:
struct border_flags
{
static const int left = 0;
static const int top = 1;
static const int right = 2;
static const int bottom = 3;
};
// initialize with no flags
std::bitset<4> style;
// set a flag
style.set(border_flags::bottom);
// set more flags
style
.set(border_flags::left)
.set(border_flags::top)
.set(border_flags::right);
// remove some flags
style[border_flags::left] = 0;
style.reset(border_flags::right);
// test if a flag is set
if (style.test(border_flags::bottom)) {}
// pass the flags as argument to a function
apply_style(style.to_ulong());位集可以从整数创建，并且可以使用to_ulong()或to_ullong()方法将其值转换为整数。但是，如果位集的大小大于这些数字类型的大小，并且超出所请求的数字类型大小的任何位被设置为1，则这些方法抛出std::overflow_error异常，因为该值不能在unsigned long或unsigned long long上表示。为了提取所有位，我们需要执行以下操作，如下面的代码所示:
- 清除超出
unsigned long或unsigned long long大小的位。 - 将数值转换为
unsigned long或unsigned long long。 - 用
unsigned long或unsigned long long中的位数移动位组。 - 这样做，直到所有位都被检索到。
template <size_t N>
std::vector<unsigned long> bitset_to_vectorulong(std::bitset<N> bs)
{
auto result = std::vector<unsigned long> {};
auto const size = 8 * sizeof(unsigned long);
auto const mask = std::bitset<N>{ static_cast<unsigned long>(-1)};
auto totalbits = 0;
while (totalbits < N)
{
auto value = (bs & mask).to_ulong();
result.push_back(value);
bs >>= size;
totalbits += size;
}
return result;
}
std::bitset<128> bs =
(std::bitset<128>(0xFEDC) << 96) |
(std::bitset<128>(0xBA98) << 64) |
(std::bitset<128>(0x7654) << 32) |
std::bitset<128>(0x3210);
std::cout << bs << std::endl;
auto result = bitset_to_vectorulong(bs);
for (auto const v : result)
std::cout << std::hex << v << std::endl;对于编译时无法知道bitset大小的情况，另一种选择是std::vector<bool>，我们将在下一个配方中介绍。
- 使用向量<布尔>用于可变大小的位序列
在前面的配方中，我们考虑了将std::bitset用于固定大小的位序列。然而，有时std::bitset不是一个好的选择，因为你在编译时不知道位数，仅仅定义一组足够大的位数并不是一个好主意，因为你可能会遇到位数实际上不够大的情况。对此的标准替代方案是使用std::vector<bool>容器，这是std::vector的特殊化，具有空间和速度优化，因为实现实际上并不存储布尔值，而是存储每个元素的单个位。
For this reason, however, std::vector<bool> does not meet the requirements of a standard container or sequential container, nor does std::vector<bool>::iterator meet the requirements of a forward iterator. As a result, this specialization cannot be used in generic code where a vector is expected. On the other hand, being a vector, it has a different interface from that of std::bitset and cannot be viewed as a binary representation of a number. There are no direct ways to construct std::vector<bool> from a number or string nor to convert to a number or string.
这个食谱假设你熟悉std::vector和std::bitset。如果您没有阅读前面的食谱，使用向量作为默认容器和使用位集作为固定大小的位序列，您应该在继续之前这样做。
vector<bool>类在<vector>头中的std命名空间中可用。
要操纵std::vector<bool>，请使用与操纵std::vector<T>相同的方法，如下例所示:
- 创建一个空向量:
std::vector<bool> bv; // []- 向向量添加位:
bv.push_back(true); // [1]
bv.push_back(true); // [1, 1]
bv.push_back(false); // [1, 1, 0]
bv.push_back(false); // [1, 1, 0, 0]
bv.push_back(true); // [1, 1, 0, 0, 1]- 设置各个位的值:
bv[3] = true; // [1, 1, 0, 1, 1]- 使用通用算法:
auto count_of_ones = std::count(bv.cbegin(), bv.cend(), true);- 从向量中移除位:
bv.erase(bv.begin() + 2); // [1, 1, 1, 1]std::vector<bool>不是标准向量，因为它被设计为通过为每个元素存储单个位而不是布尔值来提供空间优化。因此，它的元素不是以连续的序列存储的，不能替换布尔数组。正因为如此:
- 索引运算符不能返回对特定元素的引用，因为元素不是单独存储的:
std::vector<bool> bv;
bv.resize(10);
auto& bit = bv[0]; // error- 出于前面提到的相同原因，对迭代器取消引用不能产生对
bool的引用:
auto& bit = *bv.begin(); // error- 不能保证单个位可以从不同的线程同时独立操作。
- 向量不能与需要前向迭代器的算法一起使用，例如
std::search()。 - 向量不能用在期望使用
std::vector<T>的通用代码中，如果该代码需要本列表中提到的任何操作。
An alternative to std::vector<bool> is std::dequeu<bool>, which is a standard container (a double-ended queue) that meets all container and iterator requirements and can be used with all standard algorithms. However, this will not have the space optimization that std::vector<bool> is providing.
std::vector<bool>界面与std::bitset有很大不同。如果您希望能够以类似的方式编写代码，您可以在std::vector<bool>上创建一个包装器，在可能的情况下，它看起来像std::bitset。以下实现提供了类似于std::bitset的成员:
class bitvector
{
std::vector<bool> bv;
public:
bitvector(std::vector<bool> const & bv) : bv(bv) {}
bool operator[](size_t const i) { return bv[i]; }
inline bool any() const {
for (auto b : bv) if (b) return true;
return false;
}
inline bool all() const {
for (auto b : bv) if (!b) return false;
return true;
}
inline bool none() const { return !any(); }
inline size_t count() const {
return std::count(bv.cbegin(), bv.cend(), true);
}
inline size_t size() const { return bv.size(); }
inline bitvector & add(bool const value) {
bv.push_back(value);
return *this;
}
inline bitvector & remove(size_t const index) {
if (index >= bv.size())
throw std::out_of_range("Index out of range");
bv.erase(bv.begin() + index);
return *this;
}
inline bitvector & set(bool const value = true) {
for (size_t i = 0; i < bv.size(); ++ i)
bv[i] = value;
return *this;
}
inline bitvector& set(size_t const index, bool const value = true) {
if (index >= bv.size())
throw std::out_of_range("Index out of range");
bv[index] = value;
return *this;
}
inline bitvector & reset() {
for (size_t i = 0; i < bv.size(); ++ i) bv[i] = false;
return *this;
}
inline bitvector & reset(size_t const index) {
if (index >= bv.size())
throw std::out_of_range("Index out of range");
bv[index] = false;
return *this;
}
inline bitvector & flip() {
bv.flip();
return *this;
}
std::vector<bool>& data() { return bv; }
};这只是一个基本的实现，如果您想使用这样的包装器，您应该添加额外的方法，例如位逻辑操作、移位、可能从流读取和向流写入等等。但是，使用前面的代码，我们可以编写以下示例:
bitvector bv;
bv.add(true).add(true).add(false); // [1, 1, 0]
bv.add(false); // [1, 1, 0, 0]
bv.add(true); // [1, 1, 0, 0, 1]
if (bv.any()) std::cout << "has some 1s" << std::endl;
if (bv.all()) std::cout << "has only 1s" << std::endl;
if (bv.none()) std::cout << "has no 1s" << std::endl;
std::cout << "has " << bv.count() << " 1s" << std::endl;
bv.set(2, true); // [1, 1, 1, 0, 1]
bv.set(); // [1, 1, 1, 1, 1]
bv.reset(0); // [0, 1, 1, 1, 1]
bv.reset(); // [0, 0, 0, 0, 0]
bv.flip(); // [1, 1, 1, 1, 1]- 使用矢量作为默认容器
- 将位集用于固定大小的位序列
我们在任何应用中最常见的操作之一是搜索数据。因此，标准库提供了许多通用算法来搜索标准容器或任何可以表示一个范围并由开始迭代器和结束迭代器定义的东西，这并不奇怪。在这个食谱中，我们将看到这些标准算法是什么，以及如何使用它们。
对于本食谱中的所有示例，我们将使用std::vector，但是所有算法都使用由开始和结束定义的范围，输入迭代器或前向迭代器，这取决于算法(有关各种类型迭代器的更多信息，请参见食谱，编写您自己的随机访问迭代器)。所有这些算法都可以在<algorithm>头中的std命名空间中获得。
以下是可用于查找范围内元素的算法列表:
- 使用
std::find()在一个范围内寻找一个值；这个算法返回一个迭代器到等于值的第一个元素:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::find(v.cbegin(), v.cend(), 3);
if (it != v.cend()) std::cout << *it << std::endl;- 使用
std::find_if()从一元谓词中找到符合标准的范围内的值；该算法将迭代器返回到谓词返回的第一个元素true:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::find_if(v.cbegin(), v.cend(),
[](int const n) {return n > 10; });
if (it != v.cend()) std::cout << *it << std::endl;- 使用
std::find_if_not()从一元谓词中查找范围内不符合标准的值；该算法将迭代器返回到谓词返回的第一个元素false:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::find_if_not(v.cbegin(), v.cend(),
[](int const n) {return n % 2 == 1; });
if (it != v.cend()) std::cout << *it << std::endl;- 使用
std::find_first_of()从一个范围中搜索另一个范围中任何值的出现；该算法返回找到的第一个元素的迭代器:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
std::vector<int> p{ 5, 7, 11 };
auto it = std::find_first_of(v.cbegin(), v.cend(),
p.cbegin(), p.cend());
if (it != v.cend())
std::cout << "found " << *it
<< " at index " << std::distance(v.cbegin(), it)
<< std::endl;- 使用
std::find_end()查找一个范围内元素子范围的最后一次出现；这个算法返回一个迭代器到范围中最后一个子范围的第一个元素:
std::vector<int> v1{ 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1 };
std::vector<int> v2{ 1, 0, 1 };
auto it = std::find_end(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend());
if (it != v1.cend())
std::cout << "found at index "
<< std::distance(v1.cbegin(), it) << std::endl;- 使用
std::search()搜索某个范围内某个子范围的第一次出现；这个算法返回一个迭代器到范围内子范围的第一个元素:
auto text = "The quick brown fox jumps over the lazy dog"s;
auto word = "over"s;
auto it = std::search(text.cbegin(), text.cend(),
word.cbegin(), word.cend());
if (it != text.cend())
std::cout << "found " << word
<< " at index "
<< std::distance(text.cbegin(), it) << std::endl;- 将
std::search()与搜索器一起使用，这是一个实现搜索算法并满足某些预定义标准的类。std::search()的这种过载是在 C++ 17 中引入的，可用的标准搜索程序实现了博耶-摩尔和博耶-摩尔-霍斯普字符串搜索算法:
auto text = "The quick brown fox jumps over the lazy dog"s;
auto word = "over"s;
auto it = std::search(
text.cbegin(), text.cend(),
std::make_boyer_moore_searcher(word.cbegin(), word.cend()));
if (it != text.cend())
std::cout << "found " << word
<< " at index "
<< std::distance(text.cbegin(), it) << std::endl;- 使用
std::search_n()搜索某个值在某个范围内连续出现的N；这个算法返回一个迭代器到找到的序列的第一个元素:
std::vector<int> v{ 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1 };
auto it = std::search_n(v.cbegin(), v.cend(), 2, 0);
if (it != v.cend())
std::cout << "found at index "
<< std::distance(v.cbegin(), it) << std::endl;- 使用
std::adjacent_find()查找范围内相等或满足二元谓词的两个相邻元素；该算法返回找到的第一个元素的迭代器:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::adjacent_find(v.cbegin(), v.cend());
if (it != v.cend())
std::cout << "found at index "
<< std::distance(v.cbegin(), it) << std::endl;
auto it = std::adjacent_find(
v.cbegin(), v.cend(),
[](int const a, int const b) {
return IsPrime(a) && IsPrime(b); });
if (it != v.cend())
std::cout << "found at index "
<< std::distance(v.cbegin(), it) << std::endl;- 使用
std::binary_search()查找排序范围内是否存在元素；该算法返回一个布尔值来指示是否找到该值:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto success = std::binary_search(v.cbegin(), v.cend(), 8);
if (success) std::cout << "found" << std::endl;- 使用
std::lower_bound()在不小于指定值的范围内找到第一个元素；该算法返回元素的迭代器:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::lower_bound(v.cbegin(), v.cend(), 1);
if (it != v.cend())
std::cout << "lower bound at "
<< std::distance(v.cbegin(), it) << std::endl;- 使用
std::upper_bound()在大于指定值的范围内找到第一个元素；该算法返回元素的迭代器:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::upper_bound(v.cbegin(), v.cend(), 1);
if (it != v.cend())
std::cout << "upper bound at "
<< std::distance(v.cbegin(), it) << std::endl;- 使用
std::equal_range()在一个值等于指定值的范围内寻找一个子范围。该算法返回一对迭代器，定义子范围的第一个迭代器和最后一个迭代器；这两个迭代器相当于std::lower_bound()和std::upper_bound()返回的迭代器:
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto bounds = std::equal_range(v.cbegin(), v.cend(), 1);
std::cout << "range between indexes "
<< std::distance(v.cbegin(), bounds.first)
<< " and "
<< std::distance(v.cbegin(), bounds.second)
<< std::endl;这些算法的工作方式非常相似:它们都将迭代器作为参数，迭代器定义了可搜索的范围和依赖于每个算法的附加参数。除了返回布尔值的std::search()和返回一对迭代器的std::equal_range()之外，它们都向搜索到的元素或子范围返回一个迭代器。这些迭代器必须与范围的结束迭代器(即过去最后一个元素)进行比较，以检查搜索是否成功。如果搜索没有找到元素或子范围，那么返回值就是结束迭代器。
所有这些算法都有多个重载，但是在*怎么做呢...*部分，我们只看了一个特定的重载来展示如何使用该算法。有关所有重载的完整引用，您应该会看到其他来源。
在前面的例子中，我们使用了常量迭代器，但是所有这些算法对于可变迭代器和反向迭代器都是一样的。因为它们将迭代器作为输入参数，所以它们可以使用标准容器、类似 C 的数组或任何表示序列并有迭代器可用的东西。
关于std::binary_search()算法需要特别注意的是:定义搜索范围的迭代器参数至少要满足前向迭代器的要求。不管提供的迭代器的类型如何，比较的次数总是以范围的大小为对数。但是，如果迭代器是随机访问的，则迭代器增量的数量是不同的，在这种情况下，增量的数量也是对数的，或者不是随机访问的，在这种情况下，增量的数量是线性的，并且与范围的大小成比例。
除了std::find_if_not()之外，所有这些算法在 C++ 11 之前都是可用的。然而，在较新的标准中引入了它们的一些重载。一个例子是std::search()，它有几个在 C++ 17 中引入的重载。其中一个重载具有以下形式:
template<class ForwardIterator, class Searcher>
ForwardIterator search(ForwardIterator first, ForwardIterator last,
const Searcher& searcher );这个重载搜索由标准提供了几种实现的搜索器函数对象定义的模式的出现:
default_searcher基本上将搜索委托给标准的std::search()算法。boyer_moore_searcher实现了用于字符串搜索的 Boyer-Moore 算法。boyer_moore_horspool_algorithm实现了用于字符串搜索的 Boyer-Moore-Horspool 算法。
许多标准容器都有一个成员函数find()，用于查找容器中的元素。当这样的方法可用并且适合您的需求时，它应该优先于通用算法，因为这些成员函数是基于每个容器的特殊性进行优化的。
- 使用矢量作为默认容器
- 初始化范围
- 在范围内使用设定操作
- 排序范围
在前面的食谱中，我们研究了在一定范围内搜索的标准通用算法。我们经常需要做的另一个常见操作是对一个范围进行排序，因为许多例程，包括一些搜索算法，都需要一个排序的范围。标准库提供了几种排序范围的通用算法，在本食谱中，我们将了解这些算法是什么以及如何使用它们。
排序一般算法使用由开始和结束迭代器定义的范围，因此，可以对标准容器、类似 C 的数组或任何表示序列并有随机迭代器可用的东西进行排序。但是，本食谱中的所有例子都将使用std::vector。
以下是搜索范围的标准通用算法列表:
- 使用
std::sort()对范围进行排序:
std::vector<int> v{3, 13, 5, 8, 1, 2, 1};
std::sort(v.begin(), v.end());
// v = {1, 1, 2, 3, 5, 8, 13}
std::sort(v.begin(), v.end(), std::greater<>());
// v = {13, 8, 5, 3, 2, 1 ,1}- 使用
std::stable_sort()对一个范围进行排序，但保持相等元素的顺序:
struct Task
{
int priority;
std::string name;
};
bool operator<(Task const & lhs, Task const & rhs) {
return lhs.priority < rhs.priority;
}
bool operator>(Task const & lhs, Task const & rhs) {
return lhs.priority > rhs.priority;
}
std::vector<Task> v{
{ 10, "Task 1"s }, { 40, "Task 2"s }, { 25, "Task 3"s },
{ 10, "Task 4"s }, { 80, "Task 5"s }, { 10, "Task 6"s },
};
std::stable_sort(v.begin(), v.end());
// {{ 10, "Task 1" },{ 10, "Task 4" },{ 10, "Task 6" },
// { 25, "Task 3" },{ 40, "Task 2" },{ 80, "Task 5" }}
std::stable_sort(v.begin(), v.end(), std::greater<>());
// {{ 80, "Task 5" },{ 40, "Task 2" },{ 25, "Task 3" },
// { 10, "Task 1" },{ 10, "Task 4" },{ 10, "Task 6" }}- 使用
std::partial_sort()对一个范围的一部分进行排序(并以未指定的顺序保留其余部分):
std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
std::partial_sort(v.begin(), v.begin() + 4, v.end());
// v = {1, 1, 2, 3, ?, ?, ?}
std::partial_sort(v.begin(), v.begin() + 4, v.end(),
std::greater<>());
// v = {13, 8, 5, 3, ?, ?, ?}- 使用
std::partial_sort_copy()通过将排序后的元素复制到第二个范围并保持原始范围不变来排序一个范围的一部分:
std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
std::vector<int> vc(v.size());
std::partial_sort_copy(v.begin(), v.end(),
vc.begin(), vc.end());
// v = {3, 13, 5, 8, 1, 2, 1}
// vc = {1, 1, 2, 3, 5, 8, 13}
std::partial_sort_copy(v.begin(), v.end(),
vc.begin(), vc.end(), std::greater<>());
// vc = {13, 8, 5, 3, 2, 1, 1}- 使用
std::nth_element()对一个范围进行排序，使得 N 第一个元素是如果该范围被完全排序的话会在该位置的元素，并且它之前的元素都较小，而它之后的元素都较大，不保证它们也被排序:
std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
std::nth_element(v.begin(), v.begin() + 3, v.end());
// v = {1, 1, 2, 3, 5, 8, 13}
std::nth_element(v.begin(), v.begin() + 3, v.end(),
std::greater<>());
// v = {13, 8, 5, 3, 2, 1, 1}- 使用
std::is_sorted()检查范围是否排序:
std::vector<int> v { 1, 1, 2, 3, 5, 8, 13 };
auto sorted = std::is_sorted(v.cbegin(), v.cend());
sorted = std::is_sorted(v.cbegin(), v.cend(),
std::greater<>());- 使用
std::is_sorted_until()从一个范围的开始找到一个排序的子范围:
std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
auto it = std::is_sorted_until(v.cbegin(), v.cend());
auto length = std::distance(v.cbegin(), it);前面所有的通用算法都将随机迭代器作为参数来定义要排序的范围，并且其中一些算法还会获取一个输出范围。它们都有重载，一个需要比较函数对元素进行排序，一个不需要，使用operator<对元素进行比较。
这些算法的工作方式如下:
std::stable_sort()与std::sort()类似，但保证保持元素相等的原始顺序。std::partial_sort()取三个迭代器参数，表示一个范围内的第一个、中间的和最后一个元素，其中中间可以是任何元素，而不仅仅是自然中间位置的元素。结果是部分排序范围，使得来自原始范围的第一个middle - first最小元素，即[first, last)，在[first, middle)子范围中找到，而其余元素在[middle, last)子范围中以未指定的顺序出现。std::partial_sort_copy()不是std::partial_copy()的变体，正如名字所暗示的那样，而是std::sort()的变体。它通过将其元素复制到输出范围来对范围进行排序，而不改变它。算法的参数是输入和输出范围的第一个和最后一个迭代器。如果输出范围的大小 M 大于或等于输入范围的大小 N ，则输入范围被完全排序并复制到输出范围；输出范围的前 N 元素被覆盖，最后的 M - N 元素保持不变。如果输出范围小于输入范围，那么只有来自输入范围的第一个 M 排序的元素被复制到输出范围(在这种情况下被完全覆盖)。std::nth_element()基本上是一种选择算法的实现，这是一种寻找范围中第 N 个最小元素的算法。该算法采用三个迭代器参数来表示第一个、 N 和最后一个元素，并对该范围进行部分排序，以便在排序后，如果该范围已被完全排序，则第 N 个元素将位于该位置。在修改范围内，第 n 个元素之前的所有 N-1 个元素都小于它，第 n 个元素之后的所有元素都大于它。但是，这些其他元素的顺序没有保证。std::is_sorted()检查指定范围是否根据指定或默认的比较函数排序，并返回一个布尔值来指示。std::is_sorted_until()使用提供的比较函数或默认的operator<，从开始查找指定范围的排序子范围。返回值是一个迭代器，表示排序子范围的上限，也是最后一个排序元素的迭代器。
一些标准容器std::list和std::forward_list提供了一个成员函数sort()，该函数针对这些容器进行了优化。这些成员函数应该优先于通用标准算法std::sort()。
- 使用矢量作为默认容器
- 初始化范围
- 在范围内使用设定操作
- 寻找范围内的元素
在前面的食谱中，我们探索了搜索范围和排序范围的通用标准算法。算法库提供了许多其他通用算法，其中有几个是用来填充值范围的。在这个食谱中，你将学习这些算法是什么，以及它们应该如何使用。
本食谱中所有的例子都使用std::vector。然而，像所有一般的算法一样，我们将在本食谱中看到的算法使用迭代器来定义范围的边界，因此可以与任何标准容器、C 类数组或表示定义了前向迭代器的序列的自定义类型一起使用。
除了<numeric>头中的std::iota()外，其他算法都在<algorithm>头中。
要为范围赋值，请使用以下标准算法之一:
std::fill()给一个范围的所有元素赋值；范围由第一个和最后一个前向迭代器定义:
std::vector<int> v(5);
std::fill(v.begin(), v.end(), 42);
// v = {42, 42, 42, 42, 42}std::fill_n()给一个范围的多个元素赋值；该范围由第一个前向迭代器和一个计数器定义，该计数器指示有多少元素应该被赋予指定的值:
std::vector<int> v(10);
std::fill_n(v.begin(), 5, 42);
// v = {42, 42, 42, 42, 42, 0, 0, 0, 0, 0}std::generate()将函数返回的值赋给一个范围的元素；该范围由第一个和最后一个前向迭代器定义，并且对该范围中的每个元素调用一次函数:
std::random_device rd{};
std::mt19937 mt{ rd() };
std::uniform_int_distribution<> ud{1, 10};
std::vector<int> v(5);
std::generate(v.begin(), v.end(),
[&ud, &mt] {return ud(mt); }); std::generate_n()将函数返回的值赋给一个范围的多个元素；该范围由第一个前向迭代器和一个计数器来定义，该计数器指示有多少元素应该被分配来自函数的值，该函数为每个元素调用一次:
std::vector<int> v(5);
auto i = 1;
std::generate_n(v.begin(), v.size(), [&i] { return i*i++ ; });
// v = {1, 4, 9, 16, 25}std::iota()给一个范围的元素分配顺序递增的值；范围由第一个和最后一个前向迭代器定义，值使用前缀operator++从初始指定值开始递增:
std::vector<int> v(5);
std::iota(v.begin(), v.end(), 1);
// v = {1, 2, 3, 4, 5}std::fill()和std::fill_n()的工作原理类似，但不同之处在于指定范围的方式:前者由第一个和最后一个迭代器指定，后者由第一个迭代器和计数指定。第二个算法返回一个迭代器，如果计数器大于零，则表示最后一个赋值的元素，否则表示范围第一个元素的迭代器。
std::generate()和std::generate_n()也相似，不同之处仅在于范围的规定方式。第一个使用两个迭代器，定义范围的上下限，第二个使用第一个元素的迭代器和一个计数。与std::fill_n()类似，std::generate_n()也返回一个迭代器，如果计数大于零，则表示最后一个赋值的元素，否则表示范围第一个元素的迭代器。这些算法为范围中的每个元素调用指定的函数，并将返回值赋给元素。生成函数不接受任何参数，因此参数的值不能传递给函数，因为这是用来初始化范围元素的函数。如果需要使用元素的值生成新的值，应该使用std::transform()。
std::iota()它的名字来自 APL 编程语言的ι (iota)函数，虽然它是初始 STL 的一部分，但它只包含在 C++ 11 的标准库中。该函数将第一个和最后一个迭代器带到一个范围，并将初始值分配给该范围的第一个元素，然后使用前缀operator++ 为该范围中的其余元素生成顺序递增的值。
标准库为集合运算提供了几种算法，使我们能够对排序范围进行并集、交集或差集。在这个食谱中，我们将看到这些算法是什么以及它们是如何工作的。
集合运算的算法与迭代器一起工作，这意味着它们可以用于标准容器、类似 C 的数组或任何表示具有可用输入迭代器的序列的自定义类型。本食谱中的所有例子都将使用std::vector。
对于下一节中的所有示例，我们将使用以下范围:
std::vector<int> v1{ 1, 2, 3, 4, 4, 5 };
std::vector<int> v2{ 2, 3, 3, 4, 6, 8 };
std::vector<int> v3;对集合运算使用以下通用算法:
std::set_union()计算两个范围合并成第三个范围:
std::set_union(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v3));
// v3 = {1, 2, 3, 3, 4, 4, 5, 6, 8}std::merge()将两个范围的内容合并成第三个范围；这与std::set_union()类似，只是它将输入范围的全部内容复制到输出范围中，而不仅仅是它们的联合:
std::merge(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v3));
// v3 = {1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 8}std::set_intersection()计算两个范围的交集进入第三个范围:
std::set_intersection(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v3));
// v3 = {2, 3, 4}std::set_difference()将两个范围之差计算成第三个范围；输出范围将包含第一个范围中的元素，这些元素不在第二个范围中:
std::set_difference(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v3));
// v3 = {1, 4, 5}std::set_symmetric_difference()计算两个范围到第三范围的对偶差；输出范围将包含存在于任何输入范围中的元素，但只存在于一个范围中:
std::set_symmetric_difference(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v3));
// v3 = {1, 3, 4, 5, 6, 8}std::includes()检查一个范围是否是另一个范围的子集(即其所有元素也存在于另一个范围中):
std::vector<int> v1{ 1, 2, 3, 4, 4, 5 };
std::vector<int> v2{ 2, 3, 3, 4, 6, 8 };
std::vector<int> v3{ 1, 2, 4 };
std::vector<int> v4{ };
auto i1 = std::includes(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend()); // i1 = false
auto i2 = std::includes(v1.cbegin(), v1.cend(),
v3.cbegin(), v3.cend()); // i2 = true
auto i3 = std::includes(v1.cbegin(), v1.cend(),
v4.cbegin(), v4.cend()); // i3 = true事实上，从两个输入范围生成新范围的所有 set 操作都具有相同的接口，并且工作方式相似:
- 它们接受两个输入范围，每个范围由第一个和最后一个输入迭代器定义。
- 他们将输出迭代器带到要插入元素的输出范围。
- 它们有一个重载，该重载接受一个表示比较二进制函数对象的额外参数，如果第一个参数小于第二个参数，则该对象必须返回
true。未指定比较函数对象时，使用operator<。 - 它们在构造的输出范围结束后返回一个迭代器。
- 根据所使用的过载，必须使用
operator<或提供的比较功能对输入范围进行排序。 - 输出范围不得与两个输入范围重叠。
我们将使用 POD 类型的向量Task通过额外的例子来演示它们的工作方式，我们在之前的配方中也使用了该向量:
struct Task
{
int priority;
std::string name;
};
bool operator<(Task const & lhs, Task const & rhs) {
return lhs.priority < rhs.priority;
}
bool operator>(Task const & lhs, Task const & rhs) {
return lhs.priority > rhs.priority;
}
std::vector<Task> v1{
{ 10, "Task 1.1"s },
{ 20, "Task 1.2"s },
{ 20, "Task 1.3"s },
{ 20, "Task 1.4"s },
{ 30, "Task 1.5"s },
{ 50, "Task 1.6"s },
};
std::vector<Task> v2{
{ 20, "Task 2.1"s },
{ 30, "Task 2.2"s },
{ 30, "Task 2.3"s },
{ 30, "Task 2.4"s },
{ 40, "Task 2.5"s },
{ 50, "Task 2.6"s },
};这里描述了每种算法产生输出范围的具体方式:
std::set_union()将一个或两个输入范围中的所有元素复制到输出范围，产生一个新的排序范围。如果一个元素在第一个范围内被发现 M 次，在第二个范围内被发现 N 次，那么第一个范围内的所有 M 元素将以它们现有的顺序被复制到输出范围，然后第二个范围内的 N-M 元素被复制到输出范围，如果 N > M 则为 0 个元素，否则为:
std::vector<Task> v3;
std::set_union(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v3));
// v3 = {{10, "Task 1.1"},{20, "Task 1.2"},{20, "Task 1.3"},
// {20, "Task 1.4"},{30, "Task 1.5"},{30, "Task 2.3"},
// {30, "Task 2.4"},{40, "Task 2.5"},{50, "Task 1.6"}}std::merge()将两个输入范围内的所有元素复制到输出范围内，产生一个根据比较函数排序的新范围:
std::vector<Task> v4;
std::merge(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v4));
// v4 = {{10, "Task 1.1"},{20, "Task 1.2"},{20, "Task 1.3"},
// {20, "Task 1.4"},{20, "Task 2.1"},{30, "Task 1.5"},
// {30, "Task 2.2"},{30, "Task 2.3"},{30, "Task 2.4"},
// {40, "Task 2.5"},{50, "Task 1.6"},{50, "Task 2.6"}}std::set_intersection()将在两个输入范围内找到的所有元素复制到输出范围内，产生一个根据比较函数排序的新范围:
std::vector<Task> v5;
std::set_intersection(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v5));
// v5 = {{20, "Task 1.2"},{30, "Task 1.5"},{50, "Task 1.6"}}std::set_difference()将第一个输入范围中在第二个输入范围中找不到的所有元素复制到输出范围。对于在两个范围内找到的等价元素，以下规则适用:如果一个元素在第一个范围内找到 M 次，在第二个范围内找到 N 次，如果 M > N 次，则复制 M-N 次；否则不复制:
std::vector<Task> v6;
std::set_difference(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v6));
// v6 = {{10, "Task 1.1"},{20, "Task 1.3"},{20, "Task 1.4"}}std::set_symmetric_difference()将两个输入范围中任何一个范围内的所有元素复制到输出范围，但不复制到两个范围内。如果一个元素在第一个范围内被发现 M 次，在第二个范围内被发现 N 次，那么如果来自第一个范围的那些元素的最后 *M > N、*M-N 被复制到输出范围内，否则，来自第二个范围的那些元素的最后 N-M 将被复制到输出范围内:
std::vector<Task> v7;
std::set_symmetric_difference(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(v7));
// v7 = {{10, "Task 1.1"},{20, "Task 1.3"},{20, "Task 1.4"}
// {30, "Task 2.3"},{30, "Task 2.4"},{40, "Task 2.5"}}另一方面，std::includes()不产生输出范围；它只检查第二范围是否包括在第一范围内。如果第二个范围为空或其所有元素都包含在第一个范围内，则返回一个布尔值true，否则返回false。它还有两个重载，其中一个重载指定了一个比较二进制函数对象。
- 使用矢量作为默认容器
- 排序范围
- 初始化范围
- 使用迭代器在容器中插入新元素
- 寻找范围内的元素
当您使用容器时，在开头、结尾或中间的某个地方插入新元素通常很有用。有一些算法，比如我们在前面的食谱中看到的，在一个范围上使用 set 操作，需要一个迭代器到一个要插入的范围，但是如果你简单地传递一个迭代器，比如begin()返回的迭代器，它不会插入而是覆盖容器的元素。而且，使用end()返回的迭代器是不可能在末尾插入的。为了执行这样的操作，标准库提供了一组迭代器和迭代器适配器来实现这些场景。
本食谱中讨论的迭代器和适配器可以在<iterator>头中的std命名空间中找到。如果包含诸如<algorithm>之类的标题，则不必明确包含<iterator>。
使用以下迭代器适配器在容器中插入新元素:
std::back_inserter()在末端插入元素，对于有push_back()方法的容器:
std::vector<int> v{ 1,2,3,4,5 };
std::fill_n(std::back_inserter(v), 3, 0);
// v={1,2,3,4,5,0,0,0}std::front_inserter()在开头插入元素，对于有push_front()方法的容器:
std::list<int> l{ 1,2,3,4,5 };
std::fill_n(std::front_inserter(l), 3, 0);
// l={0,0,0,1,2,3,4,5}std::inserter()插入容器中的任何位置，对于具有insert()方法的容器:
std::vector<int> v{ 1,2,3,4,5 };
std::fill_n(std::inserter(v, v.begin()), 3, 0);
// v={0,0,0,1,2,3,4,5}
std::list<int> l{ 1,2,3,4,5 };
auto it = l.begin();
std::advance(it, 3);
std::fill_n(std::inserter(l, it), 3, 0);
// l={1,2,3,0,0,0,4,5}std::back_inserter()、std::front_inserter()和std::inserter()都是帮助函数，它们创建类型为std::back_insert_iterator、std::front_insert_iterator和std::insert_iterator的迭代器适配器。这些都是输出迭代器，它们追加、前置或插入到为其构建的容器中。递增和取消引用这些迭代器没有任何作用。但是，在赋值时，这些迭代器从容器中调用以下方法:
std::back_insterter_iterator呼叫push_back()std::front_inserter_iterator呼叫push_front()std::insert_iterator呼叫insert()
以下是std::back_inserter_iterator的过度简化实现:
template<class C>
class back_insert_iterator {
public:
typedef back_insert_iterator<C> T;
typedef typename C::value_type V;
explicit back_insert_iterator( C& c ) :container( &c ) { }
T& operator=( const V& val ) {
container->push_back( val );
return *this;
}
T& operator*() { return *this; }
T& operator++() { return *this; }
T& operator++( int ) { return *this; }
protected:
C* container;
};由于赋值运算符的工作方式，这些迭代器只能用于一些标准容器:
std::back_insert_iterator可搭配std::vector、std::list、std::deque、std::basic_string使用。std::front_insert_iterator可与std::list、std::forward_list、std:deque配合使用。std::insert_iterator可用于所有标准容器。
以下示例在std::vector的开头插入三个值为 0 的元素:
std::vector<int> v{ 1,2,3,4,5 };
std::fill_n(std::inserter(v, v.begin()), 3, 0);
// v={0,0,0,1,2,3,4,5}std::inserter()适配器接受两个参数:容器和元素应该插入的迭代器。在容器上调用insert()时，std::insert_iterator递增迭代器，因此再次被赋值时，它可以在下一个位置插入一个新元素。下面是如何为这个迭代器适配器实现赋值运算符:
T& operator=(const V& v)
{
iter = container->insert(iter, v);
++ iter;
return (*this);
}这些迭代器适配器旨在与将多个元素插入一个范围的算法或函数一起使用。当然，它们可以用来插入单个元素，但这是一种反模式，因为在这种情况下，简单地调用push_back()、push_front()或insert()要简单和直观得多。应避免以下示例:
std::vector<int> v{ 1,2,3,4,5 };
*std::back_inserter(v) = 6; // v = {1,2,3,4,5,6}
std::back_insert_iterator<std::vector<int>> it(v);
*it = 7; // v = {1,2,3,4,5,6,7}- 在范围内使用设定操作
在第 8 章、学习现代核心语言特性中，我们看到了如何通过实现迭代器和释放begin()和end()函数将迭代器返回到自定义范围的第一个和最后一个元素，从而为自定义类型启用基于范围的循环。您可能已经注意到，我们在该方法中提供的最小迭代器实现不符合标准迭代器的要求，因为它不能被复制构造或赋值，也不能被递增。在这个食谱中，我们将建立在这个例子的基础上，并展示如何创建一个满足所有要求的随机访问迭代器。
对于这个方法，您应该知道标准定义的迭代器的类型以及它们的不同之处。在http://www.cplusplus.com/reference/iterator/可以很好地了解他们的需求。
为了举例说明如何编写随机访问迭代器，我们将考虑在中使用的dummy_array类的一个变体，为自定义类型的循环启用基于范围的第 8 章、学习现代核心语言特性的配方。这是一个非常简单的数组概念，除了作为演示迭代器的代码库之外，没有任何实际价值:
template <typename Type, size_t const SIZE>
class dummy_array
{
Type data[SIZE] = {};
public:
Type& operator[](size_t const index)
{
if (index < SIZE) return data[index];
throw std::out_of_range("index out of range");
}
Type const & operator[](size_t const index) const
{
if (index < SIZE) return data[index];
throw std::out_of_range("index out of range");
}
size_t size() const { return SIZE; }
};下一节中显示的所有代码，迭代器类，typedef s，begin()和end()函数，都是这个类的一部分。
要为上一节中显示的dummy_array类提供可变的和恒定的随机访问迭代器，请向该类添加以下成员:
- 迭代器类模板，用元素类型和数组大小参数化。该类必须有以下定义标准同义词的公共
typedef:
template <typename T, size_t const Size>
class dummy_array_iterator
{
public:
typedef dummy_array_iterator self_type;
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef std::random_access_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
};- 迭代器类的私有成员:指向数组数据的指针和数组的当前索引:
private:
pointer ptr = nullptr;
size_t index = 0;- 迭代器类的私有方法，用于检查两个迭代器实例是否指向相同的数组数据:
private:
bool compatible(self_type const & other) const
{
return ptr == other.ptr;
}- 迭代器类的显式构造函数:
public:
explicit dummy_array_iterator(pointer ptr,
size_t const index)
: ptr(ptr), index(index) { }- 迭代器类成员满足所有迭代器的通用要求:可复制构造、可复制分配、可析构、前缀和后缀可递增。在这种实现方式中，后递增运算符是根据前递增运算符实现的，以避免代码重复:
dummy_array_iterator(dummy_array_iterator const & o)
= default;
dummy_array_iterator& operator=(dummy_array_iterator const & o)
= default;
~dummy_array_iterator() = default;
self_type & operator++ ()
{
if (index >= Size)
throw std::out_of_range("Iterator cannot be incremented past
the end of range.");
++ index;
return *this;
}
self_type operator++ (int)
{
self_type tmp = *this;
++*this;
return tmp;
}- 满足输入迭代器要求的迭代器类成员:测试等式/不等式，作为右值取消引用:
bool operator== (self_type const & other) const
{
assert(compatible(other));
return index == other.index;
}
bool operator!= (self_type const & other) const
{
return !(*this == other);
}
reference operator* () const
{
if (ptr == nullptr)
throw std::bad_function_call();
return *(ptr + index);
}
reference operator-> () const
{
if (ptr == nullptr)
throw std::bad_function_call();
return *(ptr + index);
}- 满足前向迭代器要求的迭代器类成员:默认可构造:
dummy_array_iterator() = default;- 满足双向迭代器要求的迭代器类成员:
self_type & operator--()
{
if (index <= 0)
throw std::out_of_range("Iterator cannot be decremented
past the end of range.");
--index;
return *this;
}
self_type operator--(int)
{
self_type tmp = *this;
--*this;
return tmp;
}- 迭代器类成员满足随机访问迭代器的要求:算术加法和减法，与其他迭代器的不等式相当，复合赋值，偏移量不可引用:
self_type operator+(difference_type offset) const
{
self_type tmp = *this;
return tmp += offset;
}
self_type operator-(difference_type offset) const
{
self_type tmp = *this;
return tmp -= offset;
}
difference_type operator-(self_type const & other) const
{
assert(compatible(other));
return (index - other.index);
}
bool operator<(self_type const & other) const
{
assert(compatible(other));
return index < other.index;
}
bool operator>(self_type const & other) const
{
return other < *this;
}
bool operator<=(self_type const & other) const
{
return !(other < *this);
}
bool operator>=(self_type const & other) const
{
return !(*this < other);
}
self_type & operator+=(difference_type const offset)
{
if (index + offset < 0 || index + offset > Size)
throw std::out_of_range("Iterator cannot be incremented
past the end of range.");
index += offset;
return *this;
}
self_type & operator-=(difference_type const offset)
{
return *this += -offset;
}
value_type & operator[](difference_type const offset)
{
return (*(*this + offset));
}
value_type const & operator[](difference_type const offset) const
{
return (*(*this + offset));
}- 将
typedefs 添加到dummy_array类中，用于可变和常量迭代器同义词:
public:
typedef dummy_array_iterator<Type, SIZE>
iterator;
typedef dummy_array_iterator<Type const, SIZE>
constant_iterator;- 将公共的
begin()和end()函数添加到dummy_array类中，以将迭代器返回到数组中的第一个和最后一个元素:
iterator begin()
{
return iterator(data, 0);
}
iterator end()
{
return iterator(data, SIZE);
}
constant_iterator begin() const
{
return constant_iterator(data, 0);
}
constant_iterator end() const
{
return constant_iterator(data, SIZE);
}标准库定义了五类迭代器:
- 输入迭代器:这些是最简单的类别，只保证单程序列算法的有效性。递增后，以前的副本可能会变得无效。
- 输出迭代器:这些基本上都是输入迭代器，可以用来写入指向的元素。
- 前向迭代器:这些迭代器可以读取(和写入)指向元素的数据。它们满足输入迭代器的要求，此外，必须是默认可构造的，并且必须支持多遍场景，而不会使之前的副本无效。
- 双向迭代器:这些是正向迭代器，另外支持递减，所以可以双向移动。
- 随机访问迭代器:这些支持在恒定时间内访问容器中的任何元素。它们实现了双向迭代器的所有要求，此外，还支持算术运算
+和-、复合赋值+=和-=、与其他具有<、<=、>、>=的迭代器的比较以及偏移取消引用操作符。
也实现输出迭代器要求的正向、双向和随机访问迭代器称为可变迭代器。
在上一节中，我们看到了如何实现随机访问迭代器，并逐步演练了每一类迭代器的需求(因为每一类迭代器都包含了前一类的需求并增加了新的需求)。迭代器类模板对于常量迭代器和可变迭代器都很常见，我们为它定义了两个同义词iterator和constant_iterator。
在实现内部迭代器类模板之后，我们还定义了begin()和end()成员函数，它们将迭代器返回到数组中的第一个和最后一个元素。这些方法有重载来返回可变迭代器或常量迭代器，这取决于dummy_array类实例是可变的还是常量的。
有了dummy_array类及其迭代器的这个实现，我们可以编写以下示例。有关更多示例，请查看本书附带的源代码:
dummy_array<int, 3> a;
a[0] = 10;
a[1] = 20;
a[2] = 30;
std::transform(a.begin(), a.end(), a.begin(),
[](int const e) {return e * 2; });
for (auto&& e : a) std::cout << e << std::endl;
auto lp = [](dummy_array<int, 3> const & ca)
{
for (auto const & e : ca)
std::cout << e << std::endl;
};
lp(a);
dummy_array<std::unique_ptr<Tag>, 3> ta;
ta[0] = std::make_unique<Tag>(1, "Tag 1");
ta[1] = std::make_unique<Tag>(2, "Tag 2");
ta[2] = std::make_unique<Tag>(3, "Tag 3");
for (auto it = ta.begin(); it != ta.end(); ++ it)
std::cout << it->id << " " << it->name << std::endl;除了begin()和end()之外，一个容器可能还有其他方法，例如cbegin() / cend()(对于常量迭代器)、rbegin() / rend()(对于可变的反向迭代器)和crbegin() / crend()(对于常量反向迭代器)。实现这一点是留给你的练习。
另一方面，在现代 C++ 中，这些返回第一个和最后一个迭代器的函数不必是成员函数，而是可以作为非成员函数提供。其实这是下一个食谱的题目，非成员函数的容器访问。
标准容器提供begin()和end()成员函数，用于检索容器的第一个和最后一个元素的迭代器。这些函数实际上有四套。除了begin() / end()之外，容器提供cbegin() / cend()返回常量迭代器，rbegin() / rend()返回可变的反向迭代器，crbegin() / crend()返回常量反向迭代器。在 C++ 11/C++ 14 中，所有这些都有与标准容器、类似 C 的数组和任何专用于它们的自定义类型一起工作的非成员等价物。在 C++ 17 中，甚至增加了更多的非成员函数；std::data() -返回包含容器元素的内存块的指针，std::size() -返回容器或数组的大小，std::empty() -返回给定容器是否为空。这些非成员函数用于泛型代码，但可以在代码中的任何地方使用。
在这个食谱中，我们将使用我们在前面的食谱中实现的dummy_array类及其迭代器作为例子，编写您自己的随机访问迭代器。在继续这个食谱之前，你应该先看看那个食谱。
非成员begin() / end()函数和其他变体以及非成员data()、size()和empty()在<iterator>头中的std名称空间中可用，该名称空间隐式包含在以下任何头中:<array>、<deque>、<forward_list>、<list>、<map>、<regex>、<set>、<string>、<unordered_map>、<unordered_set>和<vector>。
在本食谱中，我们将参考std::begin() / std::end()功能，但讨论的所有内容也适用于其他功能:std::cbegin() / std::cend()、std::rbegin() / std::rend()和std::crbegin() / std::crend()。
使用非成员std::begin() / std::end()功能和其他变体，以及std::data()、std::size()和std::empty()与:
- 标准容器:
std::vector<int> v1{ 1, 2, 3, 4, 5 };
auto sv1 = std::size(v1); // sv1 = 5
auto ev1 = std::empty(v1); // ev1 = false
auto dv1 = std::data(v1); // dv1 = v1.data()
for (auto i = std::begin(v1); i != std::end(v1); ++ i)
std::cout << *i << std::endl;
std::vector<int> v2;
std::copy(std::cbegin(v1), std::cend(v1),
std::back_inserter(v2));- (类 C)数组:
int a[5] = { 1, 2, 3, 4, 5 };
auto pos = std::find_if(std::crbegin(a), std::crend(a),
[](int const n) {return n % 2 == 0; });
auto sa = std::size(a); // sa = 5
auto ea = std::empty(a); // ea = false
auto da = std::data(a); // da = a- 提供相应成员功能的自定义类型，
begin()/end()、data()、empty()或size():
dummy_array<std::string, 5> sa;
dummy_array<int, 5> sb;
sa[0] = "1"s;
sa[1] = "2"s;
sa[2] = "3"s;
sa[3] = "4"s;
sa[4] = "5"s;
std::transform(
std::begin(sa), std::end(sa),
std::begin(sb),
[](std::string const & s) {return std::stoi(s); });
// sb = [1, 2, 3, 4, 5]
auto sa_size = std::size(sa); // sa_size = 5- 容器类型未知的通用代码:
template <typename F, typename C>
void process(F&& f, C const & c)
{
std::for_each(std::begin(c), std::end(c),
std::forward<F>(f));
}
auto l = [](auto const e) {std::cout << e << std::endl; };
process(l, v1); // std::vector<int>
process(l, a); // int[5]
process(l, sa); // dummy_array<std::string, 5>这些非成员函数在标准的不同版本中被引入，但都在 C++ 17 中被修改以返回constexpr auto:
- C++ 11 中的
std::begin()和std::end() - C++ 14 中的
std::cbegin()/std::cend()、std::rbegin()/std::rend()和std::crbegin()/std::crend() - C++ 17 中的
std::data()、std::size()和std::empty()
begin() / end()函数族有容器类和数组的重载，它们所做的就是:
- 返回调用容器的容器对应成员函数的结果。
- 返回指向数组的第一个或最后一个元素的指针。
std::begin() / std::end()的实际典型实现如下:
template<class C>
constexpr auto inline begin(C& c) -> decltype(c.begin())
{
return c.begin();
}
template<class C>
constexpr auto inline end(C& c) -> decltype(c.end())
{
return c.end();
}
template<class T, std::size_t N>
constexpr T* inline begin(T (&array)[N])
{
return array;
}
template<class T, std::size_t N>
constexpr T* inline begin(T (&array)[N])
{
return array+N;
}可以为没有对应的begin() / end()成员但仍然可以迭代的容器提供自定义专门化。标准库实际上为std::initializer_list和std::valarray提供了这样的专门化。
Specializations must be defined in the same namespace where the original class or function template has been defined. Therefore, if you want to specialize any of the std::begin()/std::end() pairs you must do it in the std namespace.
C++ 17 中引入的其他用于容器访问的非成员函数也有几个重载:
std::data()有几个重载；对于类C它返回c.data()，对于数组它返回array，对于std::initializer_list<T>它返回il.begin()。
template <class C>
constexpr auto data(C& c) -> decltype(c.data())
{
return c.data();
}
template <class C>
constexpr auto data(const C& c) -> decltype(c.data())
{
return c.data();
}
template <class T, std::size_t N>
constexpr T* data(T (&array)[N]) noexcept
{
return array;
}
template <class E>
constexpr const E* data(std::initializer_list<E> il) noexcept
{
return il.begin();
}std::size()有两个重载；对于类C它返回c.size()，对于数组它返回大小N。
template <class C>
constexpr auto size(const C& c) -> decltype(c.size())
{
return c.size();
}
template <class T, std::size_t N>
constexpr std::size_t size(const T (&array)[N]) noexcept
{
return N;
}std::empty()有几个重载；对于类C它返回c.empty()，对于数组它返回false，对于std::initializer_list<T>它返回il.size() == 0。
template <class C>
constexpr auto empty(const C& c) -> decltype(c.empty())
{
return c.empty();
}
template <class T, std::size_t N>
constexpr bool empty(const T (&array)[N]) noexcept
{
return false;
}
template <class E>
constexpr bool empty(std::initializer_list<E> il) noexcept
{
return il.size() == 0;
}这些非成员函数主要用于容器未知的模板代码，可以是标准容器、C 类数组或自定义类型。使用这些函数的非成员版本使我们能够编写更简单、更少的代码来处理所有这些类型的容器。
然而，这些函数的使用不仅限于泛型代码。虽然这是个人偏好的问题，但是保持一致并在代码中处处使用它们可能是一个好习惯。所有这些方法都有轻量级实现，这些实现很可能被编译器内联，这意味着使用相应的成员函数不会有任何开销。
- 编写自己的随机访问迭代器