双向链表list
双向链表（list）是C++标准库中的一种容器，与vector和deque相比，它有一些独特的特点和用途。
以下是关于双向链表list的一些特点：
- 结构：
list是由一系列节点构成的，每个节点都包含一个值和指向前一个节点和后一个节点的指针。这种结构使得插入和删除操作在任意位置上都具有常数时间复杂度。 - 插入和删除：由于双向链表的节点指针，
list在任意位置进行插入和删除操作都非常高效，不会涉及元素的移动和内存重新分配。 - 访问：与
vector和deque不同，list不支持通过随机索引进行快速访问，因为它没有连续的内存块。要访问list中的元素，需要遍历链表。 - 内存占用：由于每个节点都需要额外的指针来连接前后节点，所以相对于
vector和deque，list在空间上的开销会更大。 - 迭代器稳定性：与
vector不同，list的插入和删除操作不会使迭代器失效，因为节点的指针不会改变。但是，当对于正在被删除的节点进行解引用时，迭代器会失效。
由于上述特点，list在某些场景下具有一定的优势：
- 频繁的插入和删除操作：如果需要频繁地在容器的任意位置进行插入和删除操作，并且对于随机访问性能要求不高，那么
list是一个很好的选择。 - 迭代器稳定性要求高：当需要在插入和删除操作后仍然保持对元素的有效引用时，
list的迭代器稳定性是一个重要的考虑因素。
需要注意的是，由于list在访问元素时需要遍历链表，所以如果需要频繁地进行随机访问操作，或者对存储空间占用有较高要求，可能会选择使用vector或deque。
当然，下面是一个使用list的简单代码示例，演示了如何插入、删除和遍历链表中的元素：
#include <iostream> #include <list> int main() { std::list<int> myList; // 创建一个int类型的双向链表 // 在链表尾部插入元素 myList.push_back(10); myList.push_back(20); myList.push_back(30); // 在链表头部插入元素 myList.push_front(5); // 遍历输出链表中的元素 std::cout << "Elements in the list: "; for (const auto& element : myList) { std::cout << element << " "; } std::cout << std::endl; // 删除链表中的特定元素 myList.remove(20); // 遍历输出删除后的链表元素 std::cout << "Elements after removing 20: "; for (const auto& element : myList) { std::cout << element << " "; } std::cout << std::endl; return 0; }
在上面的示例中，首先我们包含了<iostream>和<list>头文件来使用list容器。然后，我们创建了一个名为myList的list对象，并使用push_back()和push_front()函数在链表中插入一些元素。
接着，我们使用一个范围-based for 循环来遍历并输出链表中的元素。注意，list是一个双向链表，所以我们可以使用前向迭代器（const auto& element）来访问元素。
然后，我们使用remove()函数删除了链表中的特定元素（此处为20）。
最后，我们再次遍历并输出删除后的链表元素。
好的，我将为您介绍一些list的具体操作。
- 插入元素：
push_back(value)：在链表尾部插入一个元素。push_front(value)：在链表头部插入一个元素。insert(position, value)：在指定位置插入一个元素。
- 删除元素：
pop_back()：删除链表尾部的元素。pop_front()：删除链表头部的元素。erase(position)：删除指定位置的元素。remove(value)：删除链表中所有与给定值相等的元素。
- 访问元素：
front()：返回链表头部的元素的引用。back()：返回链表尾部的元素的引用。
- 遍历元素：
- 使用循环或范围-based for 循环来遍历链表中的元素，使用迭代器访问每个元素。
- 清空容器：
clear()：清空整个链表，删除所有元素。
- 获取大小：
size()：返回链表中元素的个数。empty()：检查链表是否为空。
需要注意的是，由于list是一个双向链表，对于插入和删除操作，它们在任意位置上都具有常数时间复杂度。而对于查找元素，由于访问是基于遍历的，所以时间复杂度为线性。
函数对象
在C++中，函数对象（Function Object），也称为仿函数（Functor），是一种重载了函数调用运算符 operator() 的对象。函数对象可以像普通函数一样被调用，并且可以具有自己的状态和成员变量。
函数对象的主要优势是它们可以像普通函数一样使用，并且可以通过在类中定义函数调用运算符 operator() 来自定义函数的行为。这使得函数对象非常灵活，可以根据需要进行定制。
下面是一个简单的示例，展示了如何创建和使用函数对象：
#include <iostream> // 定义一个函数对象类 class MultiplyBy { public: MultiplyBy(int factor) : factor_(factor) { } int operator()(int value) { return value * factor_; } private: int factor_; }; int main() { MultiplyBy multiplyByTwo(2); // 使用函数对象进行计算 int result = multiplyByTwo(5); // 等同于 multiplyByTwo.operator()(5) std::cout << "Result: " << result << std::endl; // 输出结果: 10 return 0; }
在上面的示例中，我们定义了一个名为 MultiplyBy 的函数对象类。它接受一个整数作为构造函数的参数，并将其存储为类的成员变量 factor_。然后，我们重载了函数调用运算符 operator()，将输入的值乘以 factor_ 并返回结果。
在 main 函数中，我们创建了一个名为 multiplyByTwo 的函数对象，并将构造函数参数设置为 2。然后，我们使用函数对象进行计算，将 5 作为参数传递给它，得到结果 10。
函数对象非常有用，在许多情况下可以代替普通函数或函数指针，例如在标准库中的算法中使用自定义的操作。
当然，这里是一个更完整的代码示例，演示了使用函数对象来自定义排序规则：
#include <iostream> #include <algorithm> #include <vector> // 定义一个函数对象类 class CompareLength { public: bool operator()(const std::string& str1, const std::string& str2) { return str1.length() < str2.length(); } }; int main() { std::vector<std::string> words = {"apple", "banana", "cherry", "date"}; // 使用函数对象进行排序 CompareLength compare; std::sort(words.begin(), words.end(), compare); // 输出排序结果 for (const auto& word : words) { std::cout << word << " "; } std::cout << std::endl; return 0; }
在上面的示例中，我们定义了一个名为 CompareLength 的函数对象类。它重载了函数调用运算符 operator()，并接受两个字符串作为参数。在函数对象内部，我们比较两个字符串的长度，并返回比较结果。
在 main 函数中，我们创建了一个 std::vector<std::string> 类型的 words 容器，其中包含一些单词。然后，我们创建了一个名为 compare 的函数对象实例。
使用 std::sort 算法和 compare 函数对象对 words 进行排序。该算法会根据我们定义的排序规则，即字符串长度进行排序。
最后，我们使用循环输出排序后的结果。
执行上述代码，输出将是按字符串长度排序的结果：
date apple banana cherry
这个示例展示了如何使用函数对象来自定义排序规则。这种灵活性使得函数对象在许多场景下非常有用，例如 STL 的算法和容器的自定义操作。
std::set 和 std::multiset
std::set 和 std::multiset 都是 C++ 标准库中的关联容器，用于存储元素，并根据元素的值进行自动排序。它们之间的主要区别在于元素的唯一性。
std::set：是一个集合容器，其中每个元素的值都是唯一的。即使插入重复的元素，也只会保留一个。它使用红黑树数据结构实现，具有对数时间复杂度的插入、查找和删除操作。std::multiset：是一个多重集合容器，可以存储多个相同值的元素。它允许插入重复的元素，并根据值的顺序进行排序。同样，它使用红黑树数据结构实现，具有对数时间复杂度的插入、查找和删除操作。
以下是一个示例代码，展示了如何使用 std::set 和 std::multiset：
#include <iostream> #include <set> int main() { std::set<int> setOfNumbers; setOfNumbers.insert(10); setOfNumbers.insert(30); setOfNumbers.insert(20); setOfNumbers.insert(40); std::cout << "std::set:" << std::endl; for (const auto& num : setOfNumbers) { std::cout << num << " "; } std::cout << std::endl; std::multiset<int> multisetOfNumbers; multisetOfNumbers.insert(10); multisetOfNumbers.insert(30); multisetOfNumbers.insert(20); multisetOfNumbers.insert(30); std::cout << "std::multiset:" << std::endl; for (const auto& num : multisetOfNumbers) { std::cout << num << " "; } std::cout << std::endl; return 0; }
在上面的示例中，我们首先创建了一个 std::set<int> 类型的容器 setOfNumbers，并插入了一些整数。由于 std::set 中的元素是唯一的，重复插入的元素只会保留一个。然后，我们使用循环打印出集合中的元素。
接下来，我们创建了一个 std::multiset<int> 类型的容器 multisetOfNumbers，并插入了一些整数。由于 std::multiset 允许存储重复元素，我们插入了两个值为 30 的元素。然后，同样使用循环打印出多重集合中的元素。
执行上述代码，输出将是：
std::set: 10 20 30 40 std::multiset: 10 20 30 30
这个示例展示了 std::set 和 std::multiset 的基本用法和区别。根据您的需求，可以选择适合的容器类型。
map和multimap
std::map 和 std::multimap 是 C++ 标准库中的关联容器，用于存储键值对，并根据键的值进行自动排序。它们之间的主要区别在于键的唯一性。
std::map：是一个映射容器，其中每个键的值都是唯一的。即使插入具有相同键的多个元素，也只会保留一个，并且后续的插入将覆盖先前的值。它使用红黑树数据结构实现，具有对数时间复杂度的插入、查找和删除操作。std::multimap：是一个多重映射容器，可以存储具有相同键的多个元素。它允许插入具有相同键的多个元素，并根据键的顺序进行排序。同样，它使用红黑树数据结构实现，具有对数时间复杂度的插入、查找和删除操作。
以下是一个示例代码，展示了如何使用 std::map 和 std::multimap：
#include <iostream> #include <map> int main() { std::map<int, std::string> mapOfNumbers; mapOfNumbers.insert(std::make_pair(3, "Three")); mapOfNumbers.insert(std::make_pair(1, "One")); mapOfNumbers.insert(std::make_pair(2, "Two")); mapOfNumbers.insert(std::make_pair(4, "Four")); std::cout << "std::map:" << std::endl; for (const auto& pair : mapOfNumbers) { std::cout << pair.first << ": " << pair.second << std::endl; } std::multimap<int, std::string> multimapOfNumbers; multimapOfNumbers.insert(std::make_pair(3, "Three")); multimapOfNumbers.insert(std::make_pair(1, "One")); multimapOfNumbers.insert(std::make_pair(2, "Two")); multimapOfNumbers.insert(std::make_pair(3, "Another Three")); std::cout << "std::multimap:" << std::endl; for (const auto& pair : multimapOfNumbers) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }
在上面的示例中，我们首先创建了一个 std::map<int, std::string> 类型的容器 mapOfNumbers，并插入了一些键值对。由于 std::map 中的键是唯一的，重复插入具有相同键的元素将覆盖先前的值。然后，我们使用循环打印出映射中的键值对。
接下来，我们创建了一个 std::multimap<int, std::string> 类型的容器 multimapOfNumbers，并插入了一些键值对。由于 std::multimap 允许存储具有相同键的多个元素，我们插入了两个值为 3 的键值对。然后，同样使用循环打印出多重映射中的键值对。
执行上述代码，输出将是：
std::map: 1: One 2: Two 3: Three 4: Four std::multimap: 1: One 2: Two 3: Three 3: Another Three
这个示例展示了 std::map 和 std::multimap 的基本用法和区别。根据您的需求，可以选择适合的容器类型。
容器适配器
容器适配器（Container Adapters）是 C++ 标准库中提供的特殊容器，它们基于现有的容器类型，提供了不同的接口和功能。常见的容器适配器包括栈（stack）、队列（queue）和优先队列（priority_queue）。
这些容器适配器的底层实现可以使用各种不同类型的容器，例如 std::deque、std::list 或 std::vector。下面我们来详细介绍每个容器适配器的特点和用法：
- 栈（stack）：
- 使用 LIFO（后进先出）的方式操作元素。
- 可以使用
std::deque、std::list或std::vector作为底层容器。 - 提供
push()、pop()、top()等操作函数。 - 示例代码：
#include <iostream> #include <stack> int main() { std::stack<int> stackOfNumbers; stackOfNumbers.push(1); stackOfNumbers.push(2); stackOfNumbers.push(3); while (!stackOfNumbers.empty()) { std::cout << stackOfNumbers.top() << " "; stackOfNumbers.pop(); } return 0; }
- 队列（queue）：
- 使用 FIFO（先进先出）的方式操作元素。
- 可以使用
std::deque或std::list作为底层容器。 - 提供
push()、pop()、front()、back()等操作函数。 - 示例代码：
#include <iostream> #include <queue> int main() { std::queue<int> queueOfNumbers; queueOfNumbers.push(1); queueOfNumbers.push(2); queueOfNumbers.push(3); while (!queueOfNumbers.empty()) { std::cout << queueOfNumbers.front() << " "; queueOfNumbers.pop(); } return 0; }
- 优先队列（priority_queue）：
- 类似于队列，但元素按照一定的优先级进行排序。
- 默认情况下，使用
<运算符进行比较，也可以自定义比较函数。 - 可以使用
std::vector或std::deque作为底层容器。 - 提供
push()、pop()、top()等操作函数。 - 示例代码：
#include <iostream> #include <queue> int main() { std::priority_queue<int> pqOfNumbers; pqOfNumbers.push(3); pqOfNumbers.push(1); pqOfNumbers.push(2); while (!pqOfNumbers.empty()) { std::cout << pqOfNumbers.top() << " "; pqOfNumbers.pop(); } return 0; }
这些容器适配器提供了特定的接口和行为，方便我们在特定场景下使用。您可以根据需要选择适合的容器适配器来实现相应的功能。
STL中的算法
STL中的算法大致可以分为以下七类：
1)不变序列算法
2)变值算法
3)删除算法
4)变序算法
5)排序算法
6)有序区间算法
7)数值算法
当然，我可以为您提供一些代码示例来演示不同类别的 STL 算法。下面是一些简单的示例代码：
- 不变序列算法（Non-modifying Sequence Algorithms）：
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> numbers = {1, 2, 3, 4, 5}; // 使用 std::find 查找元素 auto it = std::find(numbers.begin(), numbers.end(), 3); if (it != numbers.end()) { std::cout << "Element found at index: " << std::distance(numbers.begin(), it) << std::endl; } else { std::cout << "Element not found" << std::endl; } return 0; }
- 变值算法（Mutating Algorithms）：
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> numbers = {1, 2, 3, 4, 5}; // 使用 std::fill 将容器中的元素填充为指定值 std::fill(numbers.begin(), numbers.end(), 0); // 输出变化后的容器 for (const auto& num : numbers) { std::cout << num << " "; } std::cout << std::endl; return 0; }
- 删除算法（Removing Algorithms）：
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> numbers = {1, 2, 3, 4, 5}; // 使用 std::remove_if 删除满足条件的元素 numbers.erase(std::remove_if(numbers.begin(), numbers.end(), [](int num) { return num % 2 == 0; // 删除偶数 }), numbers.end()); // 输出变化后的容器 for (const auto& num : numbers) { std::cout << num << " "; } std::cout << std::endl; return 0; }
- 变序算法（Partitioning Algorithms）：
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> numbers = {1, 2, 3, 4, 5}; // 使用 std::partition 将容器中的元素根据奇偶分为两部分 auto partitionIt = std::partition(numbers.begin(), numbers.end(), [](int num) { return num % 2 != 0; // 奇数在前，偶数在后 }); // 输出变化后的容器 for (const auto& num : numbers) { std::cout << num << " "; } std::cout << std::endl; return 0; }
- 排序算法（Sorting Algorithms）：
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> numbers = {5, 2, 4, 1, 3}; // 使用 std::sort 对容器进行排序 std::sort(numbers.begin(), numbers.end()); // 输出变化后的容器 for (const auto& num : numbers) { std::cout << num << " "; } std::cout << std::endl; return 0; }
这只是一小部分示例代码，您可以根据需要选择合适的算法并结合具体的容器类型来使用。
当然，我可以为您进一步讲解每个示例代码的作用和使用方法。
- 不变序列算法（Non-modifying Sequence Algorithms）：
这个示例使用了std::find算法来在容器中查找指定元素。它接受三个参数：待查找的范围的起始迭代器、结束迭代器和要查找的值。如果找到了该值，则返回指向该元素的迭代器；如果没有找到，则返回结束迭代器。 - 变值算法（Mutating Algorithms）：
这个示例使用了std::fill算法来将整个容器中的元素都填充为指定的值。它接受三个参数：待填充的范围的起始迭代器、结束迭代器和要填充的值。 - 删除算法（Removing Algorithms）：
这个示例使用了std::remove_if算法来删除容器中满足特定条件的元素。它接受三个参数：待删除元素的范围的起始迭代器、结束迭代器和一个可调用对象（函数或函数对象），用于判断哪些元素应该被删除。这个算法首先会将满足条件的元素移动到容器末尾，然后返回一个指向新的逻辑末尾的迭代器。最后通过使用容器的erase成员函数将这些元素从容器中移除。 - 变序算法（Partitioning Algorithms）：
这个示例使用了std::partition算法来根据指定的条件将容器中的元素进行变序。它接受三个参数：待变序元素的范围的起始迭代器、结束迭代器和一个可调用对象，用于判断哪些元素应该在前面，哪些应该在后面。这个算法会重新排列容器中的元素，使得满足条件的元素在前面，不满足条件的元素在后面。返回值是一个迭代器，指向第一个不满足条件的元素。 - 排序算法（Sorting Algorithms）：
这个示例使用了std::sort算法对容器中的元素进行排序。它接受两个参数：待排序元素的范围的起始迭代器和结束迭代器。它会按照默认的升序排序规则对元素进行排序。排序后，容器中的元素将按照从小到大的顺序排列。
