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的区别?

sethash_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_setunordered_set 更为合适。

5. unordered_map与map的区别?

mapunordered_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是怎么实现的,红黑树是怎么能够同时实现这两种容器? 为什么使用红黑树?

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

红黑树如何实现 mapset

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

为什么使用红黑树?

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