C++ 面向对象程序设计 14万字总结笔记（八）-阿里云开发者社区

算法简介

您对STL算法的描述非常准确！

算法是函数模板，大多数在头文件中定义。STL提供了可以在各种容器中通用的算法，如查找、排序等。

这些算法通过迭代器来操作容器中的元素。许多算法可以对容器中的一个局部区间进行操作，因此需要两个参数：起始元素的迭代器和终止元素的后一个元素的迭代器。比如，排序算法和查找算法就是如此。

有些算法会返回一个迭代器作为结果。例如，find()算法用于在容器中查找一个元素，并返回指向该元素的迭代器。

不仅可以处理容器，STL算法也可以处理普通数组。由于数组也可以使用迭代器进行访问，因此可以将数组的指针视为其首元素的迭代器，并将指向（末尾+1）的指针视为终止元素的迭代器。

下面是一个示例代码，演示了如何使用STL算法在容器和数组中查找元素：

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 在容器中使用find算法查找元素
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "找到了元素3" << std::endl;
    } else {
        std::cout << "未找到元素3" << std::endl;
    }
    int arr[] = {1, 2, 3, 4, 5};
    // 在数组中使用find算法查找元素
    auto ptr = std::find(arr, arr + 5, 3);
    if (ptr != arr + 5) {
        std::cout << "找到了元素3" << std::endl;
    } else {
        std::cout << "未找到元素3" << std::endl;
    }
    return 0;
}

输出：

找到了元素3
找到了元素3

通过STL算法，我们可以高效地在容器和数组中执行各种操作，大大提高了代码的复用性和可读性。

vector和deque

vector和deque都是C++标准库中的容器，用于存储和管理元素。它们有一些共同点，也有一些不同之处。

相同点：

动态大小：vector和deque都是动态数组，可以在运行时根据需要动态调整容器的大小。
随机访问：两者都支持随机访问，可以通过索引直接访问容器中的元素。
迭代器支持：两者都提供迭代器来遍历容器中的元素。
支持尾部插入和删除：vector和deque都能够在尾部进行元素的插入和删除操作，并且具有接近常数时间的复杂度。

不同点：

内存分配方式：vector使用连续的内存块来存储元素，因此在内存中是紧密排列的。而deque使用多个小块的连续内存空间分别存储元素，这些小块之间通过指针链接起来。这使得deque能够在两端进行高效的插入和删除操作。
空间占用：由于vector使用连续的内存块，因此在同样数量的元素情况下，vector所占用的空间较小，而deque则相对较大，因为它需要维护额外的指针来连接不同的块。
中间插入和删除：vector对于中间位置的插入和删除操作比较低效，因为需要移动后续的元素；而deque在任何位置都能够高效地进行插入和删除操作。
迭代器失效：由于vector使用连续的内存块，因此添加或删除元素可能会导致已存在的迭代器失效。而deque由于使用了指针链接的方式，所以在除插入和删除操作发生在容器两端时，其他位置的迭代器仍然有效。

选择使用vector还是deque取决于具体的需求。如果需要频繁在容器的前部或中间位置进行插入和删除操作，并且不关心迭代器的失效问题，可以选择deque。如果对空间占用和迭代器的稳定性有更高的要求，或者只在尾部进行插入和删除操作，可以选择vector。

无论选择哪个容器，它们都提供了丰富的成员函数和算法支持，可以方便地进行元素的访问、插入、删除、排序等操作。

双向链表`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
• 1

这个示例展示了如何使用函数对象来自定义排序规则。这种灵活性使得函数对象在许多场景下非常有用，例如 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 算法对容器中的元素进行排序。它接受两个参数：待排序元素的范围的起始迭代器和结束迭代器。它会按照默认的升序排序规则对元素进行排序。排序后，容器中的元素将按照从小到大的顺序排列。

C++ 面向对象程序设计 14万字总结笔记（八）

算法简介

vector和deque

双向链表`list`

函数对象

`std::set` 和 `std::multiset`

map和multimap

容器适配器

STL中的算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景

C++ 面向对象程序设计 14万字总结笔记（八）

算法简介

vector和deque

双向链表list

函数对象

std::set 和 std::multiset

map和multimap

容器适配器

STL中的算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景

双向链表`list`

`std::set` 和 `std::multiset`