STL

comeweijjd枫长LH...大约 20 分钟

1. 什么是STL？

C++的STL（Standard Template Library，标准模板库）是C++编程语言中的一个功能强大且广泛使用的库，它提供了一系列通用的模板类和函数，可以帮助程序员更高效地处理各种数据结构和算法问题。STL主要包含以下几个组件：

容器（Containers）：容器是用来存储和管理数据的数据结构，例如向量（vector）、列表（list）、队列（queue）、栈（stack）、集合（set）和映射（map）等。
迭代器（Iterators）：迭代器是一种类似于指针的对象，可以用来遍历容器中的元素。迭代器为容器中的数据提供了统一的访问接口，使得算法可以与容器无缝地协同工作。
算法（Algorithms）：STL提供了许多通用的算法，如排序、查找、合并等，这些算法可以直接应用于容器和迭代器。
函数对象（Function Objects）：函数对象是实现了函数调用操作符（operator()）的类的对象。它们通常用作算法的自定义操作，使得算法可以具有更高的灵活性和可扩展性。函数对象有时被称为“仿函数”（functors）。STL还提供了一些预定义的函数对象，例如less、greater、plus等，它们可以用于算法中的比较和运算操作。
适配器（Adapters）：适配器是一种特殊的容器或函数对象，它们可以修改或扩展其他容器或函数对象的行为。例如，队列（queue）和栈（stack）就是容器适配器，它们分别基于deque和vector容器实现。函数适配器包括bind、mem_fn等，可以用来组合和修改函数对象。
分配器（Allocators）：分配器是一种管理内存分配和释放的机制，它们可以用于自定义容器的内存管理策略。STL中默认使用的分配器是std::allocator，但用户可以根据需要提供自定义的分配器。

2. vector与list的区别与应用？

vector和list是C++ STL中两种常用的序列容器，它们用于存储和管理线性数据，但在底层实现、性能特点和适用场景上有一些区别。

底层实现

vector：vector是基于动态数组实现的，内存空间是连续的。当vector需要扩容时，它会分配一块更大的内存空间，将原有的数据拷贝到新的空间，并释放原有的内存。
list：list是基于双向链表实现的，内存空间是非连续的。每个元素都是一个节点，节点之间通过指针相互连接。

性能

vector
- 访问元素：由于内存连续，vector支持随机访问，可以使用下标直接访问任意元素，时间复杂度为O(1)。
- 插入和删除：在vector的末尾插入和删除元素非常高效，时间复杂度为O(1)；但在中间或开头插入和删除元素需要移动后面的元素，时间复杂度为O(n)。
- 内存使用：vector可能会预留一些额外的内存空间用于扩容，因此在某些情况下可能会浪费一些内存。但由于内存连续，vector通常对缓存友好，有更好的空间局部性。
list
- 访问元素：list不支持随机访问，访问任意元素需要从头节点开始遍历链表，时间复杂度为O(n)。
- 插入和删除：在list的任意位置插入和删除元素非常高效，只需要修改相邻节点的指针，时间复杂度为O(1)。但需要注意的是，要定位到插入或删除的位置仍然需要O(n)的时间。

应用场景

vector：当需要频繁访问元素，且插入和删除操作主要发生在容器末尾时，vector是一个好的选择。由于其连续内存特性，vector通常更适用于需要高缓存友好性的场景。
list：当需要频繁在容器中间或开头进行插入和删除操作，且对随机访问性能要求不高时，list是一个更合适的选择。list也适用于那些不支持或不方便进行内存移动的数据类型的场景，因为list在插入和删除时不会引起元素的内存移动。

3. STL vector的实现，删除其中的元素，迭代器如何变化？为什么是两倍扩容？释放空间？

STL vector的实现： vector是基于动态数组实现的，其内存空间是连续的。vector有三个指针：指向数据开始的位置（begin），指向数据结束的下一个位置（end）和指向已分配内存空间结束的下一个位置（capacity）。

删除元素及迭代器的变化：当从vector中删除元素时（如使用erase方法），被删除元素之后的所有元素会向前移动一位以填补空位，因此迭代器会受到影响。删除元素后，原来指向被删除元素的迭代器以及指向其后元素的迭代器都会失效。为了确保迭代器的有效性，通常在删除元素后重新获取迭代器。

为什么是两倍扩容： vector在需要扩容时通常会将容量增加到原来的两倍。这是因为两倍扩容可以在动态数组的插入操作上实现均摊O(1)的时间复杂度（amortized O(1)）。当每次扩容为原来的两倍时，元素移动的次数和总时间开销相对较低，从而在实际应用中表现出较好的性能。两倍扩容是一种折衷方案，既能平衡内存使用效率，又能在大多数场景下保持良好的性能。

释放空间： vector本身不会在元素删除时自动收缩内存。如果你希望在删除元素后释放多余的空间，可以使用“swap trick”技巧。创建一个新的临时vector，用它来交换（swap）原vector的内容，这样原vector的内存空间就会收缩到实际元素数量所需的大小。这个方法的示例如下：

std::vector<int> v(100);
// ... 添加/删除元素 ...

// 使用swap trick释放多余的空间
std::vector<int>(v).swap(v);

创建了一个新的临时vector对象，并使用原vector的内容进行构造。然后通过swap方法，将原vector的内容与新vector的内容交换。新vector在离开作用域时会自动销毁，从而释放多余的内存空间。请注意，此操作可能导致迭代器、指针和引用失效，因此在执行此操作后，需要确保更新这些指向vector的对象。

4. set与unordered_set的区别？

set 和 hash_set 都是用于存储不重复元素的容器，但它们之间有一些关键区别。set 是一个基于平衡二叉搜索树实现的有序容器，而 unordered_set是一个基于哈希表实现的无序容器。下面列出了它们之间的主要区别：

底层数据结构

set：基于平衡二叉搜索树（通常是红黑树）实现。元素在容器中按照一定的顺序排列（通过比较运算符 < 或自定义比较函数）。
unordered_set：基于哈希表实现。元素在容器中的位置由其哈希值决定，因此元素在容器中的顺序是无序的。

时间复杂度

set：插入、删除和查找操作的平均时间复杂度为 O(log n)，其中 n 为元素个数。
unordered_set：插入、删除和查找操作的平均时间复杂度为 O(1)，但在最坏情况下（所有元素都在同一个哈希桶中）时间复杂度可能退化为 O(n)。

空间复杂度

set：空间复杂度相对较低，因为它基于平衡二叉搜索树。
unordered_set：空间复杂度相对较高，因为哈希表需要分配额外的空间来存储桶和处理冲突。

元素顺序

set：元素在容器中按照排序顺序存储，因此遍历 set 时，元素将按照顺序输出。
unordered_set：元素在容器中是无序的。遍历时，元素的输出顺序将是随机的。

自定义哈希函数和比较函数

set：需要自定义比较函数（通常为 operator< 或 std::less 的自定义版本），以便在平衡二叉搜索树中对元素进行排序。
unordered_set：需要自定义哈希函数（用于计算元素的哈希值）和相等函数（用于比较元素是否相等）。

适用场景

set：当需要一个有序容器时，或者当对元素的插入、删除和查找时间复杂度要求为对数级别时，使用 set 是一个不错的选择。
unordered_set：当不需要关心元素顺序，且需要更快速的插入、删除和查找操作时，使用 hash_set 或 unordered_set 更为合适。

5. unordered_map与map的区别？

map 和 unordered_map都是 C++ 中常用的关联容器，它们允许使用键（key）来存储和检索值（value）。尽管它们有相似的功能，但它们的底层实现和性能特点有很大的不同。

底层数据结构

map：基于平衡二叉搜索树（通常是红黑树）实现。键值对按照键的顺序（通过比较运算符 < 或自定义比较函数）排列。
unordered_map：基于哈希表实现。键值对在容器中的位置由键的哈希值决定，因此键值对在容器中的顺序是无序的。

时间复杂度

map：插入、删除和查找操作的平均时间复杂度为 O(log n)，其中 n 为元素个数。
unordered_map：插入、删除和查找操作的平均时间复杂度为 O(1)，但在最坏情况下（所有元素都在同一个哈希桶中）时间复杂度可能退化为 O(n)。

空间复杂度

map：空间复杂度相对较低，因为它基于平衡二叉搜索树。
unordered_map：空间复杂度相对较高，因为哈希表需要分配额外的空间来存储桶和处理冲突。

元素顺序

map：键值对按照键的顺序排列，因此遍历 map 时，键值对按照键的顺序输出。
unordered_map：键值对在容器中是无序的。遍历时，键值对的输出顺序将是随机的。

自定义哈希函数和比较函数

map：需要自定义比较函数（通常为 operator< 或 std::less 的自定义版本），以便在平衡二叉搜索树中对键进行排序。
unordered_map：需要自定义哈希函数（用于计算键的哈希值）和相等函数（用于比较键是否相等）。

适用场景

map：当需要一个有序容器时，或者当对键值对的插入、删除和查找时间复杂度要求为对数级别时，使用 map 是一个不错的选择。
unordered_map：当不需要关心键值对顺序，且需要更快速的插入、删除和查找操作时，使用 unordered_map 更为合适。

6. map、set是怎么实现的，红黑树是怎么能够同时实现这两种容器？为什么使用红黑树？

map 和 set 都是基于红黑树实现的关联容器。红黑树是一种自平衡的二叉搜索树，它通过在每个节点上添加一个颜色属性（红色或黑色）来确保树保持大致平衡。红黑树的平衡特性可以保证插入、删除和查找操作具有较好的时间复杂度（O(log n)）。

红黑树如何实现 map 和 set：

实现 set：红黑树中的每个节点存储一个键，节点之间通过比较键的大小进行排序。红黑树的节点之间的顺序关系满足二叉搜索树的特性。因此，通过将元素作为红黑树的键，我们可以实现一个 set 容器。
实现 map：为了实现 map 容器，需要同时存储键和值。在红黑树中，每个节点除了存储键之外，还可以存储一个对应的值。通常将键和值封装成一个 pair 对象。这样，红黑树的
节点就包含了键值对，并且键之间的顺序关系依然满足二叉搜索树的特性。因此，通过将键值对作为红黑树的节点，我们可以实现一个 map 容器。

为什么使用红黑树？

时间复杂度：红黑树的自平衡特性保证了树的高度大致保持在 O(log n)，这意味着插入、删除和查找操作的时间复杂度都是 O(log n)。相比其他的数据结构（如普通的二叉搜索树），红黑树在最坏情况下仍然具有较好的性能。
内存效率：红黑树只需要在每个节点上存储一个额外的颜色属性，因此与其他自平衡二叉搜索树（如 AVL 树）相比，红黑树具有较好的内存效率。
灵活性：红黑树可以用于实现多种关联容器，例如 set、multiset、map和multimap。同时，红黑树支持范围查询、查找前驱和后继等高级操作，这使得它成为实现这些容器的理想选择。
良好的实时性：红黑树的插入、删除和调整操作都具有较好的实时性，因为它们的时间复杂度可以保证在 O(log n)。相比其他数据结构，红黑树能够更好地满足实时性的需求。

7. 如何在共享内存上使用stl标准库？

在C++中，在共享内存上使用STL标准库涉及到一些挑战，因为STL容器通常在堆上分配内存，而不是在共享内存中。为了解决这个问题，你可以使用Boost.Interprocess库，它提供了一些STL兼容的容器，它们可以在共享内存上分配内存。

以下是如何使用Boost.Interprocess在共享内存上创建并使用STL容器的示例：

首先已经安装了Boost库。你可以从官网（https://www.boost.org/）获取Boost库并按照说明进行安装。open in new window

接下来，引入必要的头文件：

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/sync/named_mutex.hpp>
#include <iostream>

定义共享内存中使用的容器类型：

namespace bip = boost::interprocess;

typedef bip::allocator<int, bip::managed_shared_memory::segment_manager> ShmemAllocator;
typedef bip::vector<int, ShmemAllocator> MyVector;

在共享内存中创建STL容器：

void create_shared_memory_vector() {
    bip::shared_memory_object::remove("MySharedMemory");
    bip::managed_shared_memory segment(bip::create_only,"MySharedMemory", 65536); // 65536是共享内存的大小，可以根据需要进行调整
    // 使用共享内存分配器构造容器
	ShmemAllocator alloc_inst(segment.get_segment_manager());
	MyVector *my_vector = segment.construct<MyVector>("MyVector")(alloc_inst);

	// 向共享内存中的向量添加元素
	for (int i = 0; i < 10; ++i) {
    	my_vector->push_back(i);
	}
}

从共享内存中读取STL容器：

void read_shared_memory_vector() {
    bip::managed_shared_memory segment(bip::open_only, "MySharedMemory");

    // 在共享内存中找到容器
    MyVector *my_vector = segment.find<MyVector>("MyVector").first;

    // 从共享内存中的向量读取元素并打印
    for (int i = 0; i < my_vector->size(); ++i) {
        std::cout << (*my_vector)[i] << std::endl;
    }
}

在main函数中调用创建和读取共享内存的函数：

int main() {
    create_shared_memory_vector();
    read_shared_memory_vector();

    // 清除共享内存对象
    bip::shared_memory_object::remove("MySharedMemory");

    return 0;
}

8. map插入方式有几种？

使用insert成员函数

这是一种通用的插入方式，可以将一个键值对或一个迭代器范围插入到map中。示例如下：

std::map<int, std::string> my_map;
// 插入单个键值对
my_map.insert(std::make_pair(1, "one"));
my_map.insert(std::pair<int, std::string>(2, "two"));
my_map.insert({3, "three"});

// 插入迭代器范围（例如从另一个map中插入）
std::map<int, std::string> another_map = {{4, "four"}, {5, "five"}};
my_map.insert(another_map.begin(), another_map.end());

使用emplace成员函数

emplace会直接在map中构造一个新元素，而不是先创建一个临时对象，然后再将它插入到map中。这样可以减少对象的构造和析构开销，提高性能。示例如下：

std::map<int, std::string> my_map;
my_map.emplace(1, "one");
my_map.emplace(2, "two");
my_map.emplace(3, "three");

使用下标操作符（operator[]）

下标操作符可以通过键值直接访问或插入元素。如果键值不存在于map中，它会自动插入一个具有该键值和默认值的元素。使用下标操作符插入元素时，如果键值不存在，会默认构造一个值对象，然后将其插入map。因此，如果你的值类型没有默认构造函数，这种插入方式可能会导致编译错误。示例如下：

std::map<int, std::string> my_map;
my_map[1] = "one";
my_map[2] = "two";
my_map[3] = "three";

9. vector越界访问下标会怎么样？map越界访问下标会怎么样？

vector越界访问下标

访问vector越界下标的行为是未定义的（Undefined Behavior），可能导致程序崩溃、错误结果或其他不可预期的后果。在某些情况下，可能没有立即可见的影响，但这是非常危险的，因为它可能导致内存损坏或其他难以追踪的问题。为了避免越界访问，应该确保在访问vector元素之前检查索引是否在范围内。如果需要进行安全检查，可以使用at()成员函数，它在越界访问时会抛出std::out_of_range异常。

map越界访问下标

尝试访问map中不存在的键时，C++的行为与vector不同。使用下标运算符（[]）访问map中不存在的键会导致该键被插入到map中，并创建一个具有默认构造函数初始化值的新值。这意味着越界访问不会导致未定义行为，但可能导致无意中修改map的大小和内容。如果想要查询map中的键而不插入新的键值对，可以使用find()成员函数。这将返回一个迭代器，指向找到的元素或指向map的end()，如果键不存在。

10. vector删除元素时会不会释放空间？

当使用std::vector的erase()成员函数删除元素时，它会从vector中移除元素，并将后面的元素向前移动以填补空缺。然而，erase()并不会自动减小vector的容量（capacity），即分配给vector的内存空间。实际上，除非显式地调用shrink_to_fit()或者重新分配更小容量的内存，否则vector的容量将保持不变。

如果在删除元素后想要释放多余的空间，可以使用shrink_to_fit()成员函数。这个函数会尝试将vector的容量减小到与其大小（size）相匹配，从而释放不再使用的内存空间。需要注意的是，shrink_to_fit()并不保证一定能够减小容量，因为这取决于具体的实现和内存分配策略。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    vec.erase(vec.begin() + 2); // 删除下标为2的元素

    std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;

    vec.shrink_to_fit(); // 尝试将容量减小到与大小相匹配

    std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;

    return 0;
}

在这个示例中首先创建了一个包含5个整数的vector。然后使用erase()删除了下标为2的元素。可以看到，尽管vector的大小（size）已经减小到4，但容量（capacity）仍然不变。当调用shrink_to_fit()后，vector的容量可能会减小到与大小相匹配，从而释放多余的内存空间。

11. map[]与find的区别？

std::map的operator[]（下标操作符）和find()成员函数都可以用来查询map中的键值对，但它们的行为和用途有所不同。

operator[]（下标操作符）

当使用下标操作符（[]）访问map中的某个键时，如果该键已经存在于map中，则返回对应的值的引用。但如果键不存在，map会自动创建一个新的键值对，键为给定的键，值为对应值类型的默认构造函数初始化值，然后返回新值的引用。因此，使用下标操作符可能导致map的大小和内容发生变化。

std::map<int, std::string> my_map;

my_map[1] = "One"; // 插入键值对 {1, "One"}

std::string value = my_map[1]; // 获取键为1的值，此时value为"One"

std::string non_existent_value = my_map[2]; // 键为2的值不存在，会插入一个新的键值对 {2, ""}
                                            // non_existent_value为""

find()

find()成员函数用于查询map中的键，但不会修改map。当find()在map中找到给定的键时，它返回一个指向找到的键值对的迭代器。如果键不存在，则返回指向map的end()的迭代器。因此，使用find()查询键值对不会导致map的大小和内容发生变化。

std::map<int, std::string> my_map;

my_map[1] = "One"; // 插入键值对 {1, "One"}

auto it = my_map.find(1);
if (it != my_map.end()) {
    std::string value = it->second; // 获取键为1的值，此时value为"One"
}

auto non_existent_it = my_map.find(2);
if (non_existent_it == my_map.end()) {
    std::cout << "Key 2 not found." << std::endl;
}

operator[]和find()的主要区别在于：使用下标操作符可能会修改map的大小和内容，而find()则不会。在查询键值对时，如果不希望无意中插入新的键值对，应该使用find()而不是下标操作符。

12. STL中list与queue之间的区别？

std::list： std::list 是一个双向链表容器，支持在常数时间内在任何位置插入和删除元素。它提供了随机访问迭代器，这意味着你可以在链表中向前和向后移动，但不能直接访问任意位置的元素。std::list 是一种非连续存储的数据结构，这意味着它的元素可能分散在内存中的不同位置。

std::list 主要用途：

当需要在容器中间插入或删除元素时，使用 std::list 效率较高。
当不需要随机访问元素时，可以考虑使用 std::list。

std::queue： std::queue 是一个容器适配器，它基于其他容器（如 std::deque、std::list 或 std::vector）实现了一个先进先出（FIFO）的队列。std::queue 提供了有限的接口，仅支持在队列尾部插入元素（push），在队列头部移除元素（pop）以及访问队列头部元素（front）和尾部元素（back）。std::queue 的底层容器决定了它的存储方式和性能特性。

std::queue 主要用途：

当需要实现先进先出（FIFO）策略时，使用 std::queue 是很自然的选择。
当不需要在容器中间插入或删除元素时，可以使用 std::queue。

13. STL中的allocator，deallocate？

在C++标准库（STL）中，allocator 是一个模板类，用于封装内存分配和释放策略。STL容器（如 std::vector，std::list，std::map 等）使用 allocator 对象来管理其内部存储的内存分配和释放。这样可以使容器的实现与内存管理策略解耦，从而提供更大的灵活性。

allocator 类主要提供以下功能：

分配内存：allocator 提供了 allocate() 成员函数，用于分配内存空间，以容纳指定数量的对象。例如：

std::allocator<int> alloc;
int* p = alloc.allocate(10);  // 分配内存空间，可容纳10个整数

构造对象：allocator 提供了 construct() 成员函数，用于在已分配的内存上构造对象。例如：

alloc.construct(p, 42);  // 在分配的内存空间上构造一个值为42的整数

销毁对象：allocator 提供了 destroy() 成员函数，用于销毁已构造的对象。例如：

alloc.destroy(p);  // 销毁在分配的内存空间上构造的整数

释放内存：allocator 提供了 deallocate() 成员函数，用于释放之前分配的内存空间。例如：

alloc.deallocate(p, 10);  // 释放之前分配的内存空间

你认为这篇文章怎么样？

昵称

邮箱

按正序
按倒序
按热度

STL

# 1. 什么是STL？

# 2. vector与list的区别与应用？

# 3. STL vector的实现，删除其中的元素，迭代器如何变化？为什么是两倍扩容？释放空间？

# 4. set与unordered_set的区别？

# 5. unordered_map与map的区别？

# 6. map、set是怎么实现的，红黑树是怎么能够同时实现这两种容器？ 为什么使用红黑树？

# 7. 如何在共享内存上使用stl标准库？

# 8. map插入方式有几种？

# 9. vector越界访问下标会怎么样？map越界访问下标会怎么样？

# 10. vector删除元素时会不会释放空间？

# 11. map[]与find的区别？

# 12. STL中list与queue之间的区别？

# 13. STL中的allocator，deallocate？

预览: