Visual C++ 2010 中的标准 C++ 库更改

STL 继续...

必备组件

• 理解 C++0x 标准概念，即 auto 关键字、 lambda 表达式、右值引用。
• 对 STL 有相当好的理解。几个或更多的容器类和迭代器知识就足够了。
• 您必须拥有 Visual C++ 2010 编译器，或支持新的 C++ 和更新的 STL 的编译器（*我没有其他兼容编译器的参考；如果您有，请告诉我*）。

本文解释了 STL 库中的更改。与本文 介绍的 C++ 语言的更改一样，STL 的更改是在 TR1 之上的。简而言之，以下是标准模板库的进步：

• 常量迭代器
• array 类
• tuple 类
• <algorithm> 中的新函数
• 随机数生成器类（<random>）
• 集合和无序集合的改进
• 映射和无序映射的改进
• 正则表达式
• functional, utility 头文件的更改
• memory 头文件，增强的“指针”管理类

常量迭代器

首先；常量迭代器与 const 迭代器不同。常量迭代器是 const_iterator。当 const 关键字应用于 iterator（或其他任何变量）时，该变量不能进一步更改。另一方面，const_iterator（常量迭代器）不允许访问容器的*引用的*元素。在查看以下代码后，您可能想重读此段。

using namespace std;
vector<int> IntVector;

...
 
//  Normal iterator
vector<int>::iterator   iter_nc = IntVector.begin();
*iter_nc = 100;  // Valid
iter_nc = IntVector.end(); // Valid

// Constant Iterator
vector<int>::const_iterator   iter_c = IntVector.begin();
*iter_c = 100; // INVALID!
iter_c = IntVector.end(); // Valid

// The 'const' iterator
const vector<int>::iterator   iter_const = IntVector.begin();
*iter_const = 100; // Valid
iter_const = IntVector.end(); // Invalid (Why? Learn C++!)

// The 'const' Constant Iterator
const vector<int>::const_iterator   iter_const_c = IntVector.begin();
*iter_const_c = 100; // Invalid!
iter_const_c = IntVector.end(); // Invalid

那么，有什么新内容？

嗯，它会显式返回常量迭代器（即 const_iterator）的成员函数，而不管在调用这些方法时使用何种上下文。在此之前，我想告诉您，迭代器访问*或*方法（如 begin、end）将返回一个普通迭代器或常量迭代器，如下所示：

• 如果容器是常量，或者访问器是在属于 const 的类方法中调用的，则将返回 const_iterator。
• 如果左侧是 const_iterator 类型变量，则将返回普通 iterator，但会被截断为 const_iterator（即会被*转换*）。
• 如果任一方式，容器是非 const 的 - 并且未声明变量，或者左侧是 iterator 变量，则它是普通 iterator。

注意：大多数迭代器访问方法，如 begin 和 end，都已重载以返回常量或非常量迭代器。

因此，仅仅看一行代码，您就无法确定是返回普通迭代器还是常量迭代器。您也不能显式请求常量迭代器。

IntVector.begin();

新方法是：

访问器方法	含义
cbegin	返回容器中第一个元素的 const_iterator。
cend	获取指向容器最后一个元素之后一个位置的 const_iterator。
crbegin	检索反向迭代器中第一个元素的 const_iterator。本质上，是最后一个元素的常量迭代器。
crend	返回反向迭代中最后一个元素之后一个位置的 const_iterator。逻辑上，是容器第一个元素*之前*的迭代器。

所有方法在各自的容器类中都声明为 const。

引入所有这些方法的目的何在？

好问题，你应该问！当您可以以某种方式指定您需要的迭代器类型时，您可能不需要这些新方法。

嗯，答案是：*改版*的 auto 关键字！如果您阅读了 auto 关键字的新含义，您就知道可以避免输入要声明的变量的类型。编译器可以从右侧的表达式推断出类型。现在，当您只是调用

auto iter = IntVector.begin();

您无法（通过查看代码）判断是检索普通迭代器还是常量迭代器。因此，要显式请求常量迭代器（const_iterator），您可以使用

auto iter = IntVector.cbegin(); // cbegin
// The return type is:  vector<int>::const_iterator

要以*只读*模式遍历向量，您可以编写

for(auto iter = IntVector.cbegin(); iter != IntVector.cend(); ++iter) { }

常量访问器方法只是调用非常量方法（我不能保证，我在源代码中看到了）。因此，将 cend 与 end 进行比较，反之亦然（附带免责声明！）是完全有效的。

集合和集合怎么样？

对于所有集合类（set、multiset、unordered_set 和 unordered_multiset），迭代器*始终*是常量的。这意味着，检索 begin 或 end（任何变体）、调用 find 以及下标运算符（[]）的方法将返回常量迭代器。尽管看起来非常量迭代器方法（如 begin、find）的数据类型将返回 iterator 而不是 const_iterator；它们的行为将与常量迭代器相同。

考虑以下代码：

set<int> is;
is.insert(10);

*is.begin() = 120;

wcout << is.count(10) << ", " << is.count(120);

它将 10 插入 set，然后*尝试*修改 set 上的内容。由于只插入了一个元素，begin 调用将返回同一元素的迭代器。它只是修改了它。在 VC9 及更早的编译器上，它可以成功编译，并且值被修改为 120。

从 VC10 编译器开始，第三行将无法通过编译器编译，并且编译器会抱怨：

error C3892: 'std::**::begin' : you cannot assign to a variable that is const

对于 map，不允许修改键，但允许修改值。行为保持不变。这是一个代码示例：

map<int, int> imap; 

imap.insert( make_pair( 1, 1028 ));
imap.insert( make_pair( 2, 2048 ));

imap.find(1)->second = 1024; // Compiles
imap.find(2)->first = 4;     // Error

imap[2] = 2000;

*imap.begin()->first = 10;   // Error
*imap.begin()->second= 10;   // Compiles

*imap.cbegin()->second= 10;
// Error on VC10, since iterator is constant. NA for VC9

array 类

array 是一个容器类，它以*固定大小的数组*存储元素。数组的大小作为模板参数给出，与数据类型一起。大小必须是*编译时常量*（如普通的 C/C++ 数组）。除了减少或增加容器大小（即元素数量）之外，它还支持其他标准方法 - 如迭代、随机访问、交换、赋值等。

• 头文件：<array>
• 命名空间：tr1。但是，标题隐含了 'using tr1::array'。因此，只有 std 规范就足够了。

示例

array<int, 64> IntArray;

模板的第一个参数是*数据类型*，第二个是编译时*整数常量*。IntArray 的大小以后不能更改。当然，您可以使用 int 或基本数据类型以外的其他数据类型。根据执行的操作，可能需要为自定义数据类型提供复制构造函数、赋值运算符、比较运算符。对于自定义数据类型（class、struct），必须能够访问默认构造函数。

引入此类的目的是为了与其他 STL 组件无缝集成。例如，如果您使用 vector 或 list，您需要调用 begin/end 方法来访问元素。当您决定将该容器更改为固定大小的普通数组（C/C++ 数组）时，您的代码将无法编译。您需要进行更改。通过使用 array 类，您可以获得 STL 的灵活性和普通数组的性能。

借助最新的编译器支持（TR1 添加），您还可以初始化一个 array，如下所示：

array<int, 4> ByteUnits= {1024, 2048, 4096, 8192}; 

当您省略一个或多个要初始化的元素时，它们将被设置为零。当您不初始化 array 的任何元素时，所有元素都将未初始化，因此是未定义的（标准 C/C++ 规则！）。

array 类支持以下 STL 标准方法：

• at, operator [] - 返回指定位置的引用。
• back, front - 分别返回第一个和最后一个位置的引用。
• begin, cbegin, rbegin, crbegin - 返回第一个元素的迭代器。
• end, cend, rend, crend - 返回最后一个元素之后一个位置的迭代器。
• empty - 确定容器是否为空。仅当数组大小为零时才返回 true。
• size, max_size - array 对象的大小。始终相同，因为它是编译时定义的 array 的大小。

需要详细讨论的方法

• array::assign 和 array:fill

这些方法是相同的，并且它们的作用是用给定值填充 array 的*所有*元素。它们将替换数组对象的所有值。例如：

array<int,10> MyArray;
MyArray.fill(40); // or 'assign'

for_each(MyArray.cbegin(), MyArray.cend(), 
      [](int n) { std::wcout << n << "\t";} );

这将用值 40 设置所有十个元素，然后将所有值显示在控制台上。

• array::data

此方法返回数组第一个元素的地址。对于原生数组（例如，int_array[N]），此方法等同于表达式 &int_array[0] 或 int_array。此方法用于直接指针操作。同时提供 const 和非 const 方法。例如：

int* pArray = MyArray.data();

// Or

auto pArray = MyArray.data();

• array::swap(array&) 和 swap(array&, array&)

交换两个*大小和类型完全相同*的 array 对象的内容。第一个版本是非静态类方法，它接受另一个 array 对象作为参数，并与其交换内容。第二个版本是全局函数，它接受两个 array 对象（类型完全相同！）并交换它们的内容。示例：

typedef array<int,10> MyArrayType;
 
MyArrayType Array1 = {1,2,4,8,16};
MyArrayType Array2;
Array2.assign(64);

Array1.swap(Array2);
// Or - swap(Array1, Array2);

// Array1 - 64, 64...64
// Array2 - 1,2,4,....0

如果您尝试交换不同种类的数组，编译器会抱怨。例如：

array<int,5>   IntArrayOf5 = {1,2,3,4,5};
array<int,4>    IntArrayOf4 = {10,20,40};
array<float,4>  FloatArrayOf4; 

IntArrayOf5.swap(IntArrayOf4); // ERROR! 
swap(IntArrayOf4, FloatArrayOf4); // ERROR!

• 所有六个比较（关系）运算符

运算符 ==、!=、<、>、<= 和 >= 被定义为全局函数，用于比较两个*类型完全相同*的 array 对象，如果条件满足则返回 true；否则返回 false。例如：

typedef array<int,10> MyArrayType;
MyArrayType Array1 = {1,2,4,8,16};
MyArrayType Array2;
Array2.assign(64);

if (Array2 == Array1)
    wcout << "Same";
else
    wcout << "Not Same";

这将显示 'Not Same'。请参阅文档，并自行练习小于号和大于号运算符的用法。

tuple 类

任何常规的 STL 程序员都会知道一个名为 pair 的结构，它可以容纳任何数据类型的两个元素。除了 map 之外，打包两个元素而无需定义 struct 也很方便。first 和 second 成员变量实际上就是这些打包的值。为了方便回顾和讨论相关内容：

pair<string,int>  NameAndAge;
NameAndAge.first = "Intel";
NameAndAge.second = 40;

程序员经常 typedef 它们，以便可以轻松声明变量，并且 pair 可以优雅地传递给函数。

如果需要打包更多两个元素怎么办？

嗯，在这种情况下，您可能会定义一个 struct，或者使用多个 pair。前者不与 STL 无缝集成，后者则不能实现优雅易懂的代码。

为您带来福音：tuple 类。tuple 类允许将*2 到 10* 个元素组合在一起。所有类型都可以不同，并且根据所需的操作，可能需要您类的*特殊*方法。tuple 类如何用于模板重载超出了我的理解范围。我将讨论可以*实现*什么，以及*在哪里*可以使用它。

• 头文件：<tuple>
• 命名空间：tr1。在 std 下隐含了 'using tr1::tuple'。

让我们从示例开始

声明一个包含两个元素的元组

tuple<int,int> TwoElements;

构造时初始化

tuple<int,int> TwoElement (400, 800);

（如果正在初始化）*所有*元素的初始化都是强制的。以下是错误的：

tuple<int,int> TwoElement (400); // Second initializer missing

错误不会一目了然，但您可以理解需要初始化所有元素！

构造后初始化 - 不那么简单！但也不难。如果您还记得，有一个 make_pair 辅助函数用于 pair 的构造/初始化。您没猜错！辅助函数 make_tuple 就是为您准备的。如果您已经阅读过或将要阅读有关 VC++ 2010 并发运行时（Concurrency Runtime）的内容，您会发现 C++ 库中还有其他新的 make_ 函数。

总之，初始化 tuple 对象的方法如下：

TwoElement = make_tuple(400, 800);

与元组模板类一样，make_tuple 也被重载以接受 2 到 10 个参数。有趣的是，make_tuple 利用了 C++0x 语言的*右值引用*概念以及 STL 的*完美转发*特性。前者在本文 中讨论，后者将在稍后讨论。简而言之，它们允许重用同一个对象而不是调用复制构造函数和赋值运算符，从而提高整体性能。

您可以将 make_tuple 与 auto 关键字一起使用，以智能地定义一个其类型由编译器推断的 tuple：

auto Elements = make_tuple(20, 'X', 3.14159);
// Eq: tuple<int, char, double> Elements(20, 'X', 3.14159);

继续。以上是一些初始化 tuple 对象的*少数*方法。现在显而易见的问题将是*“如何访问元组的元素？”*。

对于 pair 对象，我们可以简单地使用其*模板化*成员变量：first 和 second。但是，由于 tuple 类本身没有定义任何命名的成员变量，因此我们需要使用辅助函数 **get 来访问这些未命名的变量。示例：**

tuple<string, int, char> NameAgeGender("Gandhi", 52, 'M');
int nAge = get<1>(NameAgeGender);

显式模板参数，它将是一个整数（具体来说是 size_t），指定基于零的索引。*索引*必须在 tuple 的模板参数数量范围内。在这种情况下，它必须是 0、1 或 2。在上面的示例中，get 函数用于检索元组对象的*第二个*元素。第二个元素是一个整数，存储在 nAge 变量中。

如果您为 get 函数指定了超出范围的索引，编译器将不会高兴。它*必须*是*编译时常量*并且*在*范围内。此外，返回类型也是在编译时推断的；您不能欺骗编译器，如下所示：

int nAge = get<0>(NameAgeGender);
// ERROR - cannot convert from 'string' to 'int'

这也有助于查找潜在的代码缺陷。

char cGender = get<1>(NameAgeGender); // Leve 4 C4244 warning - 'int' to 'char'
// Should be get<2>

更重要的是，它允许使用 auto 关键字！

auto sName = get<0>(NameAgeGender); // Type deduction - 'string'

由于对于非 const tuple 对象，返回类型是所需元组元素的引用，因此您也可以更改元素的值：

// Modify Age
get<1>(NameAgeGender) = 79;

当然，您可以将其放入引用变量中，稍后修改它。auto 关键字也可用。

auto & rnAge = get<1>(NameAgeGender) ;

rnAge = 79

为了充分赞扬 get 函数，我必须提到它也可以与 array 类一起使用。

array<char, 5> Vowels = {'A','E','I','o','U'};
 
char c = get<1>(Vowels); // 'E'
get<3>(Vowels) = 'O';  // Modify
get<10><Vowels);  // ERROR - Out of range!

tie 函数

此函数在逻辑上是 make_tuple 函数的反向操作。使用 tie 函数，您可以从元组对象初始化一组变量。先看一个例子：

tuple<string, int, char> NameAgeGender("Gandhi", 52, 'M');

string sName;
int nAge;
char cSex;
  
tie(sName, nAge, cSex) = NameAgeGender;

这将分别用值“Gandhi”、52 和 'M' 设置这三个变量。我的好奇心表明 tie 也可以用于代替 make_tuple。但反之则不然。

tuple<string, int, char> NameAgeGender;
NameAgeGender = tie("Gates", 46, 'M'); // make_tuple
 
string sName;  int nAge;   char cSex;
make_tuple(sName, nAge, cSex) = NameAgeGender; // NO error. See below.

tie 函数接受并返回元组对象的引用；make_tuple 在逻辑上*创建*一个对象，并接受/返回非引用。最后一行会编译，但不会产生预期的结果，因为所有三个参数都是按值传递的，并且正在尝试修改临时元组。我建议您按照其设计用途来使用 tie 和 make_tuple 辅助函数。

六个关系运算符

与 array 一样，所有六个关系运算符也为 tuple 类定义。所有重载运算符都要求两个操作数（tuple 对象）*必须类型完全相同*！遵循 C/C++ 语义，函数返回 true 或 false 作为结果。

algorithm> 中的新函数

作为 TR1 添加的一部分，以下函数是 <algorithm> 头文件中的新函数：

1. all_of
2. any_of
3. none_of
4. find_if_not
5. copy_if
6. partition_copy
7. is_partitioned
8. partition_point
9. minmax_element
10. is_sorted
11. is_sorted_until
12. is_heap
13. is_heap_until
14. move

读者应具备对算法函数如何工作的基本理解。例如 count、count_if 或 find_if 函数是如何工作的。简而言之，它们作用于给定的迭代器，并返回所需的结果。例如 count_if 计算给定容器（由迭代器指定）中与指定条件匹配的元素数量。大多数函数不改变给定的范围。少数函数会修改其中一个给定的范围（如 copy、remove_copy），还有一些函数会修改给定的范围（for_each、fill、generate）。

• all_of 函数

all_of 函数测试给定范围内的所有元素，并且仅当所有元素都匹配给定谓词时才返回 true。如果任何元素未能匹配谓词，则函数将中止进一步搜索并返回 false。示例：

vector<int> IntVector(10);

fill(IntVector.begin(), IntVector.end(), 64);
// IntVector[1]=3;

bool bAllAre4 = all_of(IntVector.cbegin(), IntVector.cend(),
    [](int nValue) { return nValue % 2 == 0; });

上面的代码将向量的所有 10 个元素填充为值 64。然后调用 all_of 函数来测试所有元素是否都是偶数。谓词通过 C++0x lambda 提供。它也可以是函数指针或函数对象（仿函数）。在这里，它将返回 true，因为所有元素都是偶数。如果您取消注释注释掉的（第三个）行，返回值将是 false。

对于此函数以及所有后续函数，重要的是要注意给定的函数*不会*复制给定的仿函数/lambda。我的意思是：在每次迭代中都会调用给定的谓词，其行为取决于谓词在该调用中返回的内容。让我通过一个例子来解释：

int nCheck = 2;
bool bAllAre4 = all_of(IntVector.cbegin(), IntVector.cend(),
    [&nCheck](int nValue) { return nValue % nCheck++ == 0; });

使用*有状态 lambda*，谓词函数的含义已更改。因此，每次调用，函数都会表现不同。第一次调用时，它会测试模 2，然后是模 3，依此类推。因此，您会看到给定的谓词函数不会被*算法*函数复制，而是在每次迭代中调用。尽管此行为可能符合您的要求 - 但请注意！

• any_of 函数

您可以猜测此函数的作用；它测试*任何*元素是否匹配给定谓词，如果匹配，则返回 true。如果没有元素匹配给定谓词，它将返回 false。值得注意的是，该函数一旦找到匹配给定谓词的项就会退出。此函数与 find 函数*并非完全相同*。find/find_if 函数返回一个iterator，但 any_of 返回 bool。很多时候，我们只需要定位一个项目是否存在于容器中。使用 'iter != container.end()' 很麻烦。所以，为您带来福音：

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

bool bDoes3Exists = any_of(IntArray.begin(), IntArray.end(),
   [](int nValue) { return nValue == 3; });

它将返回 true，因为数字 3 存在于容器中。要查找是否存在任何偶数/奇数，您可以相应地进行更改。这是另一个示例，用于查找给定字符串列表中的国家名称：

list<string> Countries;

Countries.push_back("Japan"); 
Countries.push_back("India");
Countries.push_back("Singapore");
Countries.push_back("USA");

if ( any_of(Countries.begin(), Countries.end(),
     [](const string& sName) { return sName.compare("Singapore")==0; } )
   )
   {
       wcout << "Country exists";
   }

如果您想知道哪个元素匹配了条件，您需要使用 find 或 find_if 函数。不幸的是，any_of 函数不支持使用给定值进行搜索；它需要一个函数/lambda！

• none_of 函数

none_of 函数在没有元素匹配给定谓词时返回 true。从语义上讲，它与 !any_of 相同。它仅在*所有*元素*未能*匹配条件时返回 true（即，谓词始终返回 false）。如果任何匹配成功，它将返回 false。示例：

array<int, 5> IntArray = {1,8,64,128,1024};
//IntArray[2] = 8192;

auto bLessThan2K = none_of(IntArray.cbegin(), IntArray.cend(),
    [](int nValue) { return nValue>=2048;});

变量 bLessThan2K 将为 true，因为没有项大于 2048。当您取消注释第二行时，none_of 的返回值将为 false，因为它找到了一个*未能*匹配谓词的匹配项。您可以通过将 'none_of' 替换为 '!any_of' 来实现相同的结果。

• find_if_not 函数

与 find/find_if 函数类似，它返回适当类型的迭代器。它尝试定位*不*匹配给定谓词的第一个项。例如，您可能想找到一个未婚的人。由于婚姻状况可能是多样的，最好是查找一个人是否*未婚*（搜索“未婚”可能效果不佳！）。让我们看一个例子：

using namespace std;
 
// Tuple of Name, Age, Sex, Marital Status
typedef tuple<string, int, char, char> Person;

vector<Person> People;

People.push_back(make_tuple("Adam", 21, 'M', 'M'));
People.push_back(make_tuple("Eve", 19, 'F', 'M'));
People.push_back(make_tuple("Natasha", 23, 'F', 'C')); // Committed 
People.push_back(make_tuple("Enrique", 32, 'M', 'U'));
People.push_back(make_tuple("James", 38, 'M', 'D')); 

auto iter = find_if_not(People.cbegin(), People.cend(), [](const Person& person)
{
    // Lambdas dont capture namespace
    return std::get<3>(person) == 'M';
});

if(iter == People.end())
{
    wcout << "No one found!";
}
else
{
    wcout << "Found a person!\n" <<
        "Name: " << get<0>(*iter).c_str() // I hate std::string
        << "\nAge: " << get<1>(*iter);
}

// Output:
//   Name: Natasha,  Age: 23

上面的代码要求您重新访问 tuple！iter 的类型是 vector<Person>::const_iterator，它通过 auto 关键字进行了缩写。

• copy_if 函数

此函数需要一些注意和解释。首先，根函数：copy，它将一个范围（输入）复制到另一个范围（输出）。由于这是一个*复制函数*，而不是*插入函数*，因此目标范围必须有足够的空间。示例：

vector<int> IntVector(10);
array<int, 10> IntArray = {1,2,3,4,5,6,7,8,9,10};

copy(IntArray.cbegin(), IntArray.cend(), IntVector.begin());

如果目标不够大，Debug 版本将断言。要实现*插入*，您可以使用 back_inserter 类：

// Starts from IntVector.end
copy(IntArray.cbegin(), IntArray.cend(), back_inserter(IntVector));

继续，就相关讨论而言。remove_copy 函数可用于仅将与给定值匹配的元素复制到*另一个*容器/范围。此外，remove_copy_if 可用于按给定谓词进行复制。“remove”一词在函数名中并不意味着它会*移除*原始范围中的某些内容，而是仅复制匹配值/谓词的值，*移除*（排除）其他内容。目标范围的要求与 copy 函数相同。以下是两者的示例：

vector<int> IntVector; // Size = 0
array<int, 10> IntArray = {1, 2, 3, 4, -1, 6, 7, -1, 8, -1}; 

// Copy all excluding -1
remove_copy(IntArray.cbegin(), IntArray.cend(), back_inserter(IntVector), -1);

wcout << "Size: " << IntVector.size(); // 7
 
...

IntVector.clear(); // size  = 0
 
// Copies ONLY elements that are NOT even
remove_copy_if(IntArray.cbegin(), IntArray.cend(), back_inserter(IntVector),
    [](int nValue) { return nValue % 2 == 0;});

wcout << "Size: " << IntVector.size(); // 6

现在，如果我们想*只复制偶数*，我们只需将 lambda 中的表达式更改为：

return nValue % 2 != 0;

您可以看到，要放入您*需要*的内容，您需要以“*不需要*”的形式来表达。如果条件涉及多个条件（AND、OR），则编写和理解起来会更复杂。是的，解决方案是取整个条件的否定（!）。但该方法再次要求您以“*不需要*”的形式编写，并且难以理解。

copy_if 函数提供了一种简洁直接的方法。您可以将其视为带有条件测试的 copy 函数。以下是“*我*只需要偶数*”要求的代码：

copy_if(IntArray.cbegin(), IntArray.cend(), back_inserter(IntVector),
      [](int nValue) { return nValue % 2 == 0;} ); // Positive condition

让我们再举一个例子，涉及 Person 元组。在一个 Person 向量中，我们需要只复制已婚男性。我们可以写：

typedef tuple<string, int, char, char> Person;
vector<Person> OriginalPeople, RequiredPeople;

OriginalPeople.push_back(make_tuple("Adam", 21, 'M', 'M'));
OriginalPeople.push_back(make_tuple("Eve", 19, 'F', 'M'));
OriginalPeople.push_back(make_tuple("Natasha", 23, 'F', 'C')); // Committed 
OriginalPeople.push_back(make_tuple("Enrique", 32, 'M', 'M')); // Now married!
OriginalPeople.push_back(make_tuple("James", 38, 'M', 'C')); 

copy_if(OriginalPeople.cbegin(), OriginalPeople.cend(),
        back_inserter(RequiredPeople), // Copy here 
      [](const Person& person_obj) -> bool // No simple return, -> required!
      {
          if ( std::get<2>(person_obj) == 'M' && 
               std::get<3>(person_obj) == 'M' )
          {
               return true;
          }
          else
          {
               return false;
          } 

       } // Lambda end
);
 
// RequiredPeople would have 2 elements

**注意**：截至本文撰写时，MSDN 上关于 copy_if 的文档是不正确的。它说需要三个参数，但实际上它需要四个参数。

• partition_copy 函数

partition_copy 函数根据条件将输入范围*分区*到两个不同的输出范围。如果条件为 true，它将复制到第一个输出范围。如果条件为 false，它将复制到第二个输出范围。这是一个生成一些随机数，然后将偶数和奇数复制到不同向量的示例：

vector<int> IntVectorEven, IntVectorOdd;
array<int, 50> IntArray;
 
// Generate random numbers
generate(IntArray.begin(), IntArray.end(), rand);

partition_copy(IntArray.cbegin(), IntArray.cend(), 
          back_inserter(IntVectorEven), back_inserter(IntVectorOdd),
          [](int nValue) { return nValue%2==0;});
 
// IntVectorEven.size() + IntVectorSize would be: IntArray.size() !

在 Person 向量中，让我们按性别划分人员：

typedef tuple<string, int, char, char> Person;

vector<Person> OriginalPeople, RequiredPeople;
list<Person> Males, Females;

/**  All 5 people inserted same as above **/

partition_copy(OriginalPeople.cbegin(), OriginalPeople.cend(),
      back_inserter(Males), back_inserter(Females),
      [](const Person& objPerson) 
  { 
      return std::get<2>(objPerson) == 'M';
  });

// Males.size = 3, Females.size = 2

• is_partitioned 函数

此函数测试给定范围是否基于给定的条件进行了分区。例如，一个包含 10 个元素的数组可能包含一组负数和零/正数。此外，假设所有负数都放在正数之前，所有正数都跟在负数之后。在这种情况下，它被称为*分区*。如果范围已正确分区，函数 is_partitioned 将返回 true；否则；它返回 false。

首先，调用 is_partitioned：

bool bPartitioned = is_partitioned(IntArray.cbegin(), IntArray.cend(), 
      [](int nValue){return nValue < 0;} );

在这里，一组不同的值被放入 IntArray，其结果被*分区*：

array<int, 10> IntArray = 
     {-1, -3, -4, -5, 0, 1, 2, 3, 4, 5}; // TRUE
     {-1, 1, 3, 4, 0, 1, 2, 3, 4, 5}; // TRUE 
     {1, 3, 4, 0, -12, -2,-5, 3, 4, 5}; // FALSE
     {0, 1, 3, 4, 0, 1, 2, 3, 4, 5}; // TRUE - Only one partition exists
     {-1, -3, -4, -5, -1, -21, -22, -3,-4, -5}; // TRUE
     {5, 4, 3, 1, 0, -1, -2, -4, -192, -129}; // FALSE, Partitioned, but not as expected

不。分区范围不意味着排序范围。使用以下调用，我们可以测试 IntArray 是否根据偶数/奇数顺序进行了分区：

array<int, 10> IntArray = {2, 4, 8, 64, 256, 1024, 9, 17, 29, 47};

bool bPartitioned = is_partitioned(IntArray.cbegin(), IntArray.cend(), 
     [](int nValue){return nValue%2 == 0;} );
// Returns true, since it is logically partitioned!

• partition_point 函数

文档的说法不同，但通过实际工作和查看源代码，我发现这等同于调用 find_if_not。因此，在获得关于此函数的正确信息之前，我将不在此详细介绍。

• minmax_element 函数

minmax_element 结合了 min_element 和 max_element 函数所执行的工作。回顾一下：min_element 在给定范围内查找最小的元素，max_element 查找最大的值。由于它们返回的是迭代器而不是值，因此将返回第一个找到的相关*迭代器*。

minmax_element 返回一个类型为 pair<iterator,iterator> 的 pair，其中 first 迭代器指向最小元素，second 指向最大元素。除了避免两次函数调用外，它的性能也优于两次组合调用。它的查找速度更快：它在 *N * 1.5* 次尝试中找到两个值，而两次函数调用需要 *N * 2* 次尝试（N 是给定范围内的元素数量）。

例如

array<int, 10> IntArray = {2, 4, 8, 64, 256, 1024, 9, 17, 29, 47};

// It returns pair<X,Y>
auto minmax_pair = minmax_element(IntArray.cbegin(), IntArray.cend() );
 
// Since the pair holds iterators, they must be indirected to get value
wcout << "\nSmallest:" << (*minmax_pair.first) << 
       "\tLargest: "<< (*minmax_pair.second);

所有三个函数都已重载，以接受 2 个或 3 个参数。3 参数函数接受一个谓词进行测试。谓词应在逻辑上实现小于比较。

• is_sorted 函数

顾名思义，is_sorted 函数确定给定范围是否按*升序*（通过*小于*运算符测试）或按谓词函数指定的顺序排序。如果范围已排序，则返回 true，否则返回 false。以下示例非常清楚，无需进一步解释：

array<int, 10> IntArray = {2, 4, 8, 64, 256, 1024, 9, 17, 29, 47};

bool bIsSorted = is_sorted(IntArray.cbegin(), IntArray.cend());
// Would be false

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

bIsSorted = is_sorted(IntArray.cbegin(), IntArray.cend());
// Now, it would return true

如果我们想测试一个 Person 元组的 vector 是否已排序，我们必须将二元谓词作为比较器传递，因为 tuple 没有定义 operator < 来协助它。在下面的示例中，我们的“*向量是否已排序*”基于人的年龄：

typedef tuple<string, int, char, char> Person;
vector<Person> People;

OriginalPeople.push_back(make_tuple("Eve", 19, 'F', 'M'));
OriginalPeople.push_back(make_tuple("Adam", 21, 'M', 'M'));
OriginalPeople.push_back(make_tuple("Natasha", 23, 'F', 'C'));
OriginalPeople.push_back(make_tuple("Enrique", 32, 'M', 'M'));
OriginalPeople.push_back(make_tuple("James", 38, 'M', 'C')); 

bIsSorted = is_sorted(OriginalPeople.cbegin(), OriginalPeople.cend(),
    [](const Person& left_person, const Person& right_person)
    {
        // The second element is age
        return std::get<1>(left_person) < std::get<1>(right_person);
    } );
// The return value would be true, since elements are inserted in age ascending order

如果您有其他类型的对象（如 struct、class、指针），则必须提供合适的比较器作为谓词。由于本文是关于 STL 中的新概念，我不会尝试给出标准示例。

• is_sorted_until 函数

is_sorted 函数的“大哥”。is_sorted_until 函数由 is_sorted 调用。实际任务由 is_sorted_until 完成。

您可能会问有什么区别！嗯，只是 is_sorted 返回 bool，而 is_sorted_until 返回*排序*测试失败*之后*的迭代器。对于范围 **[First, Last]**，如果排序测试成功，它将返回 **Last**（即给定范围的 end）；否则，它将返回一个排序测试失败的迭代器。例如：

array<int, 10> IntArray = {2, 4, 8, 64, 256, 1024, 9, 17, 29, 47};
array<int,10>::const_iterator iter; // You see how convenient 'auto' is!

iter = is_sorted_until(IntArray.cbegin(), IntArray.cend());

if(iter != IntArray.cend())
{
// Would refer to 1024, which is the point range was sorted.
    wcout << "Sorting fails at: "<< *iter << 
             "which is " << (iter - IntArray.cbegin()) << 
             " items away from begin.";
}
else
{
    wcout << "Array is sorted!";
}

谓词版本（接受三个参数）与 is_sorted 相同，并且其*比较器*要求也相同。记住，is_sorted 调用 is_sorted_until。

// Simplified
bool is_sorted(iterator first, iterator last)
{
   return is_sorted_until(first, last) == last;
}

关于 STL 堆

坦率地说，我不知道 STL*堆*数据结构是什么。搜索没有给我足够的结果，所以我认为 STL 程序员对此不太了解。在我学习并实际尝试了堆之后，我发现堆对于大多数程序设计来说并不有用。尽管如此，为了完整性（is_heap、is_heap_until 函数的阐述），我需要解释什么是堆，它是如何创建的，以及它可能有什么用途。

在 STL 术语中，堆本身并不是一种数据结构 - 没有专门为此分配的 STL 类。STL 堆工作在*随机访问*容器（如 deque、vector、array、原生数组）之上。有一组函数用于将随机访问容器变成堆。

**注意**：堆不同于堆内存。在计算机科学中，堆是一种数据结构！

在 堆数据结构中，最大的元素始终位于顶部。其余元素排列成一个（特殊的）二叉树（称为*二叉堆*）。与需要指针和左右节点的二叉树数据结构不同，堆通常通过数组实现。此外，在堆中，没有排序（当以根-左-右方式迭代时）；只是元素排列使得根元素大于其子节点（所有底层节点都遵循相同的规则）。在我进一步讨论之前，让我们看一个二叉堆示例：

{ 500, 40, 300 };

这是一个有效的二叉堆

  500
40  300

让我们在二叉堆中添加更多元素：

{ 4096, 512, 1024, 16, 32, 128, 4};

可以表示为：

      4096
   512   1024
 16  32  128  4

最后是一个包含 10 个元素的树，它将形成一个*非严格*二叉树：

        10
     9      7
   8   5  6   3 
 1  4 2

因此，您可以看到二叉堆具有以下属性：

• 最大的元素始终位于顶部（这是一个*最大堆*；*最小堆*的顶部最小）。对于树的每一层，规则都相同。
• 元素未排序，尽管它们看起来已排序。它也不是二叉树。
• 对于 2^(N-1) 个元素，二叉树被完全填充。否则，最低层上的项将放置在树的左侧。
• 堆可用于实现*优先队列*（实际上，priority_queue 基于堆和下面的 STL 函数）。我不知道其他有用的实现。

堆的创建和其他堆操作

对于任何随机访问容器，可以使用 STL 函数 make_heap 将其转换为堆。例如：

// Or ordinary array, vector, deque...
array<int,10> IntArray = {1,2,3,4,5,6,7,8,9,10};

make_heap(IntArray.begin(), IntArray.end()); // {10,9,7,8,5,6,3,1,4,2}

这将使 IntArray 成为一个堆（完全如最后一个二叉堆所示）。此外，pop_heap 可用于从堆中检索最大的元素（并*逻辑上*将其*删除*）。pop_heap 函数移除最大的元素，并将其放入堆的末尾，并*重新形成*堆（排除已移除的项）。示例：

// Continuing with heap created above...
pop_heap(IntArray.begin(), IntArray.end());

wcout << "Largest: " << IntArray[9]; // Displays 10
 
// Heap now: {9,8,7,4,5,6,3,1,2,10}

重要的是要知道，*堆*本身现在只有九个元素。因此，程序员有责任从堆中移除该项。由于 IntArray 是一个 array，无法移除任何项。为此，我们可以使用一个计数器，并使用 IntArray.end() - nCounter 进行堆操作。对于 vector 和 deque，可以使用 pop_back 方法。

要将项插入堆，可以使用 push_heap 函数。在此之前，必须将实际元素推入相关容器。例如：

vector<int> IntVector;

IntVector.push_back(20);
IntVector.push_back(40);
IntVector.push_back(80);
IntVector.push_back(120);
IntVector.push_back(180);

make_heap(IntVector.begin(), IntVector.end());
// {180,120,80,20,40}

// Let's display largest item from heap
wcout << IntVector.front() << endl;

// Remove it from heap, AND from container
pop_heap(IntVector.begin(), IntVector.end());
IntVector.pop_back();

// Put new item into container
IntVector.push_back(128);

// And let the 'heap' know it, so that it can re-form the heap
push_heap(IntVector.begin(), IntVector.end()); // {128,120,80,20,40}

如何操作堆取决于您 - 是先弹出堆然后获取最后一个元素；*还是*先获取第一个元素然后从堆中弹出（之后，在这两种情况下都从容器中实际移除该元素）。

最后一个函数，仅为完整起见，是 sort_heap 函数，它将对堆进行排序。堆排序后，它实际上是一个已排序的容器，不再是堆。

简而言之，关于 STL 堆：

• 基于随机访问容器。
• 调用 make_heap 以将范围初始转换为堆。
• 访问*前端元素*以获取容器中的最大项。
• 调用 pop_heap 以*逻辑上*从容器中移除它，然后*实际*从堆中移除它。调用适当的函数将其物理上从容器中移除。
• 使用 push_heap，然后插入实际项，以重新形成堆。
• 使用 sort_heap 函数将堆转换为已排序的范围。

回到正轨！让我们讨论关于堆的新 STL 函数。

• is_heap 函数

此函数确定给定范围是否为有效堆。如果范围是有效堆，则返回值为 true；否则为 false。例如：

array<int,10> IntArray = {1,2,3,4,5,6,7,8,9,10};
make_heap(IntArray.begin(), IntArray.end());

bool bIsHeap = is_heap(IntArray.cbegin(), IntArray.cend()); // true
 
// Logically remove from heap..
bIsHeap == is_heap(IntArray.cbegin(), IntArray.cend()); 
// Would be false since largest item moved to end...

 
// Following would return true 
bIsHeap == is_heap(IntArray.cbegin(), IntArray.cend() - 1); // (exclude last)

与 is_sorted 函数一样，此函数的另一个重载也接受一个二元谓词作为*比较器*。堆应该使用类似的谓词创建（即，通过 make_heap、push_heap 和 pop_heap 的*三个*参数版本）。

• is_heap_until 函数

与 is_sorted 和 is_sorted_until 的关系类似，此函数返回一个迭代器而不是 bool。返回的值可用于测试堆测试失败的位置。is_heap 函数调用此函数，就像 is_sorted 调用 is_sorted_until 一样。

此函数也接受一个二元谓词，并且要求堆使用类似的二元谓词创建。

• move 函数

啊！C++0x 移动语义、STL 的完美转发以及 std::move 函数的变体... 由于 move 在多个头文件中具有不同的变体，并且它还需要了解 STL 如何利用右值引用来提高性能 - 讨论所有这些内容需要一个单独的部分。因此，我将在本文稍后介绍所有这些主题。

简而言之，move 函数在适用和可能的情况下调用移动构造函数和移动赋值运算符，以将一个资源*移动*到另一个资源，而无需创建新的副本并删除旧的副本。

random> 头文件

大多数 C++ 程序员不喜欢 rand 函数，并且需要花费一番功夫才能获得一个好的随机数生成器，并且具有较大的变异性。嗯，STL 的开发者听到了我们的声音，并为我们准备了一个全新的头文件：<random>。这个头文件为我们提供了数十个类来获取随机数 - 具有不同的数据类型：bool、整数和 float/double！

在我尝试解释这个头文件的*概念*（这可能会让您头脑发胀）之前，让我先举一个简单的例子：

using namespace std;

default_random_engine def_rand;

int nRandom;

for (int nIter = 0; nIter < 20; nIter++)
{
   nRandom = def_rand();
   wcout << nRandom << "\t"; 
}

如您所见，它生成 20 个随机数并将它们显示在屏幕上。default_random_engine 类型，实际上是另一个类的*类型定义*，为您生成随机数。operator() 返回下一个随机数。上面的代码会产生类似如下的结果：

-795755684      581869302       -404620562      -708632711      545404204
-133711905      -372047867      949333985       -1579004998     1323567403
418932835       -1944672731     1196140740      809094426       -1946129057
-30574576       -182506777      -15198492       -150802599      -138749190

它比 rand 函数好。

• 返回的值在 signed long（4 字节有符号整数）的范围内。
• 同时返回正值和负值。

现在，让我们不再继续诋毁我们老朋友 rand。<random> 头文件还有更多内容，无法与标准随机生成函数进行比较。

如果您多次运行上面的代码，它将产生相同的结果集。要获取不同的值，您需要使用 seed 方法。尽管 seed 方法有三种变体，但我举了一个接受整数的例子：

// Putting it before the loop.
def_rand.seed(45001); // Takes 'unsigned long', must not be (less than) zero

现在这将生成一组不同的数字。是的，使用相同的种子值，程序仍然会生成相同的随机数集。不用担心，头文件现在还有很多内容。

现在，概念和术语！

以下是 <random> 头文件中类的逻辑划分：

• **随机数生成器** 是一个生成随机数的对象。简而言之，一个实例变量（上面示例中的 def_rand）。这具有特定含义，因为它可能与下面提到的类类型组合。
• 一个*引擎*是*生成器*类，它实际生成随机数。引擎可以是*简单引擎*，它自己生成随机数；或者它可以是*复合引擎*，它利用一个或多个其他简单引擎来生成最终的随机数。此外，引擎可以与*分布*结合。（default_random_engine 是引擎的一种。）
• 一个*分布*是一个类，它生成均匀*分布*的随机值。分发器利用引擎生成随机值。

除了 random_device_engine，所有引擎都生成伪随机值 - 这意味着如果未设置种子，这些引擎将产生相同的结果；或者如果设置了种子，则使用相同的种子值。因此，可能需要利用 random_device_class 来为适当的引擎设置随机值的种子。示例：

random_device rnd_device; 

def_rand.seed(rnd_device());

这会导致 def_rand（即 default_random_engine）在每次运行时产生一组不同的随机值。稍后将详细介绍此类。

为了循序渐进，请允许我推迟类分类，让我介绍更多示例。现在，您不需要使用任意随机值，而是需要值在给定范围内。例如，您可以对 100 取模（如果您需要，再加上 1）来获得范围内的值：

for (int nIter = 0; nIter < 20; nIter++)
{
   nRandom = def_rand() % 100; // +1
   wcout << nRandom << "\t"; 
}

这将仅生成 0 到 99 范围内的值。这时就可以使用分布类了！对于这种情况，您可以使用 uniform_int_distribution 类。以下代码生成 1 到 100 范围内的真正随机值：

default_random_engine   def_rand; 
uniform_int_distribution<int>  uni_dist(1,100); // Range

int nRandom;

random_device  rnd_device; 

def_rand.seed(rnd_device()); // Good random seed

for (int nIter = 0; nIter < 20; nIter++)
{
   nRandom = uni_dist(def_rand); // Distribution utilizes the Engine
   wcout << nRandom << "\t"
}

uniform_int_distribution 是众多分布之一。在构造时，我将其设置为仅发出 1 到 100 之间的值。random_device 类用于设置 def_rand 对象，这将使其在每次运行时都能生成真正随机的值。此外，通过表达式 uni_dist(def_rand)，引擎与分发器结合。分发器调用给定引擎的 operator()。

多次运行此代码将产生类似如下的结果：

/* Run 1 */
36      91      61      97      17      11      91      45      88      56
5       96      100     1       25      26      27      69      4       90

/* Run 2 */
14      51      98      90      59      77      9       16      17      4
43      60      99      92      7       13      12      66      20      87

为了有深刻的理解，请随意玩弄给定的代码！

让我们再举一个例子，您将请求生成 true 或 false，并且您要求 70% 的*true* 概率。为此，我们可以使用名为 bernoulli_distribution 的类：

bernoulli_distribution ber_dist(0.7);
... 

// In loop:
nRandom = ber_dist(def_rand);

这将产生类似如下的结果：

1       1       1       1       1       0       1       1       0       1
1       1       0       0       1       0       1       1       1       1

不要计数！概率就是概率，而不是必然性。如果您需要 70% 的*false* 概率，只需将 0.7 更改为 0.3！

好的。到目前为止，您有两个*简单*引擎：default_random_engine 类型定义和 random_device 类；以及两个分布类：uniform_int_distribution 和 bernoulli_distribution（忽略含义！）。您可以看到*引擎*实际生成伪随机值，*分布*对其进行适当过滤。

引擎类的属性

每个引擎都具有以下属性：

属性	含义
参数类型	类模板的参数类型。根据引擎模板类接受的输入和/或结果类型，可以是一个、两个或零个。 如果没有，则引擎类不是模板类，并且 result_type 由类显式定义（如 random_device，它有 int 作为 result_type）。
result_type	类 operator() 返回的数据类型。这是模板参数的第一个参数类型（如果存在）。 此类型由类的 min 和 max 方法返回。 seed 的一个版本接受此类型作为其参数。
min 和 max 方法	返回此引擎类 operator() 可以返回的最小值和最大值。 这些值可以是预定义的，也可以取决于给定的模板参数。
seed 方法	为下一个随机值设置引擎的种子。 seed 方法可以接受整数/实数值作为种子（实际类型取决于引擎类）。 它还接受 seed_seq 类（稍后描述）。 另一个重载也接受仿函数/lambda，它会被调用多次以生成种子。 对 random_device 类*不可用*。
operator()	返回下一个随机值的运算符。 返回类型为 result_type。 返回值在 min 和 max 之间。
discard 方法	调用给定次数的 operator()，有效地丢弃生成的随机值集。

我不想写太多理论和参考材料，但我需要这样做；因为目前没有好的、易于理解的文本。所以请耐心！表格和文本现在可能看起来很陌生，但您需要再次参考它们，它们会证明是有益的。

总之，让我放一些代码片段来让您满意：

random_device::result_type nMin, nMax, nRandom;
random_device rnd_device;

// Both methods are static, for all engine classes
// Thus object is not required.
nMin = random_device::min();
nMax = rnd_device.max();

 
// Operator ()
nRandom = rnd_device();

... 
  
default_random_engine def_eng;
def_eng.seed(1000);

// Discards next 10 random generations, 
// same as calling op() 10 times
def_eng.discard(10); 

...
 
// One of compound class. Takes template parameters.
// The data-type (__int64) defines the result_type
// The numeric argument (32) defines the min, max values
typedef independent_bits_engine<random_device, 32, __int64> T32Bits;
T32Bits ib32; 

T32Bits::result_type rt; // rt is '__int64'
 
// Again, min and max are static methods, but template 
// redefines them each time a class-template is instantiated. 
rt= ib32.max(); // 1<<32-1  (4294967295)
rt = T32Bits::min(); // 0

rt = ib32(); // random value 

上面显示的示例仅用于说明引擎属性，并非所有显示的类都已讨论。上面显示的示例还举例说明了*复合*引擎类，该类尚未详细阐述。

对于所有引擎类*和*所有分布类，结果类型和模板参数类型可以是以下之一（这些不是 typedef 或 enum，只是文档/头文件中的模板参数占位符）：

• IntType 表示类接受有符号或无符号类型。
• UIntType 表示类接受无符号整数类型。对于这两种类型，整数意味着从 bool 到 __int64 的基本整数类型。
• RealType 表示 float 或 double 类型。

分布类的属性

分布类（约 20 个）的数量多于引擎类（约 8 个）。因此，不幸的是，读者有更多的*属性*适用于分布类。与引擎类相同的属性在下表的*第一行*中进行了归类：

属性	含义
参数类型 结果类型 min 和 max， operator()	所有分布类都具有这些属性/方法。 seed 方法不适用于分布。 operator() 接受引擎，该引擎将生成伪随机值。
input_type	引擎的 operator() 应该返回的类型。 编译器将转换类型，否则将发出警告/错误。 此类型由分布类预定义，或由模板参数指定。
operator()	接受一个引擎对象作为参数。 在该引擎上调用 operator() 根据分布*过滤*返回值，并将值返回给调用者。 另一个重载接受 param_type 作为参数。
reset()	重置任何缓存值，以便下次调用 operator() 不依赖于先前获取的值。
param_type	内部类型，超出讨论范围。
前置条件	在构造对象时，必须满足分布指定的先决条件。 如果未满足先决条件，Debug 版本将简单地调用 assert 函数。 一个例子是 0.0 到 0.5 作为*分布*参数的前置条件（还记得 0.7 吗？）。

好的，让我尝试通过提供更多示例及其输出来阐明事物。我不会探索 <random> 头文件中的所有类，但会探索一些重要/有趣的类。在本节的末尾，将有一个（*或曾经*）包含所有类及其主要特征的表格。相信我，收集相关信息、制作好的示例并将其写下来，比阅读和理解它的*难度*级别要困难得多！

让我们使用实现最古老、最知名的随机数生成器——*线性同余生成器*（Linear Congruential Generator）的类。该算法被许多运行时使用，并且被 rand 函数使用。[无需理解以下内容]。LCG 算法按以下公式定义下一个数字：

X[i+1] = (A * X[i] + C) % M;  //  x(i+1) = (a * x(i) + C) mod m

其中 **A**、**C** 和 **M** 是整数常量。常量 **A** 和 **C** 必须小于 **M**。此类的引擎类（*简单引擎*）是 linear_congruential_engine。这是一个类模板，其第一个参数接受 UIntType，其余参数接受反映 **A**、**C** 和 **M** 的无符号整数常量。类模板的原型是：

template <class UIntType, 
          UIntType A, UIntType C, UIntType M> 
          linear_congruential_engine ;

下面是如何实例化和使用它（不要问常量的意义！）

linear_congruential_engine<int, 12, 16, 8000> lce;
int nRandom;

nRandom = lce(); // Returns 28
nRandom = lce(); // Returns 352 

如*引擎类的属性*中所述，这是接受数据类型并且该数据类型成为 result_type 的引擎类之一。因此，此实例（lce）的 result_type 是 int。这是*简单*引擎之一。

我们使用了名为 default_random_engine 的默认引擎，它实际上是与 mt19937 类型定义的：

typedef mt19937 default_random_engine;

那是什么？嗯，mt19937 是与*梅森旋转算法*（Mersenne Twister）模板实例类型定义。64 位*梅森旋转算法*的另一个类型定义表示为 mt19937_64，它是 mersenne_twister_engine 类与 64 位数据类型（结果类型）的模板实例。

typedef mersenne_twister<unsigned long, 32, 624, 397, 31,
        0x9908b0df, 11, 7, 0x9d2c5680, 15, 0xefc60000, 18>
        mt19937;

typedef mersenne_twister_engine<_ULonglong, 64, 312, 156, 31,
        0xb5026f5aa96619e9ULL, 29,
        0x5555555555555555ULL, 17,
        0x71d67fffeda60000ULL, 37,
        0xfff7eee000000000ULL, 43,
        6364136223846793005ULL>
        mt19937_64;

不明白？别担心！我只是为了完整性提到它，因为本文中使用了 default_random_engine，而且您可能也会用于快速编码。此外，在 MSDN 文档和示例中，经常使用 mt19937。mersenne_twister（_engine）同样是一个简单引擎。

**注意**：所有 VC10 引擎类都以 _engine 结尾。如果不是，则它们不是 VC10 新增的。

现在，让我解释一些*复合引擎*，即接受另一个引擎进行操作的引擎。

如果您还记得所有引擎的一个通用方法 discard，您就会回想起它有效地丢弃了给定数量的下一个随机值。它通过调用*同一个类*的 operator() 来实现。如果您需要*附加*一个会丢弃*N*个随机数并给出下一个随机数的引擎，该怎么办？为此，您可以使用名为 discard_block_engine 的*复合*引擎。这个*模板*类接受另一个引擎和一些常量数字 - 使用它们，它可以生成随机值。这里有一个例子：

default_random_engine def_rand;
discard_block_engine<default_random_engine, 5, 2> dbe; // SEE DESCRIPTION BELOW

for(int nIter = 0; nIter <20; nIter++)
{
    wcout << def_rand() % 100 << "\t";
}

wcout << "===============\n";

for(int nIter = 0; nIter < 20; nIter++)
{
    wcout << dbe() % 100 << "\t";
}

类型为 discard_block_engine 的对象 dbe 被实例化，它将 default_random_engine 作为其*父*引擎。随机值将仅由父引擎生成，而 discard_block_engine 将根据模板参数丢弃并返回一组随机值。第二个模板参数（整数）指定*总块大小*（指定为 **P**），第三个模板参数指定*已用块大小*（**R**）。

引擎生成 R（根据上面的代码为 **2**）个随机值，在该计数之后，它会忽略（丢弃）P - R（**3**）个值。例如，如果原始数字生成为 1 到 20，它将生成：

1, 2, 6, 7, 11, 12, 16, 17...

对于这个基于 default_random_engine（梅森旋转算法）的程序，结果将如下：

12      2       34      85      4       91      29      85      98      3
35      65      40      26      39      20      19      4       97      6
===============
12      2       91      29      35      65      20      19      9       9
26      36      12      9       95      53      44      6       76      45

对 100 取模只是为了产生小数字，以便于分析。

嗯... *随机*的讨论越来越长，我推迟了对不同类的进一步讨论。如果时间允许，我一定会进行更多研究并在此处更新获得的信息。

这是 <random> 头文件中*所有*类的表格摘要。

引擎

类名	简单或复合
discard_block_engine	复合
independent_bits_engine	复合
linear_congruential_engine	简单
mersenne_twister_engine	简单
random_device	简单
shuffle_order_engine	复合
subtract_with_carry_engine	简单
xor_combine	复合

分布

类名	实现
bernoulli_distribution	伯努利分布
binomial_distribution	二项分布
cauchy_distribution	柯西分布
chi_squared_distribution	卡方分布
discrete_distribution	不确定！
exponential_distribution	指数分布
extreme_value_distribution	极值分布
fisher_f_distribution	费舍尔 F 分布
gamma_distribution	伽马分布
geometric_distribution	不确定！
lognormal_distribution	对数正态分布
negative_binomial_distribution	负二项分布
normal_distribution	正态分布
piecewise_constant_distribution	不确定！
piecewise_linear_distribution	不确定！
poisson_distribution	泊松分布
student_t_distribution	学生 t 分布
uniform_int_distribution	不确定！
uniform_real_distribution	不确定！
weibull_distribution	韦布尔分布

集合的改进

首先，关于集合。在 STL 中，set 是一种实现关联数据容器的数据结构。它*只包含唯一*值，丢弃任何重复插入。它以*有序形式*存储它们，这意味着当您遍历 set 时，值将按升序排序（使用默认比较函数）。以下示例插入一些随机值，然后显示它们：

// Codename: SET1.CPP
set<int> us;

mt19937 rnd; // mersenne!

uniform_int_distribution<> uid(1,100); // <int>

for(int n=0;n<100;n++)
   us.insert( uid(rnd) );// Random generation, distribution

// wcout << "Elements: " << us.size() << "==>\n";

for_each(us.begin(), us.end(),[](int n)
{
   std::wcout << n << "\t";
});

由于上面的代码只生成伪随机值，它将始终具有以下 60 个值：

1       4       5       6       10      11      12      13      14      15
16      18      19      22      23      28      30      31      32      37
39      40      41      43      44      45      46      48      49      50
51      55      64      65      66      67      68      69      70      71
73      75      76      77      80      81      82      83      84      85
88      91      92      93      94      96      97      98      99      100

注意：如果您没有阅读关于随机头文件，或者不感兴趣，您可以将随机元素插入替换为 rand。集合大小会有所不同！

在同一个家族中，multiset 类允许将非唯一元素*按排序顺序*放入容器中。例如：

// Codename: SET2.CPP
multiset<int> ms;

for(int n=0;n<20;n++)
    ms.insert( n % 4);

for(auto iter = ms.cbegin(); iter != ms.cend(); ++iter )
    wcout << *iter << "\t";

将产生以下输出：

0       0       0       0       0       1       1       1       1       1
2       2       2       2       2       3       3       3       3       3

因为它允许多个项具有相同的值。

集合的进步

• 包括*常量迭代器*，已在上面详细阐述。
• *Emplace* 函数和移动语义（稍后将描述）。
• 新类，名为 unordered_set 和 unordered_multiset，以及它们的*新*特殊方法。

您可以看到 set 始终按有序序列排列元素。因此，插入成本很高（约 O(log n)）- 而且，正如您可能从“大 O”符号中理解的那样，插入时间复杂度随着元素数量的增加而增加。无论如何，我不是来使用这些行话的。让我简而言之，一个集合只包含唯一元素，并且按排序顺序排列。插入、删除和搜索花费的时间相同：O(log n)。

使用 TR1，一些编译器（包括 Visual C++）添加了一个*无序集合*，名为 unordered_set，它只包含唯一元素，但没有特定的顺序。它借助*哈希*函数将元素放入一组*桶*中。

无序集合的头文件：<unordered_set>

注意：在 TR1 之前，集合的*无序性*可以通过 hash_set 和 hash_multiset 类获得。然而，这些类没有新类所具有的所有功能。

好的，在事情变得更复杂之前，让我们将我们的 set 更改为 unordered_set（在代码文件*SET1.CPP*中）：

#include <unordered_set>
....

// This is in code-named SET1.CPP, as given above
unordered_set<int> us;

并查看输出：

18      82      14      91      28      92      84      77      13      97
23      64      31      10      55      83      19      100     32      96
80      16      73      98      99      75      11      49      81      94
30      15      65      1       43      76      12      88      51      66
68      4       37      85      22      5       69      40      48      71
6       70      50      67      44      39      41      46      45      93

相同的数值集合，没有重复 - 但没有特定的顺序。您应该问的逻辑问题是：“unordered_set 比 set 快吗？” 嗯，是的！插入时间几乎相同（*需要专家评论*），但 unordered_set 定位元素的速度比 set 快。有关性能基准测试，请参阅 本文。以下代码将元素插入 set，然后搜索其中一半：

/*unordered_*/ set<int> the_set;
const int nSize = 5000000;

for(int n=0;n<nSize;n++)
    the_set.insert(n);

nEnd = GetTickCount(); // Please ignore the 15ms timing precision!
wcout << (nEnd - nStart )<< " ms\n";

// Timing for search
nStart = GetTickCount();

for(int n=nSize; n>0; n -= 2) // Alternate
{
   the_set.find(n);
}

nEnd = GetTickCount();
wcout << (nEnd - nStart )<< "m s\n";

在我的机器上，结果显示：

1123 ms 250m s

当 set 更改为 unordered_set 时，结果是：

1139ms
140ms

这明确声明 unordered_set 是搜索竞赛的获胜者。

**类似地**，在行为方面，unordered_multiset 的行为与 multiset 类相同。将 set 更改为 unordered_multiset（在*SET1.CPP*中）会产生以下输出：

18      18      82      14      91      28      28      92      92      84
13      13      13      97      97      97      23      64      64      31
31      10      10      55      55      19      19      100     100     100
32      32      96      96      96      96      80      80      80      80
80      80      16      73      98      99      75      75      11      49
49      49      81      81      94      30      15      15      1       43
43      76      76      12      88      88      51      66      66      68
4       4       4       4       37      85      22      22      69      40
40      48      71      71      5       83      83      70      77      77
50      67      44      39      6       41      46      45      65      93

这总共是 100 个数字（而不仅仅是 60 个数字），因为多集允许非唯一的数字。您还注意到，与存储*已排序*元素的 multiset 不同，unordered_multiset 不遵循排序。但是，对上面显示的数字进行仔细分析（这只是从开始到结束的迭代）会揭示相似的数字被分组在一起。这就是桶和哈希函数发挥作用并展示其作用的地方。请记住，桶和哈希函数也在无序集合中发挥作用；尽管尚未解释。

同样，当您在*SET2.CPP*中将 multiset 更改为 unordered_multiset 时，它会将数字放入桶中。由于数字很少并且已按顺序插入（0 到 3），因此结果没有差异（请参阅*SET2.CPP*的输出）。但对于其他值的集合和插入顺序，multiset 和 unordered multiset 肯定会有所不同，因为无序集不按排序顺序排列元素。

*无序*集合和映射使用桶和哈希函数来存储元素。有一组函数可以查看它们的性能、有多少桶、每个桶中有多少元素以及桶的*加载顺序*。您还可以要求重新排列桶（*重新哈希*）。还可以使用自己的函数作为哈希函数。由于这些概念对无序集合和无序映射都是通用的，因此我将在下面的无序映射讨论之后进行阐述。

映射的改进

对于不了解 STL 映射或对其有模糊概念的读者，请允许我简要介绍一下。map 存储*键*及其*值*，并且键必须是唯一的。对于 set，键就是值（即两者相同）。*值*可以重复，但*键*不能。在学生集合中，学号可以作为键（学号是唯一的），学生姓名可以作为值。以下示例消除了部分疑虑：

map<int, string> Roll2Name;

Roll2Name.insert(make_pair(12, "Canon"));
Roll2Name.insert(make_pair(13, "Sony"));
Roll2Name.insert(make_pair(14, "Nikon"));
Roll2Name.insert(make_pair(15, "Olympus"));

// Get name of student having roll-no 14
string sName = Roll2Name[14]; // Same as Roll2Name.find(14)->second;

wcout << "Name: " << sName.c_str();

map 的元素类型为 pair<Key, Value>。因此，对于上面的代码，它是 <int,string> 对。find 方法返回 pair<K,V> 类型的迭代器。

类似地，multimap 允许将非唯一键存储到映射中。两种映射类型都以排序顺序存储键。下面的示例将作进一步说明。

映射的进步

• 包含常量迭代器。
• *Emplace* 函数和移动语义，稍后将进行描述。
• 成员函数 map::at，它在元素访问方面与 map::operator[] 的行为相同。但是，与 operator[] 不同，如果*在*映射中找不到键，它*不*允许插入元素。
• 新类，名为 unordered_map 和 unordered_multimap，以及它们的*新*特殊操作。

与有序集合到无序集合的更改*类似*，STL 现在通过 unordered_map 和 unordered_multimap 类分别提供无序映射和无序多重映射。

无序映射所需的头文件：<unordered_map>

在 TR1 之前，映射的*无序性*可以通过 hash_map 和 hash_multimap 类获得，尽管它们不具备新类所具有的所有功能。

让我们再举一个例子，我将用它来解释不同类型的映射：

// NOTE: This example is just for illustration,
// The squares would not correspond to their actual sqrts.

map<int, int> Squares;
int e;
for(int n=2; n<100; n++)
{
   e = (n % 10)+1;
   Squares.insert(make_pair(e, n*n));
}

for (auto iter = Squares.cbegin(); iter != Squares.cend(); ++iter)
{
     wcout << "\nNumber: " << iter->first <<
              "\tSquare: " << iter->second;
}

由于键（e）仅限于 1 到 10，下一个 insert 调用将简单地替换值（请参阅文档以了解更多信息）。因此，输出将如下：

Number: 1       Square: 100
Number: 2       Square: 121
Number: 3       Square: 4
Number: 4       Square: 9
Number: 5       Square: 16
Number: 6       Square: 25
Number: 7       Square: 36
Number: 8       Square: 49
Number: 9       Square: 64
Number: 10      Square: 81

而且，如果我将 square 的类型从 map 更改为 multimap，输出将如下：

...
Number: 8       Square: 7569
Number: 8       Square: 9409
Number: 9       Square: 64
Number: 9       Square: 324
...
Number: 9       Square: 7744
Number: 9       Square: 9604
Number: 10      Square: 81
Number: 10      Square: 361
...

为什么？就像 multiset 允许插入多个值一样，multimap 允许插入多个键（具有不同值！）。

**现在**，来到新类。当我将类型从 map 更改为 unordered_map 时，集合将如下所示：

Number: 3       Square: 4
Number: 4       Square: 9
Number: 5       Square: 16
Number: 6       Square: 25
Number: 7       Square: 36
Number: 8       Square: 49
Number: 1       Square: 100
Number: 9       Square: 64
Number: 10      Square: 81
Number: 2       Square: 121

正如您所见，键现在是*无序的*，因为 unordered_map 不关心键的顺序。它使用桶和哈希函数来放置元素，我稍后将详细介绍。

最后，当我将 Square 的数据类型更改为 unordered_multimap 时，输出是：

...
Number: 8       Square: 7569
Number: 8       Square: 9409
Number: 1       Square: 100
Number: 1       Square: 400
...
Number: 1       Square: 8100
Number: 9       Square: 64
Number: 9       Square: 324
...
Number: 9       Square: 9604
Number: 10      Square: 81
...
Number: 10      Square: 9801
Number: 2       Square: 121
Number: 2       Square: 441
Number: 2       Square: 961
...

就像 unordered_multiset 的分散性一样，元素被放置在不同的桶中，因此迭代不会给出正确的顺序。但是，应该注意的是，相同键的值被放在一起（*需要专家评论*）。

好的，让我们再看一个代码，它将向我们展示所有四种映射类的性能统计：

map<int, double> IntDouble;
const int nSize = 2500000;

DWORD nStart = GetTickCount();
DWORD nEnd;

// Insert
for (int n=0; n<nSize; n++)
{
   IntDouble.insert( make_pair (n, n * 2.5));
}

nEnd = GetTickCount();
wcout << (nEnd - nStart )<< " ms\n";

nStart = GetTickCount();

// Alternate Search
for(int n= nSize; n>0 ; n -= 2)
   IntDouble.find(n);

nEnd = GetTickCount();
wcout << (nEnd - nStart )<< " ms\n";

下表显示了结果：

容器/时间（毫秒）	插入	搜索
map	468	171
multimap	468	110
unordered_map	749	78
unordered_multimap	749	62

显示的时间仅供参考。多次运行后，我发现 map 和 multimap 的行为始终如所示。但是，unordered_map 的*搜索*速度很多时候达到了与 unordered_multimap 相同的水平，尽管它从未超过 unordered_multimap 的速度。

由于本文不是关于映射的介绍，我没有写，但简而言之。对于多重映射，应使用 lower_bound 和 upper_bound 来迭代给定键的值，因为多重映射存储给定键上的多个值。对于多重映射，find 方法将始终返回给定键中*第一个*元素的迭代器。count 方法可用于查找给定键上有多少个元素。

哈希、桶和更多...

本节探讨适用于*所有四个无序*容器的桶、哈希函数和比较函数。所有这些概念对所有容器都相似，如果它们不同，我会明确说明。让我们从简单的操作开始，然后深入细节。

本节将使用以下 typedef 和声明的变量，我将在更改 typedef 时注明。

typedef unordered_set<int> Container;
Container cont;

让我们看看*默认*桶的数量：

wcout << cont.bucket_count() << "\n";

这将返回 8，对于所有四种类型的无序容器（MS 实现，其他可能有所不同）。这意味着总共有八个桶，元素将被放置在其中。每个桶中的元素数量是多少？嗯，我们可以使用 max_load_factor 来查找：

wcout << cont.max_load_factor() << "\n"; // Returns 1.0

当我们向容器中添加元素时，统计数据会发生变化：

for (int n=0; n<10; ++n)
{
   cont.insert(n);
}

wcout << cont.bucket_count() << "\n"; // Returns 64
wcout << cont.max_load_factor() << "\n"; // Returns 1

这意味着现在有 64 个桶，并且每个桶（仍然）只能容纳 1 个元素。如果我们只插入了 8 个（或更少）元素，桶的数量将保持不变（8）。同样，当我们插入 65 个或更多元素时，桶的数量将增加到 512，依此类推（仍然，每个桶只能容纳*一个*元素）。由于元素数量可能少于桶的数量，并非所有桶都会被填满（无论*桶大小*如何）；一些桶可能包含零个元素。

应该会产生一些问题：

• 如何更改桶大小？
• 如何知道哪个桶中有多少元素？
• 所有桶中的平均元素数量是多少（称为*负载因子*）？
• 删除和插入元素后，所有桶（即哈希表）的情况如何？

桶的*可管理性*取决于*负载因子*。您可以使用另一个重载 max_load_factor 来*设置*负载因子。它只是指定要放入桶中的最大元素数量。因此，指定更大的值意味着桶更少，因为一个桶现在可以容纳更多值。例如：

cont.max_load_factor(500);

要求哈希表将最多 500 个元素放入每个桶中。因此，当您插入 500 个或更少的元素时，将只使用一个桶 -*不*！请记住，负载因子只是每个桶中平均元素数量。您只是建议容器使用每个桶容纳更多（或更少）元素。示例：

cont.max_load_factor(100);

for (int n=0;n<150;++n) // 150 elements
{
   cont.insert(n);
}

wcout << cont.bucket_count() << "\n";
wcout << cont.max_load_factor() << "\n";
wcout << cont.max_bucket_count() << "\n";
wcout << cont.load_factor() << "\n";

这将给出以下输出：

8
100
8
18.75

桶的数量是 8，因为这些最小的桶（每个容量为 100）足以容纳所有 150 个元素。如果您插入 800 个或更多的元素，桶的数量将增加到 64（重新阅读上面的逻辑）。以下代码显示了每个桶中有多少元素：

for (int n = 0; n < cont.bucket_count(); ++n)
{
    wcout << "Bucket " << n <<
             " has " << cont.bucket_size(n) << " elements\n";
}

这将显示类似如下的内容：

Bucket 0 has 19 elements
Bucket 1 has 18 elements
Bucket 2 has 18 elements
Bucket 3 has 19 elements
Bucket 4 has 19 elements
Bucket 5 has 19 elements
Bucket 6 has 19 elements
Bucket 7 has 19 elements

您会看到桶被最优地填充。有趣的是，使用相同的 150 个值，所有四种无序容器的元素放置方式相同。

您可能想知道给定桶包含哪些元素。嗯，这很简单 - 您只需要使用*本地迭代器*；无序类特有的迭代器类型。它们通过 begin 和 end 重载来支持。没有 cbegin/cend 方法，因为类型 [const_]local_iterator 只代表常量迭代器。以下代码迭代桶 0：

// Valid only if Container represents set
// otherwise l_iter would be pair<K,V>

Container::const_local_iterator l_iter;
for(l_iter = cont.begin(0); l_iter != cont.end(0); ++l_iter)
   wcout << *l_iter << "\t";

这将显示以下文本：

144    136     128     120     112     104     96      88      80      72
64      56      48      40      32      24      16      8       0

由于哈希方案相同，所有四种容器都会以相同的顺序显示相同的值。

最后一件事，在相同的半径内，是找出特定元素被放入哪个桶中。这是通过 bucket 方法实现的。它返回一个零基桶位置，其中元素被放入（或未被放入）。是的，通过哈希，它会为不存在的元素返回正确的桶号！例如，输出为

wcout << "Element 144 is in: " << cont.bucket(144)
      <<"\nNon-existent 1131 is/would-be in: " << cont.bucket(1131);

/* Element 144 is in: 0
Non-existent 1131 is/would-be in: 5 */

通过设置最大负载因子并插入元素，您可以看到桶的数量会适当地增加。如果您想自己设置桶的数量怎么办？例如，而不是让它自行从 8、64、512、4096... 增长，您可能想给它一个提示。您可以通过简单地调用 rehash 方法来做到这一点。此方法可以随时调用，是在插入元素之前、所有元素插入之后、插入过程中，还是在元素删除之后。rehash 方法始终会重建哈希表。它会将最小哈希大小设置为 8，然后逐渐加倍，直到满足您的请求。例如，如果您指定 10，它将设置为 16；如果您指定 100，它将设置为 128。请记住，最大负载因子仍然有效。

因此，当您调用

cont.max_load_factor(100);
cont.rehash(20);

for (int n=0;n<2500;++n)
{  cont.insert( n ); }

每个桶最多可以包含 100 个元素，总共有 32 个桶，每个桶大约有 78 个元素。当您向其中添加 5000 个元素时，它将超出负载因子（高于 100），因此桶的数量将增加到 256。

听起来很混乱？请记住，当负载因子超出其限制时，哈希表会添加更多桶，增加 **8 倍**。这意味着，对于上面的例子，32 * 8 = 256。如果您指定 10（即 16）作为桶的大小，桶的增量将如下所示：128、1024、8192 等等。这完全取决于给定的负载因子。

更多内容

...

更改历史

• 2010 年 9 月 11 日 - 发布第一个版本。解释了常量迭代器、array 和 tuple。
• 2010 年 9 月 12 日 - 详细介绍了 <algorithm> 的八个函数。
• 2010 年 9 月 13 日 - 演示了 is_sorted 和 is_sorted_until。
• 2010 年 9 月 16 日 - 阐述了堆、is_heap 和 is_heap_until。
• 2010 年 9 月 19 日 - <random> 头文件及其几个类。
• 2010 年 9 月 22 日 - 进一步阐述了 <random> 头文件。
• 2010 年 9 月 25 日 - 无序集合和映射部分；在常量迭代器部分包含映射/集合。
• 2010 年 9 月 28 日 - 部分的本地链接；关于 rehash 的内容。
• 其余概念正在准备中。敬请关注！