STL 提供了一套算法，可以和它提供的容器一起使用。这些算法都使用迭代器。迭代器是一种抽象机制，允许遍历许多不同的 STL 集合。本章包括迭代器和一些不同的算法以及它们的用途。
配方 8-1。使用迭代器定义容器中的序列
问题
你有一个 STL 容器，你想在这个容器中标记一个序列，这个序列在特定的点开始和结束。
解决办法
STL 提供了适用于所有容器的迭代器,可以用来表示容器中序列的开始和结束。该序列可以包括容器中的每个节点，也可以包括容器中节点的子集。
它是如何工作的
迭代器的工作方式与指针相似。它们的语法非常相似。你可以在清单 8-1 中看到迭代器的使用。
清单 8-1 。使用带有vector和的iterator
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
int main(int arcg, char* argv[])
{
using IntVector = vector<int32_t>;
using IntVectorIterator = IntVector::iterator;
IntVector myVector{ 0, 1, 2, 3, 4 };
for (IntVectorIterator iter = myVector.begin(); iter != myVector.end(); ++iter)
{
cout << "The value is: " << *iter << endl;
}
return 0;
}在清单 8-1 中的main函数中创建了一个int类型的vector。一个类型别名被用来制作一个新类型的IntVector来表示这种类型的集合。第二个别名用于表示这个集合使用的iterator的类型。可以看到iterator类型是通过初始的vector类型访问的。这是必要的，因为iterator也必须操作与矢量本身操作相同类型的对象。在 vector 类型中包含迭代器类型允许您指定要操作的类型，在本例中是int32 _t，同时用于两者。
iterator类型用于在for循环中获取对myVector集合的开始和结束的引用。向量返回迭代器的begin和end方法。如果表示集合开始的iterator等于表示集合结束的迭代器，则称该集合为空。这是iterators与指针共有的第一个属性，它们是可比较的。
for 循环中的iter变量被初始化为由vector::begin方法返回的值。执行for循环，直到 iter 变量等于由vector::end方法 返回的iterator。这说明集合中的值序列可以用两个iterators来表示，一个在序列的开头，一个在序列的结尾。一个iterator提供了一个增量操作符，允许iterator移动到序列中的下一个元素。这就是如何将 for 循环中的iter变量初始化为由begin返回的iterator，并针对end进行测试，直到序列遍历完成。这也恰好是iterators与指针共享的另一个属性，递增或递减会将迭代器移动到序列中的下一个或最后一个元素。
注意不是所有的迭代器都支持递增和递减操作。在下面的段落中，您将会看到这种情况。
用iterator覆盖的最后一个重要操作是解引用操作符。你可能在标准指针操作中熟悉这些，这是迭代器与指针共享的最后一个属性。从清单 8-1 中可以看到，解引用操作符用于检索由iterator表示的值。在本例中，解引用用于从集合中检索每个迭代器，并将其发送到控制台。图 8-1 表明情况就是如此。
图 8-1 。当myVector集合被遍历时清单 8-1 的输出
试图在不使用解引用操作符的情况下打印出iterator会导致编译错误，因为cout::<<操作符不支持iterator类型。
清单 8-1 中的代码使用了标准的正向迭代器。这种迭代器为容器中的每个元素提供非常量访问。清单 8-2 显示了这个属性的含义。
清单 8-2 。使用非常数迭代器
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
int main(int arcg, char* argv[])
{
using IntVector = vector<int32_t>;
using IntVectorIterator = IntVector::iterator;
IntVector myVector(5, 0);
int32_t value{ 0 };
for (IntVectorIterator iter = myVector.begin(); iter != myVector.end(); ++iter)
{
*iter = value++;
}
for (IntVectorIterator iter = myVector.begin(); iter != myVector.end(); ++iter)
{
cout << "The value is: " << *iter << endl;
}
return 0;
}如果你将清单 8-2 与清单 8-1 进行比较，你会发现myVector集合的初始化是以不同的方式处理的。清单 8-2 初始化vector以包含值 0 的 5 个副本。然后一个for循环遍历vector，并使用iterator解引用操作符将递增后的值变量分配给myVector中的每个位置。由于iterator类型的非常数性质，这是可能的。如果你想使用一个iterator，你知道它不应该有写权限，那么你可以使用一个const_iterator，如清单 8-3 所示。
清单 8-3 。使用const_iterator
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
int main(int arcg, char* argv[])
{
using IntVector = vector<int32_t>;
using IntVectorIterator = IntVector::iterator;
using ConstIntVectorIterator = IntVector::const_iterator;
IntVector myVector(5, 0);
int32_t value{ 0 };
for (IntVectorIterator iter = myVector.begin(); iter != myVector.end(); ++iter)
{
*iter = value++;
}
for (ConstIntVectorIterator iter = myVector.cbegin(); iter != myVector.cend(); ++iter)
{
cout << "The value is: " << *iter << endl;
}
return 0;
}清单 8-3 在第二个for循环中使用vector::cbegin和vector::cend方法来获得对myVector元素的访问，但不提供写访问。任何试图给const_iterator赋值的行为都会导致编译错误。C++ 集合提供的iterator和const_iterator类型都是正向迭代器的例子。这意味着它们都按照您可能会想到的顺序从头到尾遍历集合。STL 集合也支持reverse_iterator和const_reverse_iterator类型。这些允许你向后遍历你的序列。清单 8-4 显示了使用reverse_itertor从最高到最低初始化myVector集合。
清单 8-4 。使用reverse_iterator 初始化myVector
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
int main(int arcg, char* argv[])
{
using IntVector = vector<int32_t>;
using IntVectorIterator = IntVector::iterator;
using ConstIntVectorIterator = IntVector::const_iterator;
using ReverseIntVectorIterator = IntVector::reverse_iterator;
using ConstReverseIntVectorIterator = IntVector::const_reverse_iterator;
IntVector myVector(5, 0);
int32_t value { 0 };
for (ReverseIntVectorIterator iter = myVector.rbegin(); iter != myVector.rend(); ++iter)
{
*iter = value++;
}
for (ConstIntVectorIterator iter = myVector.cbegin(); iter != myVector.cend(); ++iter)
{
cout << "The value is: " << *iter << endl;
}
return 0;
}清单 8-4 显示reverse_iterator应该与vector提供的rbegin 和rend方法一起使用。递增一个reverse_iterator会导致它在集合中向后移动。图 8-2 显示myVector集合已经以相反的顺序存储了值。
图 8-2 。从myVector开始按相反顺序取值
图 8-2 中的输出也可以使用清单 8-5 中的代码来实现，该代码使用一个const_reverse_iterator来打印数值。
清单 8-5 。使用const_reverse_iterator反向打印myVector
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
int main(int arcg, char* argv[])
{
using IntVector = vector<int32_t>;
using IntVectorIterator = IntVector::iterator;
using ConstIntVectorIterator = IntVector::const_iterator;
using ReverseIntVectorIterator = IntVector::reverse_iterator;
using ConstReverseIntVectorIterator = IntVector::const_reverse_iterator;
IntVector myVector(5, 0);
int32_t value{ 0 };
for (IntVectorIterator iter = myVector.begin(); iter != myVector.end(); ++iter)
{
*iter = value++;
}
for (ConstReverseIntVectorIterator iter = myVector.crbegin();
iter != myVector.crend();
++iter)
{
cout << "The value is: " << *iter << endl;
}
return 0;
}清单 8-5 使用const_reverse_iterator以及crbegin和crend方法从最后到第一步遍历集合，并以相反的顺序打印值。
迭代器将在本章的剩余部分扮演重要的角色，因为它们被用作 STL 提供的算法的输入。
食谱 8-2。对容器中的每个元素调用函数
问题
你有一个容器，想要一个简单的方法来调用每个元素的函数。
解决办法
STL 提供了for_each函数 ,它采用一个开始迭代器、一个结束迭代器和一个函数来调用两者之间的每个元素。
它是如何工作的
for_each函数可以传递两个迭代器。这些迭代器定义了容器中应该被遍历的起点和终点。3 rd 参数是一个应该为每个元素调用的函数。元素本身被传递到函数中。清单 8-6 显示了for_each函数的用法。
清单 8-6 。for_each算法
#include <algorithm>
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector<int32_t> myVector
{
1,
2,
3,
4,
5
};
for_each(myVector.begin(), myVector.end(),
[](int32_t value)
{
cout << value << endl;
});
return 0;
}清单 8-6 中的代码创建了一个包含 5 个元素的vector，数字 1 到 5。向for_each函数传递由begin和end方法返回的迭代器，以定义应该传递给参数 3 中提供的函数的值的范围。参数 3 是未命名的函数或 lambda。
lambda 的方括号表示捕获列表。这个列表用于允许 lambda 访问存在于创建它的函数中的变量。在这种情况下，我们没有从函数中捕获任何变量。括号表示参数列表。清单 8-1 中的 lambda 将一个int32_t作为参数，因为它是存储在vector中的类型。花括号表示函数体，就像它们表示标准函数体一样。执行这段代码会产生如图图 8-3 所示的输出。
图 8-3 。清单 8-6 中的for_each和生成的输出
生成此输出是因为for_each算法将来自myVector中每个位置的整数传递给所提供的函数，在本例中是一个 lambda。
食谱 8-3。查找容器中的最大值和最小值
问题
偶尔你会想找出容器中的最大值或最小值。
解决办法
STL 提供了允许你在 STL 容器中找到最大和最小值的算法。这些是min_element和max_element功能。
它是如何工作的
寻找容器中的最小值
min_element功能通过在给定序列的开头和结尾放置一个iterator来运行。它遍历该序列，并找到该序列中包含的最小值。清单 8-7 展示了这个算法的使用。
清单 8-7 。使用最小元素算法
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector<int> myVector{ 4, 10, 6, 9, 1 };
auto minimum = min_element(myVector.begin(), myVector.end());
cout << "Minimum value: " << *minimum << std::endl;
return 0;
}在这种情况下，您可以看到一个vector被用来存储integer元素。向min_element函数传递的iterator表示vector包含的序列的开始和结束。该算法向包含最小值的元素返回一个iterator。我在这里使用auto是为了避免写出整个迭代器的类型(应该是vector<int>::iterator)。很明显，当查看输出值的行时，返回的是迭代器。从迭代器中检索integer值需要指针解引用操作符。您可以在图 8-4 中看到代码生成的输出。
清单 8-7 中的容器显示了一个容器存储整数值的简单例子。这种情况是微不足道的，因为两个int变量已经可以使用<操作符进行比较。通过在你的类中提供一个重载的<操作符，你可以在你自己的类中使用min_element。你可以在清单 8-8 中看到这样的例子。
清单 8-8 。将min_element与包含<操作符的class结合使用
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class MyClass
{
private:
int m_Value;
public:
MyClass(const int value)
: m_Value{ value }
{
}
int GetValue() const
{
return m_Value;
}
bool operator <(const MyClass& other) const
{
return m_Value < other.m_Value;
}
};
int main(int argc, char* argv[])
{
vector<MyClass> myVector{ 4, 10, 6, 9, 1 };
auto minimum = min_element(myVector.begin(), myVector.end());
if (minimum != myVector.end())
{
cout << "Minimum value: " << (*minimum).GetValue() << std::endl;
}
return 0;
}清单 8-7 和 10-8 的不同之处在于使用了MyClass对象的vector而不是integer值的vector。然而，对min_element的呼叫仍然完全一样。在这种情况下，min_element调用将遍历序列，并使用添加到MyClass class的<操作符来查找最小值。在这种情况下，防止碰到序列的结尾也是必要的，因为 end 元素不会指向有效的对象，因此对GetValue的解引用和调用可能会崩溃。
比较非基本类型的另一个选择是直接向min_element函数提供一个比较函数。该选项如清单 8-9 中的所示。
清单 8-9 。使用带有 min_element 的独立函数
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class MyClass
{
private:
int m_Value;
public:
MyClass(const int value)
: m_Value{ value }
{
}
int GetValue() const
{
return m_Value;
}
};
bool CompareMyClasses(const MyClass& left, const MyClass& right)
{
return left.GetValue() < right.GetValue();
}
int main(int argc, char* argv[])
{
vector<MyClass> myVector{ 4, 10, 6, 9, 1 };
auto minimum = min_element(myVector.begin(), myVector.end(), CompareMyClasses);
if (minimum != myVector.end())
{
cout << "Minimum value: " << (*minimum).GetValue() << std::endl;
}
return 0;
}在清单 8-9 中，我们为min_element函数提供了一个指向比较函数的指针。该函数用于比较从MyClass GetValue方法返回的值。比较函数 是以一种非常特殊的方式构造的，它有两个参数，都是对MyClass对象的常量引用。如果第一个参数被评估为小于第二个参数，该函数应该返回true。选择名称left和right是为了帮助形象化<操作员的通常外观。对min_element的调用被修改为包含第三个参数，即指向CompareMyClasses函数的指针。清单 10-8 和清单 10-9 中显示的代码产生的输出与图 8-4 中显示的输出相同。
寻找容器中的最大值
min_element函数可用于查找序列中的最小值，而max_element函数可用于查找最大值。该函数的使用方式与min_element函数完全相同，如清单 8-10 中的所示。
清单 8-10 。使用max_element
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class MyClass
{
private:
int m_Value;
public:
MyClass(const int value)
: m_Value{ value }
{
}
int GetValue() const
{
return m_Value;
}
bool operator <(const MyClass& other) const
{
return m_Value < other.m_Value;
}
};
bool CompareMyClasses(const MyClass& left, const MyClass& right)
{
return left.GetValue() < right.GetValue();
}
int main(int argc, char* argv[])
{
vector<int> myIntVector{ 4, 10, 6, 9, 1 };
auto intMinimum = max_element(myIntVector.begin(), myIntVector.end());
if (intMinimum != myIntVector.end())
{
cout << "Maxmimum value: " << *intMinimum << std::endl << std::endl;
}
vector<MyClass> myMyClassVector{ 4, 10, 6, 9, 1 };
auto overrideOperatorMinimum = max_element(myMyClassVector.begin(),
myMyClassVector.end());
if (overrideOperatorMinimum != myMyClassVector.end())
{
cout << "Maximum value: " << (*overrideOperatorMinimum).GetValue() <<
std::endl << std::endl;
}
auto functionComparisonMinimum = max_element(myMyClassVector.begin(),
myMyClassVector.end(),
CompareMyClasses);
if (functionComparisonMinimum != myMyClassVector.end())
{
cout << "Maximum value: " << (*functionComparisonMinimum).GetValue() <<
std::endl << std::endl;
}
return 0;
}清单 8-10 显示了max_element函数可以用来代替min_element函数。认识到max_element函数仍然使用<操作符是很重要的。看起来，max_element可能会使用>操作符，但是使用<操作符并响应false而不是true的结果来表明一个值大于另一个值也是有效的。
食谱 8-4。对序列中某个值的实例计数
问题
有时您可能希望知道一个序列中有多少个特定值的实例。
解决办法
STL 提供了一种叫做count的算法。该算法可以搜索一系列值，并返回找到所提供值的次数。
它是如何工作的
count函数有 3 个参数，一个开始参数iterator，一个结束参数iterator和一个要查找的值。给定这三条信息，算法将返回该值出现的次数。清单 8-11 展示了这个算法的使用。
清单 8-11 。使用计数算法
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector<int> myVector{ 3, 2, 3, 7, 3, 8, 9, 3 };
auto number = count(myVector.begin(), myVector.end(), 3);
cout << "The number of 3s in myVector is: " << number << endl;
return 0;
}清单 8-11 中的代码将让count函数遍历序列并返回遇到值 3 的次数。在图 8-5 中可以看到这个操作的结果是 4。
C++ 还提供了一些特殊的谓词函数，可以与字符数据和count_if函数结合使用。这些函数可以用来计算大写或小写字母的数量，以及字符是字母数字、空格还是标点符号。你可以在清单 8-12 中看到所有这些。
清单 8-12 。使用带有count的字符谓词
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
string myString{ "Bruce Sutherland!" };
auto numberOfCapitals = count_if(
myString.begin(),
myString.end(),
[](auto&& character)
{
return static_cast<bool>(isupper(character));
});
cout << "The number of capitals: " << numberOfCapitals << endl;
auto numberOfLowerCase = count_if(
myString.begin(),
myString.end(),
[](auto&& character)
{
return static_cast<bool>(islower(character));
});
cout << "The number of lower case letters: " << numberOfLowerCase << endl;
auto numberOfAlphaNumerics = count_if(
myString.begin(),
myString.end(),
[](auto&& character)
{
return static_cast<bool>(isalpha(character));
});
cout << "The number of alpha numeric characters: " << numberOfAlphaNumerics << endl;
auto numberOfPunctuationMarks = count_if(
myString.begin(),
myString.end(),
[](auto&& character)
{
return static_cast<bool>(ispunct(character));
});
cout << "The number of punctuation marks: " << numberOfPunctuationMarks << endl;
auto numberOfWhiteSpaceCharacters = count_if(
myString.begin(),
myString.end(),
[](auto&& character)
{
return static_cast<bool>(isspace(character));
});
cout << "The number of white space characters: " << numberOfWhiteSpaceCharacters << endl;
return 0;
}在清单 8-12 中，可以看到谓词使用 lambda 传递给了count_if函数。lambda 对于count_if模板来说是必要的，它可以满足被提供的函数是一个返回bool的谓词。count_if函数将返回所提供的函数返回true的次数。您可以在图 8-6 的中看到不同调用count_if的结果。
清单 8-6 中提供的字符串相当简单，因此很容易确认字符谓词是否按预期工作。您可以对照图 8-6 的结果来确认这一点。
配方 8-5。在序列中查找值
问题
您可能希望找到序列中匹配特定值的第一个元素的迭代器。
解决办法
STL 提供了 find 函数来检索序列中匹配给定值的第一个元素的迭代器。
它是如何工作的
find 函数可用于检索与您提供的值匹配的第一个值的迭代器。你可以用它从头到尾地浏览一个序列。清单 8-13 展示了如何使用 while 循环来移动整个序列。
清单 8-13 。使用find
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
string myString{ "Bruce Sutherland" };
auto found = find(myString.begin(), myString.end(), 'e');
while (found != myString.end())
{
cout << "Found: " << *found << endl;
found = find(found+1, myString.end(), 'e');
}
return 0;
}清单 8-13 中的代码将打印出字母 e 两次，因为变量myString中的string中有两个字母。对find的第一次调用返回一个迭代器，指向字符串中字符 e 的第一个实例。然后，while 循环中的调用从紧接该迭代器之后的位置开始。这使得 find 函数逐步搜索所提供的数据集，并最终到达末尾。一旦发生这种情况，while 循环将终止。清单 8-13 中的代码生成如图 8-7 所示的输出。
配方 8-6。排序序列中的元素
问题
有时，容器中的数据变得无序，您希望对这些数据进行重新排序。
解决办法
STL 提供了排序算法来对序列中的数据进行重新排序。
它是如何工作的
sort 函数将一个迭代器放在序列的开头，将一个迭代器放在序列的结尾。它会自动将迭代器之间的值按数字升序排序。你可以在清单 8-14 中看到实现这一点的代码。
清单 8-14 。使用sort算法
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector<int> myVector{ 10, 6, 4, 7, 8, 3, 9 };
sort(myVector.begin(), myVector.end());
for (auto&& element : myVector)
{
cout << element << ", ";
}
cout << endl;
return 0;
}清单 8-14 中的代码将把myVector中的值按升序重新排序。图 8-8 显示了这段代码产生的输出。
图 8-8 。按升序排序的 myVector 元素
如果您希望按照自定义的顺序对数据进行排序，比如降序，那么您必须为sort算法提供一个谓词函数。清单 8-15 展示了一个谓词对一个数字vector进行降序排序的用法。
清单 8-15 。使用带sort的谓词
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
bool IsGreater(int left, int right)
{
return left > right;
}
int main(int argc, char* argv[])
{
vector<int> myVector{ 10, 6, 4, 7, 8, 3, 9 };
sort(myVector.begin(), myVector.end(), IsGreater);
for (auto&& element : myVector)
{
cout << element << ", ";
}
return 0;
}清单 8-15 中的 myVector 中的数据与清单 8-14 中存储的数据相同。这两个清单的区别是在清单 8-15 中使用了IsGreater函数。这被传递给sort函数，用于比较myVector中的值。标准排序函数将数值从最低到最高排序，如图 8-9 中的所示。图 8-10 显示清单 8-15 中的代码将把数字从最高到最低排序。
