21天学通C++读书笔记（二十二：STL 算法）

21天学通C++读书笔记（二十二：STL 算法）

1. 什么是STL 算法

• 查找、搜索、删除和计数是一些通用算法，其应用范围很广。STL 通过通用的模板函数提供了这些算法以及其他的很多算法，可通过迭代器对容器进行操作
• 并非所有算法都对容器进行操作，因此并非所有算法都需要迭代器。有些算法接受一对值，例如，swap() 将这对值交换。同样，min() 和 max() 也对值进行操作。

2. STL 算法的分类

STL 算法分两大类：非变序算法与变序算法

2.1 非变序算法

2.2 变序算法

3. 使用STL 算法

3.1 根据值或条件查找元素

#include <iostream>
#include <algorithm>
#include <vector>int main() {using namespace std;vector<int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };cout << "Enter number to find in collection: ";int numToFind = 0;cin >> numToFind;auto element = find (numsInVec.cbegin(), // Start d(),   // End of rangenumToFind);          // Element to findif (element != d()) {cout << "Value " << *element << " found!" << endl;} else {cout << "No element contains value " << numToFind << endl;}cout << "Finding the first even number using find_if: " << endl;auto evenNum = find_if (numsInVec.cbegin(), // Start d(),  // End of range[](int element) { return (element % 2) == 0; } );if (evenNum != d()) {cout << "Number '" << *evenNum << "' found at position [";// 确定找到的元素相对于容器起点的位置cout << distance (numsInVec.cbegin(), evenNum) << "]" << endl;}return 0;
}

3.2 在集合中搜索元素或序列

• 有时需要查找序列或模式，在这种情况下，应使用 search() 或 search_n()
  • search() 用于在一个序列中查找另一个序列
  • search_n() 用于在容器中查找 n 个相邻的指定值

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>
using namespace std;template <typename T>
void DisplayContents (const T& container) {for (auto element = container.cbegin(); element != d(); ++element) {cout << *element << ' ';}   cout << endl;
}int main() {vector<int> numsInVec{ 2017, 0, -1, 42, 10101, 25, 9, 9, 9 };list<int> numsInList{ -1, 42, 10101 };cout << "The contents of the sample vector are: " << endl;DisplayContents (numsInVec);cout << "The contents of the sample list are: " << endl;DisplayContents (numsInList);cout << "search() for the contents of list in vector:" << endl;auto range = search (numsInVec.cbegin(), // Start range to d(), // End range to search innumsInList.cbegin(), // Start range to d()); // End range to search forif (range != d()) {cout << "Sequence in list found in vector at position: ";cout << distance (numsInVec.cbegin(), range) << endl;}cout << "Searching {9, 9, 9} in vector using search_n(): " << endl;auto partialRange = search_n (numsInVec.cbegin(), // d(),   // End range3,  // Count of item to be searched for9);   // Item to search forif (partialRange != d()) {cout << "Sequence {9, 9, 9} found in vector at position: ";cout << distance (numsInVec.cbegin(), partialRange) << endl;}return 0;
}

3.3 计算包含给定值或满足给定条件的元素数

• std::count() 计算包含给定值（使用相等运算符==进行测试）的元素数
• std::count_if() 计算这样的元素数：满足通过参数传递的一元谓词（可以是函数对象，也可以是lambda 表达式）

#include <algorithm>
#include <vector>
#include <iostream>// 一元谓词
template <typename elementType>
bool IsEven (const elementType& number) {return ((number % 2) == 0); // true, if even
}int main () {using namespace std;vector <int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };size_t numZeroes = count (numsInVec.cbegin(), d(), 0); // 计算0的个数cout << "Number of instances of '0': " << numZeroes << endl;size_t numEvenNums = count_if (numsInVec.cbegin (),d (), IsEven <int> );cout << "Number of even elements: " << numEvenNums << endl;cout << "Number of odd elements: ";cout << numsInVec.size () - numEvenNums << endl;return 0;
}

3.4 将容器中的元素初始化为指定值

• STL 算法 fill() 和 fill_n() 用于将指定范围的内容设置为指定值

#include <algorithm>
#include <vector>
#include <iostream>int main () {using namespace std;vector<int> numsInVec (3);// fill all elements in the container with value 9fill (numsInVec.begin(), d(), 9);// Increase the size of the vector to hold size (6);// Fill the three elements starting at offset position 3 with value -9fill_n (numsInVec.begin() + 3, 3, -9); // 起始位置, 元素数, 要设置的值cout << "Contents of the vector are: " << endl;for (size_t index = 0; index < numsInVec.size(); ++index) {cout << "Element [" << index << "] = ";cout << numsInVec [index] << endl;}return 0;
}

3.5 使用std::generate() 将元素设置为运行阶段生成的值

• 函数 fill() 和 fill_n() 将集合的元素设置为指定的值，而 generate() 和 generate_n() 用于将集合的内容设置为一元函数返回的值

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>
#include <ctime>int main () {using namespace std;srand(time(NULL)); // seed random generator using timevector<int> numsInVec (5);generate (numsInVec.begin(), d(), // rangerand); // generator functioncout << "Elements in the vector are: ";for (size_t index = 0; index < numsInVec.size (); ++ index) {cout << numsInVec [index] << " ";}    cout << endl;list<int> numsInList (5);generate_n (numsInList.begin(), 3, rand); // 起始位置, 调用rand()次数, randcout << "Elements in the list are: ";for (auto element = numsInList.begin(); element != d(); ++element) {cout << *element << ' ';}    return 0;
}

3.6 使用 for_each() 处理指定范围内的元素

• 算法 for_each() 对指定范围内的每个元素执行指定的一元函数对象
• 也可使用接受一个参数的 lambda 表达式代替一元函数对象

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;template <typename elementType>
struct DisplayElementKeepcount {int count;DisplayElementKeepcount (): count (0) {}void operator () (const elementType& element) {++ count;cout << element << ' ';}
};int main () {vector<int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };cout << "Elements in vector are: " << endl;DisplayElementKeepcount<int> functor =for_each (numsInVec.cbegin(),   // Start d (),      // End of rangeDisplayElementKeepcount<int> ()); // functorcout << endl;// 使用 for_each 返回值中存储的状态cout << "'" << unt << "' elements displayed" << endl;string str ("for_each and strings!");cout << "Sample string: " << str << endl;cout << "Characters displayed using lambda:" << endl;int numChars = 0;for_each (str.cbegin(), d (),[&numChars](char c) { cout << c << ' '; ++numChars; } );cout << endl;cout << "'" << numChars << "' characters displayed" << endl;return 0;
}

3.7 使用 std::transform() 对范围进行变换

通过使用迭代器，可将容器及其实现同 STL 算法分离：transform() 是一种处理范围的算法，它无需知道实现这些范围的容器的细节。因此，虽然这里的输入范围为 vector，而输出范围为 deque，但该算法仍管用——只要指定范围的边界（提供给 transform 的输入参数）有效

#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <iostream>
#include <functional>int main() {using namespace std;string str ("THIS is a TEst string!");cout << "The sample string is: " << str << endl;string size (str.size());transform (str.cbegin(), // start d(),   // end source rangestrLowerCaseCopy.begin(), // start destination range::tolower);        // unary functioncout << "Result of 'transform' on the string with 'tolower':" << endl;cout << """ << strLowerCaseCopy << """ << endl << endl;// Two sample vectors vector<int> numsInVec1{ 2017, 0, -1, 42, 10101, 25 };vector<int> numsInVec2 (numsInVec1.size(), -1);// A destination range for holding the result of additiondeque<int> sumInDeque (numsInVec1.size());transform (numsInVec1.cbegin(), // start of source d(),   // end of source range 1numsInVec2.cbegin(), // start of source range 2sumInDeque.begin(),  // start of destination rangeplus<int>());        // 头文件 function 中定义，将两个元素相加cout << "Result of 'transform' using binary function 'plus': " << endl;cout << "Index   Vector1 + Vector2 = Result (in Deque)" << endl;for (size_t index = 0; index < numsInVec1.size(); ++index) {cout << index << "    t " << numsInVec1 [index]   << "t+   ";cout << numsInVec2[index]  << " t  =    ";cout << sumInDeque[index] << endl;}return 0;
}

3.8 复制和删除操作

• STL 提供了三个重要的复制函数：copy()、copy_if() 和copy_backward()
  • copy 沿向前的方向将源范围的内容赋给目标范围
  • copy_if() 是 C++11 新增的，仅在指定的一元谓词返回 true 时才复制元素
  • copy_backward() 沿向后的方向将源范围的内容赋给目标范围
  • remove() 将容器中与指定值匹配的元素删除
  • remove_if() 使用一个一元谓词，并将容器中满足该谓词的元素删除

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>
using namespace std;template <typename T>
void DisplayContents(const T& container) {for (auto element = container.cbegin(); element != d(); ++element) {cout << *element << ' ';}   cout << "| Number of elements: " << container.size() << endl;
}int main() {list<int> numsInList{ 2017, 0, -1, 42, 10101, 25 };cout << "Source (list) contains:" << endl;DisplayContents(numsInList);// Initialize vector to hold 2x elements as the listvector <int> numsInVec (numsInList.size() * 2);auto lastElement = copy (numsInList.cbegin(),  // start d(),    // end source rangenumsInVec.begin());   // start dest range// copy odd numbers from list into vectorcopy_if (numsInList.cbegin(), d(), lastElement,[](int element){return ((element % 2) != 0);});cout << "Destination (vector) after copy and copy_if:" << endl;DisplayContents(numsInVec);// Remove all instances of '0', resize vector using erase()auto newEnd = remove (numsInVec.begin(), d(), 0);ase (newEnd, d());// Remove all odd numbers from the vector using remove_ifnewEnd = remove_if (numsInVec.begin(), d(),[](int element) {return ((element % 2) != 0);} );ase (newEnd , d());  // resizingcout << "Destination (vector) after remove, remove_if, erase:" << endl;DisplayContents(numsInVec);return 0;
}

3.9 替换值以及替换满足给定条件的元素

• replace() 根据比较运算符==的返回值来替换元素
• replace_if() 需要一个用户指定的一元谓词，对于要替换的每个值，该谓词都返回true

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;template <typename T>
void DisplayContents(const T& container) {for (auto element = container.cbegin(); element != d(); ++element)cout << *element << ' ';cout << "| Number of elements: " << container.size() << endl;
}int main () {vector<int> numsInVec (6);// fill first 3 elements with value 8, last 3 elements with 5fill (numsInVec.begin(), numsInVec.begin() + 3, 8);fill_n (numsInVec.begin () + 3, 3, 5);// std::random_shuffle 将容器内的值打乱random_shuffle (numsInVec.begin(), d());cout << "The initial contents of vector: " << endl;DisplayContents(numsInVec);cout << endl << "'std::replace' value 5 by 8" << endl;replace (numsInVec.begin(), d(), 5, 8);// 将所有偶数都替换为 -1 cout << "'std::replace_if' even values by -1" << endl;replace_if (numsInVec.begin (), d (),[](int element) {return ((element % 2) == 0); }, -1);cout << endl << "Vector after replacements:" << endl;DisplayContents(numsInVec);return 0;
}

3.10 排序、在有序集合中搜索以及删除重复元素

• 在实际的应用程序中，经常需要排序以及在有序范围内（出于性能考虑）进行搜索。经常需要对一组信息进行排序，为此可使用 sort()
• 在显示集合的内容前，需要删除重复的元素。要删除相邻的重复值，可使用 unique()
• 要进行快速查找，可使用 binary_search()，这种算法只能用于有序容器

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;template <typename T>
void DisplayContents(const T& container) {for (auto element = container.cbegin(); element != d(); ++element) {cout << *element << endl;}     
}int main () {vector<string> vecNames{"John", "jack", "sean", "Anna"};vecNames.push_back ("jack");cout << "The initial contents of the vector are: " << endl;DisplayContents(vecNames);cout << "The sorted vector contains names in the order:" << endl;sort (vecNames.begin(), d());DisplayContents(vecNames);cout << "Searching for "John" using 'binary_search':" << endl;bool elementFound = binary_search (vecNames.begin(), d(), "John");if (elementFound) {cout << "Result: "John" was found in the vector!" << endl;} else {cout << "Element not found " << endl;}   // 删除相邻的重复值auto newEnd = unique (vecNames.begin(), d());ase (newEnd, d());cout << "The contents of the vector after using 'unique':" << endl;DisplayContents(vecNames);return 0;
}

• 与 remove() 一样，unique() 也不调整容器的大小。它将元素前移，但不会减少元素总数。为避免容器末尾包含不想要或未知的值，务必在调用 unique() 后调用 vector::erase()，并将 unique() 返回的迭代器传递给它
• stable_sort() 确保排序后元素的相对顺序保持不变。为了确保相对顺序保持不变，将降低性能，这是一个需要考虑的因素，尤其在元素的相对顺序不重要时

3.11 将范围分区

• std::partition() 将输入范围分为两部分：一部分满足一元谓词；另一部分不满足
• 然而，std::partition() 不保证每个分区中元素的相对顺序不变。在相对顺序很重要，需要保持不变时，应使用 std::stable_partition()

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;bool IsEven (const int& num) {return ((num % 2) == 0);
}template <typename T>
void DisplayContents(const T& container) {for (auto element = container.cbegin(); element != d(); ++element) {cout << *element << ' ';}    cout << "| Number of elements: " << container.size() << endl;
}int main () {vector<int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };cout << "The initial contents: " << endl;DisplayContents(numsInVec);vector<int> vecCopy (numsInVec);cout << "The effect of using partition():" << endl;partition (numsInVec.begin(), d(), IsEven);DisplayContents(numsInVec);// stable_partition() 保持每个分区中元素的相对顺序不变，但速度更慢cout << "The effect of using stable_partition():" << endl;stable_partition (vecCopy.begin(), d(), IsEven);DisplayContents(vecCopy);return 0;
}

3.12 在有序集合中插入元素

• 将元素插入到有序集合中时，将其插入到正确位置很重要，可使用 lower_bound() 和 upper_bound() 等函数
• lower_bound() 和 upper_bound() 都返回一个迭代器，分别指向在不破坏现有顺序的情况下，元素可插入到有序范围内的最前位置和最后位置

#include <algorithm>
#include <list>
#include <string>
#include <iostream>
using namespace std;template <typename T>
void DisplayContents(const T& container) {for (auto element = container.cbegin(); element != d(); ++element) {cout << *element << endl;}      
}int main() {list<string> names{ "John", "Brad", "jack", "sean", "Anna" };cout << "Sorted contents of the list are: " << endl;names.sort();DisplayContents(names);cout << "Lowest index where "Brad" can be inserted is: ";auto minPos = lower_bound(names.begin(), d(), "Brad");cout << distance(names.begin(), minPos) << endl;cout << "The highest index where "Brad" can be inserted is: ";auto maxPos = upper_bound(names.begin(), d(), "Brad");cout << distance(names.begin(), maxPos) << endl;cout << endl;cout << "List after inserting Brad in sorted order: " << endl;names.insert(minPos, "Brad");DisplayContents(names);return 0;
}