标准模版库知识点总结 C++程序设计与算法笔记总结（八）北京大学郭炜（上）-阿里云开发者社区

标准模版库

https://blog.csdn.net/shaozheng0503/article/details/129101932?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168802585416800211563089%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=168802585416800211563089&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_blogfirst_rank_ecpm_v1~rank_v31_ecpm-2-129101932-null-null.268^v1koosearch&utm_term=stl&spm=1018.2226.3001.4450

标准模板库（Standard Template Library，STL）是C++的一个重要组成部分，提供了一套丰富的数据结构和算法容器。STL中的容器、算法和迭代器是三个主要的组件。

以下是STL中常见的几个组件：

容器（Containers）：STL提供了各种容器，包括向量（vector）、链表（list）、双向链表（deque）、集合（set）、映射（map）等。这些容器类似于数据结构，用于存储和管理数据。
算法（Algorithms）：STL提供了大量的算法，包括排序、搜索、合并、查找等操作。这些算法可以应用于各种不同的容器，使得对容器进行操作变得非常简单。
迭代器（Iterators）：迭代器是用于遍历容器中元素的一种通用方式。STL中的迭代器提供了一种统一的接口，使得可以以相同的方式访问不同类型的容器。
函数对象（Function Objects）：函数对象是可调用对象（如函数指针或重载了函数调用运算符的类对象），用于在算法中定义自定义的操作。
分配器（Allocators）：分配器用于管理内存的分配和释放，可以在STL的容器和算法中使用不同的分配器。

STL的设计目标是提供高效、灵活、通用的数据结构和算法，使得C++开发者可以更加便捷地进行编程。使用STL可以大大减少开发时间和代码复杂性，并且提供了可移植性和重用性。在C++开发中，使用STL可以极大地提高代码质量和开发效率。

泛型程序设计

C++ 语言的核心优势之一就是便于软件的重用

C++中有两个方面体现重用：

1.面向对象的思想：继承和多态，标准类库

2.泛型程序设计(generic programming) 的思想：模板机制，以及标准模板库 STL

简单地说就是使用模板的程序设计法。

将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。

标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。有了STL，不必再写大多的标准数据结构和算法，并且可获得非常高的性能。

STL中的基本的概念

容器：可容纳各种数据类型的通用数据结构,是类模板

迭代器：可用于依次存取容器中元素，类似于指针

算法：用来操作容器中的元素的函数模板

 sort()来对一个vector中的数据进行排序

 find()来搜索一个list中的对象

算法本身与他们操作的数据的类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。

int array[100];
该数组就是容器，而 int * 类型的指针变量就可以作为迭代器，sort算
法可以作用于该容器上，对其进行排序：
sort(array,array+70); //将前70个元素排序
迭代器

容器概述

没错，您提到的是STL中的一些常见容器和容器适配器。让我详细介绍一下它们：

顺序容器：

向量（vector）：向量是一个动态数组，能够在其末尾高效地添加和删除元素。它还支持随机访问，即可以通过索引直接访问元素。
双端队列（deque）：双端队列与向量类似，但也允许在头部进行高效插入和删除操作。
链表（list）：链表是一种双向链表，可以在任意位置进行高效的插入和删除操作，但无法通过索引直接访问元素。

关联容器：

集合（set）：集合是一个有序且不含重复元素的容器。它支持高效的搜索、插入和删除操作。
多重集合（multiset）：多重集合与集合类似，但允许容器中存在重复的元素。
映射（map）：映射是一种键-值对的容器，每个元素都有一个唯一的键。它支持按照键进行高效的搜索、插入和删除操作。
多重映射（multimap）：多重映射与映射类似，但允许容器中存在重复的键。

容器适配器：

栈（stack）：栈是一种后进先出（LIFO）的容器适配器。它基于双端队列或列表实现，只允许在顶部进行插入和删除操作。
队列（queue）：队列是一种先进先出（FIFO）的容器适配器。它基于双端队列或列表实现，允许在一端进行插入，在另一端进行删除。
优先队列（priority_queue）：优先队列是一种基于堆的容器适配器，它保证队列中具有最高优先级的元素始终位于队列前端。

这些容器和容器适配器提供了不同的数据组织方式和操作特性，可以根据需要选择最合适的容器来存储和管理数据。每个容器都有其独特的优势和适用场景，了解它们的特点和使用方法将对编程非常有帮助。

对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载 == 和 < 运算符。

迭代器

 用于指向顺序容器和关联容器中的元素

 迭代器用法和指针类似

 有const 和非 const两种

 通过迭代器可以读取它指向的元素

 通过非const迭代器还能修改其指向的元素

迭代器是STL中的一个重要概念，它用于遍历容器中的元素并访问它们。通过迭代器，我们可以以一种统一的方式对不同类型的容器进行操作，而不需要关心具体容器的实现细节。

STL中定义了多种类型的迭代器，每种迭代器具有不同的特性和功能。以下是STL中的常见迭代器分类：

输入迭代器（Input Iterator）：输入迭代器用于在容器中从前向后遍历元素，并支持读取元素的值。输入迭代器只能单向移动，不支持修改容器中的元素。
输出迭代器（Output Iterator）：输出迭代器用于在容器中从前向后遍历元素，并支持修改元素的值。输出迭代器只能单向移动，不支持读取元素的值。
正向迭代器（Forward Iterator）：正向迭代器可以像输入迭代器和输出迭代器一样进行单向遍历和修改。与输入迭代器和输出迭代器不同的是，正向迭代器支持多次遍历，即可以对同一个容器进行多次迭代。
双向迭代器（Bidirectional Iterator）：双向迭代器比正向迭代器更强大，它支持从前向后和从后向前遍历容器中的元素。双向迭代器可以进行递增和递减操作。
随机访问迭代器（Random Access Iterator）：随机访问迭代器是最强大的迭代器类型，它具有所有其他迭代器的功能，并且支持随机访问容器中的元素。随机访问迭代器可以像指针一样进行算术运算，使得我们可以在常数时间内访问容器中的任意元素。

使用迭代器，我们可以通过以下方式遍历容器中的元素：

for (auto it = container.begin(); it != container.end(); ++it) {
    // 访问迭代器指向的元素
    // *it 可以获取当前迭代器指向的元素
}

需要注意的是，不同类型的容器可能提供不同类型的迭代器。例如，向量和双端队列提供随机访问迭代器，而链表只提供双向迭代器。在编写代码时，我们需要根据具体容器的特性选择合适的迭代器类型来进行操作。

迭代器是STL的核心概念之一，掌握了迭代器的使用方法，可以更加灵活和高效地操作容器中的元素。

当然，继续回答您关于迭代器的问题。

在STL中，除了常见的迭代器类型外，还有一些其他类型的迭代器和相关概念：

反向迭代器（Reverse Iterator）：反向迭代器是一种特殊的迭代器，它可以逆序遍历容器中的元素。通过rbegin()和rend()成员函数可以获取反向迭代器的起始和结束位置。

for (auto rit = container.rbegin(); rit != container.rend(); ++rit) {
    // 访问反向迭代器指向的元素
}

常量迭代器（Const Iterator）：常量迭代器用于对容器中的元素进行只读访问，不允许修改元素的值。通过cbegin()和cend()成员函数可以获取常量迭代器的起始和结束位置。

for (auto cit = container.cbegin(); cit != container.cend(); ++cit) {
    // 访问常量迭代器指向的元素，只允许进行读取操作
}

插入迭代器（Insert Iterator）：插入迭代器是一种特殊的迭代器，它可以在容器中插入新的元素。插入迭代器是通过std::inserter()函数创建的。

std::vector<int> vec;
std::fill_n(std::inserter(vec, vec.begin()), 5, 0);
// 在vec的开始位置插入5个0

流迭代器（Stream Iterator）：流迭代器用于将容器中的元素通过输入输出流进行读写。通过std::istream_iterator和std::ostream_iterator可以创建输入和输出流迭代器。

// 从标准输入流中读取整数，并存储到容器中
std::vector<int> vec(std::istream_iterator<int>(std::cin), std::istream_iterator<int>());
// 将容器中的元素通过空格分隔输出到标准输出流
std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));

这些特殊类型的迭代器扩展了STL对容器的操作能力，使得我们可以更灵活地使用迭代器进行元素的遍历、修改和插入等操作。根据实际需求，选择合适的迭代器类型能够提高代码的可读性和效率。

迭代器是用于指向顺序容器（如向量、列表等）和关联容器（如映射、集合等）中的元素的对象。它的用法与指针非常相似，可以通过迭代器访问和操作容器中的元素。

迭代器分为const迭代器和非const迭代器两种类型。const迭代器只能读取其指向的元素，而非const迭代器除了读取，还可以修改其指向的元素。

使用迭代器可以通过以下方式读取和修改元素：

读取元素：通过解引用操作符*来获取迭代器指向的元素的值。例如*it获取迭代器it指向的元素。
修改元素：通过解引用操作符*获取元素的引用，然后对引用进行修改。例如*it = value将迭代器it指向的元素设置为value。

下面是一个使用迭代器进行读取和修改的示例代码：

#include <iostream>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 使用非const迭代器读取和修改元素
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        // 读取元素的值
        int value = *it;
        std::cout << value << " ";
        // 修改元素的值
        *it = value * 2;
    }
    std::cout << std::endl;
    // 输出修改后的元素
    for (const auto& num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出：

1 2 3 4 5
2 4 6 8 10

通过迭代器，我们可以灵活地对容器中的元素进行读取和修改，使得我们能够更方便地操作容器中的数据。

算法简介

您对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。

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

标准模版库知识点总结 C++程序设计与算法笔记总结（八）北京大学郭炜（上）