前言

STL容器一览

set和map如何降序构建

set和map如何插入自定义对象

multiset和multimap如何降序构建

multiset和multimap如何插入自定义对象

multi_系列如何equal_range

multiset

multimap

unorder_multiset

unorder_multimap

STL容器迭代器一览

迭代器性能一览

copy()

ostream_iterator

reverse_iterator

insert_iterator系列

for_each

set_union

remove_if

transform

list.remove

string.find

string.substr

算法组

tolower

toupper

next_permutation

unique

count_if

bitset：用于将整数转化为二进制

后续

前言

君子生非异也，善假与物也。本文着重于讲解在做leetcode和牛客题目时，会较为经常用到的容器、容器方法和通用算法，使我们在做题时，可以得心应手。在不断的学习方法中，我们实际上还能更进一步理解c++的各种编程思想。但是本文是基于你已经做了许多题目，已经有所实践的基础上。如果你连十道题都没做过，那你暂时无法体会本文所讲的内容或者说所讲内容的意义。

STL容器一览

set和map如何降序构建

set降序构建

#include <iostream>
#include <set>int main() {// 建立降序setstd::set<int, std::greater<int>> descendingSet;// 插入元素descendingSet.insert(5);descendingSet.insert(3);descendingSet.insert(7);descendingSet.insert(1);// 遍历输出for (int num : descendingSet) {std::cout << num << " ";}// 输出结果为：7 5 3 1return 0;
}

map降序构建

#include <iostream>
#include <map>int main() {// 建立降序mapstd::map<int, std::string, std::greater<int>> descendingMap;// 插入元素descendingMap.insert({10, "apple"});descendingMap.insert({5, "banana"});descendingMap.insert({15, "cherry"});// 遍历输出for (const auto& pair : descendingMap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 输出结果为：// 15: cherry// 10: apple// 5: bananareturn 0;
}

set和map如何插入自定义对象

set插入自定义对象

#include <iostream>
#include <set>
#include <string>class Person {
public:std::string name;int age;Person(const std::string& n, int a) : name(n), age(a) {}
};// 自定义比较函数对象
struct PersonComparator {bool operator()(const Person& a, const Person& b) const {if (a.age!= b.age) {return a.age < b.age;}return a.name < b.name;}
};int main() {std::set<Person, PersonComparator> people;people.insert(Person("Alice", 25));people.insert(Person("Bob", 20));people.insert(Person("Charlie", 25));for (const auto& person : people) {std::cout << "Name: " << person.name << ", Age: " << person.age << std::endl;}return 0;
}

map插入自定义对象

#include <iostream>
#include <map>
#include <string>class StudentID {
public:int id;std::string school;StudentID(int i, const std::string& s) : id(i), school(s) {}
};// 自定义比较函数对象
struct StudentIDComparator {bool operator()(const StudentID& a, const StudentID& b) const {if (a.id!= b.id) {return a.id < b.id;}return a.school < b.school;}
};int main() {std::map<StudentID, std::string, StudentIDComparator> studentNames;studentNames[StudentID(1, "SchoolA")] = "Alice";studentNames[StudentID(2, "SchoolB")] = "Bob";studentNames[StudentID(1, "SchoolC")] = "Charlie";for (const auto& pair : studentNames) {std::cout << "ID: " << pair.first.id << ", School: " << pair.first.school<< ", Name: " << pair.second << std::endl;}return 0;
}

multiset和multimap如何降序构建

与set和map如何降序构建一致

multiset和multimap如何插入自定义对象

与set和map如何插入自定义对象一致

multi_系列如何equal_range

equal_range返回一个std::pair，其中.first指向范围的起始位置，是一个迭代器，.second指向范围的结束位置（最后一个匹配元素的下一个位置），是一个迭代器。如果没有找到与键 k 相等的元素，.first 和 .second 都等于 end()，即超尾迭代器。

`multiset`

#include <iostream>
#include <set>int main() {std::multiset<int> numbers;numbers.insert(5);numbers.insert(3);numbers.insert(5);numbers.insert(7);numbers.insert(5);auto range = numbers.equal_range(5);for (auto it = range.first; it!= range.second; ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

multimap

#include <iostream>
#include <map>
#include <string>int main() {std::multimap<int, std::string> idNames;idNames.insert({1, "Alice"});idNames.insert({2, "Bob"});idNames.insert({1, "Charlie"});idNames.insert({3, "David"});auto range = idNames.equal_range(1);for (auto it = range.first; it!= range.second; ++it) {std::cout << "ID: " << it->first << ", Name: " << it->second << std::endl;}return 0;
}

unorder_multiset

#include <iostream>
#include <unordered_set>int main() {std::unordered_multiset<int> numbers;numbers.insert(5);numbers.insert(3);numbers.insert(5);numbers.insert(7);numbers.insert(5);auto range = numbers.equal_range(5);for (auto it = range.first; it != range.second; ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

unorder_multimap

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_multimap<int, std::string> idNames;idNames.insert({ 1, "Alice" });idNames.insert({ 2, "Bob" });idNames.insert({ 1, "Charlie" });idNames.insert({ 3, "David" });auto range = idNames.equal_range(1);for (auto it = range.first; it != range.second; ++it) {std::cout << "ID: " << it->first << ", Name: " << it->second << std::endl;}return 0;
}

STL容器迭代器一览

迭代器性能一览

copy()

OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
copy()函数将覆盖目标容器中已有的数据，同时目标容器必须足够大，以便能够容纳被复制的元素。

// copy algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::copy
#include <vector>       // std::vectorint main () {int myints[]={10,20,30,40,50,60,70};std::vector<int> myvector (7);std::copy ( myints, myints+7, myvector.begin() );std::cout << "myvector contains:";for (std::vector<int>::iterator it = myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

`ostream_iterator`

template< class T, class charT = char, class traits = std::char_traits<charT> >
ostream_iterator(std::ostream& os, const charT* delim);：构造一个 ostream_iterator，将元素输出到指定的输出流 os，每个元素后跟着分隔符 delim
std::ostream_iterator 是一个输出迭代器，只支持 ++（前置和后置）、* 和 = 操作符。
*out_iter++ = 15; //works like cout << 15 << " ";
copy(istream_iterator<int,char>(cin),istream_iterator<int,char>(),dice.begin());

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 使用 std::ostream_iterator 将 vector 元素输出到 std::cout，元素间以空格分隔std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));std::cout << std::endl;return 0;
}

reverse_iterator

rbegin和rend

前者返回一个指向超尾的反向迭代器
后者返回一个指向第一个元素的反向迭代器。
*rbegin = *(end-1)
*rend = *(begin -1)

insert_iterator系列

insert_iterator、back_insert_iterator和front_insert_iterator，这三个为插入迭代器。

back_insert_iterator将元素插入到容器尾部
front_insert_iterator将元素插入到容器的前端，不能用于vector这样头插效率极低的容器
insert_iterator将元素插入到insert_iterator构造函数的参数指定的位置前面
这三个插入迭代器都是输出容器概念的模型
back_insert_iterator<vector<int>>back_iter(dice);
front_insert_iterator<vector<int>>front_iter(dice);
insert_iterator<vector<int>>insert_iter(dice,dice.begin());
必须声明容器类型的原因是，迭代器必须使用合适的容器方法。back_insert_iterator的构造函数将假设传递给它的类型有一个push_back()方法。copy()是一个独立的函数，没有重新调整容器大小的权限。但前面的声明让back_iter能够使用方法vector<int>::push_back(),该方法有这样的权限。

for_each

Function for_each (InputIterator first, InputIterator last, Function fn）
for_each 本身不会修改数组元素，但它会对范围内的每个元素调用你提供的函数或函数对象，如果这个函数或函数对象对元素进行了修改操作，那么数组元素就会被修改。

#include <iostream>
#include <algorithm>
#include <array>// 定义一个函数，将传入的整数加倍
void doubleValue(int& num) {num *= 2;
}int main() {std::array<int, 5> arr = {1, 2, 3, 4, 5};// 使用 for_each 对数组每个元素应用 doubleValue 函数std::for_each(arr.begin(), arr.end(), doubleValue);// 输出修改后的数组for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

set_union

set_union 是 C++ 标准库 <algorithm> 头文件中的一个算法，用于构造两个有序范围的并集。这里的 “有序” 至关重要，意味着输入的两个范围必须是已经排好序的（通常是升序），否则结果将是未定义的。

示例 1：使用默认比较（<）

#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> v1 = {1, 2, 3, 5, 7};std::vector<int> v2 = {2, 4, 6, 7};std::vector<int> result(v1.size() + v2.size());auto it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());result.resize(std::distance(result.begin(), it));std::cout << "Union of the two vectors: ";for (int num : result) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

示例 2：使用自定义比较函数

#include <iostream>
#include <algorithm>
#include <vector>// 自定义比较函数，用于降序比较
bool greaterThan(int a, int b) {return a > b;
}int main() {std::vector<int> v1 = {7, 5, 3, 2, 1};std::vector<int> v2 = {7, 6, 4, 2};std::vector<int> result(v1.size() + v2.size());auto it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin(), greaterThan);result.resize(std::distance(result.begin(), it));std::cout << "Union of the two vectors in descending order: ";for (int num : result) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

示例3：复习front_insert_iterator

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>int main() {std::vector<int> v1 = { 1, 2, 3, 5, 7 };std::vector<int> v2 = { 2, 4, 6, 7 };std::vector<int> result;auto it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::insert_iterator<std::vector<int>>(result, result.begin()));//result.resize(std::distance(result.begin(), it));std::cout << "Union of the two vectors: ";for (int num : result) {std::cout << num << " ";}std::cout << std::endl;return 0;
}