1 vector 相关？

1-1 vector 和 list 的异同？

vector和list是C++中的两种不同的容器类型，用于存储和操作元素的集合。它们有以下区别和应用：

内存结构：

Vector: Vector使用连续的内存空间存储元素，类似于数组。它可以高效地进行随机存取，时间复杂度为O(1)。插入和删除操作会导致内存块的拷贝，时间复杂度为O(n)。

List: List使用双向链表来存储元素，内存空间不连续。它的随机存取效率较低，需要遍历链表，时间复杂度为O(n)。但是插入和删除操作非常高效。 容量动态增长：

Vector: Vector具有动态增长的能力，当元素数量超过当前容量时，会自动重新分配更大的内存空间，并进行内存拷贝。程序员不需要手动处理容量问题。

List: List没有容量的限制，可以根据需要动态增长。

迭代器的有效性：

Vector: 在对Vector进行插入和删除操作后，迭代器可能会失效，需要重新定位。 List: 在对List进行插入和删除操作后，迭代器仍然有效。

查找两者的倒数第二个元素：

1

int mySize = vec.size();vec.at(mySize -2);

2

list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过 你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历：

1-2 vector 的底层实现？

C++的vector底层通常使用动态分配的数组来实现，即连续的线性空间。下面分别介绍vector的底层实现、扩容机制和insert方法的几种情况：

底层实现：

vector内部维护一个指针，指向连续的内存空间，用于存储元素。 初始时，vector会分配一块固定大小的内存空间，可以容纳一定数量的元素。

当需要存储更多的元素时，vector会根据扩容机制重新分配更大的内存空间，并将原有元素移动到新的空间中。

扩容机制：

vector的扩容是自动进行的，它会在需要添加元素时判断当前空间是否足够。 当空间不足以容纳新元素时，vector会进行扩容操作。

扩容通常会分配一块更大的内存空间（例如原空间的两倍大小），将原有元素移动到新空间中，然后释放原空间。 扩容可能涉及到数据的复制或移动，因此会有一定的性能开销。

insert方法的几种情况：

vector的insert方法用于在指定位置插入元素，它有多个重载形式，可以根据需要插入单个元素、一定数量的元素或者另一个容器中的元素。

如果插入位置是末尾（end）之前的位置，且当前空间足够容纳新元素，那么插入操作会在指定位置直接插入元素，不会触发扩容，时间复杂度为O(1)。

如果插入位置是末尾（end）之前的位置，但当前空间不足，需要进行扩容操作，那么插入操作会在指定位置插入元素，并触发扩容。扩容操作的时间复杂度为O(n)，其中n为需要插入的元素数量。

如果插入位置是末尾（end）位置，无论当前空间是否足够，插入操作都会在末尾添加元素，不会触发扩容，时间复杂度为O(1)。

如果插入位置是其他位置（非末尾），无论当前空间是否足够，插入操作都需要将插入位置后的元素逐个向后移动，然后在指定位置插入元素，时间复杂度为O(n)，其中n为元素的数量。

void vector::expandCapacity() {
    size_t newCapacity = capacity * 2; // 扩容为原大小的两倍
    T* newElements = new T[newCapacity]; // 配置新的更大空间
    for (size_t i = 0; i < size; i++) {
        newElements[i] = elements[i]; // 移动数据到新空间
    }
    delete[] elements; // 释放原空间
    elements = newElements; // 更新指针指向新空间
    capacity = newCapacity; // 更新容量
}

1-3 vector 中的删除操作？

• 向量容器vector的成员函数pop_back()可以删除最后一个元素。pop_back()会将最后一个元素从向量中移除，并且会调整向量的大小，使其减少一个元素。

• 函数erase()可以删除由一个iterator指向的元素，也可以删除一个指定范围的元素。erase()的用法有多种形式，可以传入一个迭代器指向要删除的元素，或者传入两个迭代器指定要删除的范围。

• 通用算法remove()并不能直接删除vector容器中的元素。remove()算法是用来移除容器中满足特定条件的元素，并将剩余的元素前移，返回一个指向新的逻辑末尾的迭代器。但是remove()并不会改变容器的大小，它只是移动元素并返回新的逻辑末尾位置，需要结合erase()函数来实际删除元素并改变容器大小。

• pop_back()、erase()等成员函数会改变容器的大小，而remove()算法不会直接改变容器的大小，需要结合erase()函数才能删除元素并改变容器的大小。

2 容器指针和引用？

#include <vector>

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

    // 使用指针指向vector
    std::vector<int>* ptr = &vec;

    // 通过指针访问容器元素
    (*ptr)[0] = 10;

    // 通过指针调用容器的成员函数
    ptr->push_back(6);

    return 0;
}
#include <vector>

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

    // 使用引用引用vector
    std::vector<int>& ref = vec;

    // 直接访问容器元素
    ref[0] = 10;

    // 直接调用容器的成员函数
    ref.push_back(6);

    return 0;
}

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

1

vector的size()函数返回已使用的空间大小，capacity()函数返回总空间大小，而capacity() - size()表示剩余可用空间大小。

2

当size()和capacity()相等时，表示vector的空间已被用完，如果再添加新元素，则会引发vector空间的动态增长。

3

使用reserve(n)可以预先分配一块较大的指定大小的内存空间，这样在指定大小的内存空间未被使用完之前，不会引发重新分配内存空间，从而提高效率。只有当n大于capacity()时，调用reserve(n)才会改变vector的容量。

4

resize()函数只改变元素的数目，不改变vector的容量。

• 空的vector对象的size()和capacity()都为0。
• 当空间大小不足时，新分配的空间大小为原空间大小的2倍。
• 用reserve(size_type)只是扩大capacity值，这些内存空间可能还是“野”的，如果此时使用“[ ]”来访问，则可能会越界。而resize(size_type new_size)会真正使容器具有new_size个对象。

5

不同编译器下，vector的扩容大小可能有所不同，如在VS中为1.5倍，在GCC中为2倍。这是空间和时间的权衡，增加空间分配可以降低平摊时间复杂度，但也会浪费空间。

6

使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配 的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1,2)

采用成倍方式扩容可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此推荐使用成倍的方式进行扩容。

使用 reserve() 函数预先分配容量为 10，然后依次向 vector 中插入 20 个元素。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    // 增加指定大小的容量
    vec.reserve(10);  // 预分配容量为10

    for (int i = 0; i < 20; i++) {
        vec.push_back(i);
        std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    }

    return 0;
}
Size: 1, Capacity: 10
Size: 2, Capacity: 10
Size: 3, Capacity: 10
Size: 4, Capacity: 10
Size: 5, Capacity: 10
Size: 6, Capacity: 10
Size: 7, Capacity: 10
Size: 8, Capacity: 10
Size: 9, Capacity: 10
Size: 10, Capacity: 10
Size: 11, Capacity: 15
Size: 12, Capacity: 15
Size: 13, Capacity: 15
Size: 14, Capacity: 15
Size: 15, Capacity: 15
Size: 16, Capacity: 22
Size: 17, Capacity: 22
Size: 18, Capacity: 22
Size: 19, Capacity: 22
Size: 20, Capacity: 22

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    for (int i = 0; i < 20; i++) {
        vec.push_back(i);
        std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    }

    return 0;
}


Size: 1, Capacity: 1
Size: 2, Capacity: 2
Size: 3, Capacity: 3
Size: 4, Capacity: 4
Size: 5, Capacity: 6
Size: 6, Capacity: 6
Size: 7, Capacity: 9
Size: 8, Capacity: 9
Size: 9, Capacity: 9
Size: 10, Capacity: 13
Size: 11, Capacity: 13
Size: 12, Capacity: 13
Size: 13, Capacity: 13
Size: 14, Capacity: 19
Size: 15, Capacity: 19
Size: 16, Capacity: 19
Size: 17, Capacity: 19
Size: 18, Capacity: 19
Size: 19, Capacity: 19
Size: 20, Capacity: 28

7

vector的内存空间只在析构时才会被系统回收，clear()函数可以清空所有元素，但无法保证内存的回收。如果需要动态缩小空间，可以考虑使用deque，或使用swap()函数来帮助释放内存。

vector(Vec).swap(Vec);
vector().swap(Vec);

vector(Vec).swap(Vec);: 这行代码的作用是清空Vec并释放其内存空间。它通过创建一个临时的vector对象，命名为vector(Vec)，该对象使用了Vec的拷贝构造函数，从而复制了Vec中的元素。接下来，通过调用swap函数，将临时的vector对象与原始的Vec进行交换。由于交换操作会将临时对象的内存空间释放掉，因此这样就清空了Vec并释放了其内存空间。

vector().swap(Vec);: 这行代码的作用也是清空Vec并释放其内存空间。它直接创建了一个临时的匿名vector对象，即vector()，并通过调用swap函数，将临时对象与Vec进行交换。由于临时对象没有任何元素，因此交换后的效果就是将Vec清空并释放其内存空间。

4 容器内部删除一个元素

在顺序容器（如vector、deque）中使用erase()函数删除元素时，被删除的迭代器不仅会失效，而且之后的所有迭代器也会失效（除了list容器）。

因此，不能使用erase(it++)的方式进行迭代器的删除操作。然而，erase()函数会返回被删除元素的下一个有效迭代器，因此可以通过将返回值赋给迭代器来更新迭代器的位置。

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int>::iterator it = vec.begin();

while (it != vec.end()) {
    if (*it % 2 == 0) {
        it = vec.erase(it);  // 删除偶数元素，并将it更新为下一个有效迭代器
    } else {
        ++it;  // 移动到下一个元素
    }
}

在关联容器（如map、set、multimap、multiset）中使用erase()函数删除元素时，被删除的迭代器失效，但是erase()函数没有返回值（返回void）。因此，可以使用erase(it++)的方式进行迭代器的删除操作。

std::set<int> mySet = {1, 2, 3, 4, 5};
std::set<int>::iterator it = mySet.begin();

while (it != mySet.end()) {
    if (*it % 2 == 0) {
        mySet.erase(it++);  // 删除偶数元素，并将it更新为下一个迭代器
    } else {
        ++it;  // 移动到下一个元素
    }
}

5 STL 中的迭代器

迭代器是一种抽象的设计理念，它提供了一种遍历容器内部元素的接口，使得我们可以在不了解容器内部原理的情况下对容器进行操作。

迭代器可以看作是容器与STL算法之间的粘合剂，通过迭代器，我们可以将算法应用于不同类型的容器。

迭代器的主要作用是提供遍历容器内部元素的能力。

迭代器内部通常保存有一个与容器相关联的指针（或其他迭代器所需的信息），并重载了一系列运算符，例如*运算符和->运算符，以及前缀和后缀形式的递增（++）和递减（--）运算符等。

这使得我们可以通过迭代器来访问容器中的元素并进行操作。迭代器的设计类似于C++中的智能指针，它们都封装了指针，并提供了方便的操作接口，例如自动释放内存。

在STL中，最常用的迭代器有五种相应的类型，分别是：

• value type：迭代器所指向元素的类型。
• difference type：表示两个迭代器之间的距离，通常是一个带符号整数类型。
• pointer：指向迭代器所指向元素的指针类型。
• reference：迭代器所指向元素的引用类型。
• iterator category：迭代器的类型标签，用于标识迭代器的特性和支持的操作，例如输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。

这些迭代器的类型特性和支持的操作可能会有所不同，它们适用于不同种类的容器，并提供了不同级别的功能和效率。通过使用这些迭代器，我们可以以统一的方式访问和操作各种容器，使得代码更加灵活和可复用。

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

1. 他们的底层都是以红黑树的结构实现，因此插入删除等操作都在O(logn)时间内完成，因此可以完成高效的插入删除；
2. 在这里我们定义了一个模版参数，如果它是key那么它就是set，如果它是map，那么它就是map；
   底层是红黑树，实现map的红黑树的节点数据类型是key+value，而实现set的节点数据类型是value
3. 因为map和set要求是自动排序的，红黑树能够实现这一功能，而且时间复杂度比较低。

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

将STL容器（如map、vector、list等）放入共享内存中可以极大地增强进程间通信的能力。这样做的好处是我们不需要为共享内存设计额外的数据结构，因为STL容器本身已经提供了强大的通用数据结构和内存管理方案。

想象一下，当我们将一个元素插入到STL列表（list）中时，列表容器会自动为其分配内存并保存数据。考虑将STL容器放入共享内存中时，我们不希望容器自己在堆上分配内存，因为这样会导致问题。

一种笨拙的方法是在堆上构造STL容器，然后将容器复制到共享内存中，并确保容器内部分配的内存指向共享内存的相应区域。然而，这几乎是不可能完成的任务。

当进程A在共享内存中放置了多个容器时，进程B如何找到这些容器呢？有几种方法可以实现。

一种方法是进程A将容器放置在共享内存中的确定地址上（固定偏移量），然后进程B可以通过已知的地址来获取容器。

另一种改进的方法是，进程A首先在共享内存的某个地址上放置一个map容器，然后进程A创建其他容器，并将它们的名称和地址一并保存到这个map容器中。

进程B知道如何获取保存地址映射的map容器，然后根据名称获取其他容器的地址。

这样，进程B可以通过已知的共享内存地址或者通过map容器来定位和访问进程A放置在共享内存中的容器，实现进程间通信和数据共享。

这种方法充分利用了STL容器的灵活性和可扩展性，并提供了一种方便的机制来管理和访问共享内存中的数据结构。

8 map 插入方式有几种？

用insert函数插入pair数据， mapStudent.insert(pair<int, string>(1, "student_one"));

用insert函数插入value_type数据 mapStudent.insert(map<int, string>::value_type (1, "student_one"));

在insert函数中使用make_pair()函数 mapStudent.insert(make_pair(1, "student_one"));

用数组方式插入数据 mapStudent[1] = "student_one";

9 vector越界访问下标，map越界访问下标？vector删除元素时会不会释放空间？

通过下标访问vector中的元素时不会做边界检查，即便下标越界。也就是说，下标与first迭代器相加的结果超过了finish迭代器的位置，程序也不会报错，而是返回这个地址中存储的值。

如果想在访问vector中的元素时首先进行边界检查，可以使用vector中的at函数。通过使用at函数不但可以通过下标访问vector中的元素，而且在at函数内部会对下标进行边界检查。

map的下标运算符[]的作用是：将key作为下标去执行查找，并返回相应的值；如果不存在这个key，就将一个具有该key和value的键值对插入这个map。

erase()函数，只能删除内容，不能改变容量大小；erase成员函数，它删除了itVect迭代器指向的元素，并且返回要被删除的itVect之后的迭代器，迭代器相当于一个智能指针；clear()函数，只能清空内容，不能改变容量大小。如果要想在删除内容的同时释放内存，那么你可以选择deque容器。

10 map中[]与find的区别？

map的下标运算符[]的作用是：将关键码作为下标去执行查找，并返回对应的值；如果不存在这个关键码，就将一个具有该关键码和值类型的默认值的项插入这个map。

map的find函数用于通过关键码执行查找，如果找到了对应的关键码，则返回该位置的迭代器；如果不存在这个关键码，则返回尾迭代器（end()迭代器）。可以通过判断find函数的返回值与end()迭代器进行比较来确定是否找到了指定的关键码。

11 STL中list与queue之间的区别？

list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。由于list是双向链表，其节点可以在内存中的任意位置分布，因此使用普通指针作为迭代器无法准确表示节点的位置。

list的插入操作和删除操作不会造成原有的list迭代器失效。由于list的节点结构不会改变，插入或删除节点并不会影响其他节点的位置，因此在插入和删除操作之后，原有的list迭代器仍然有效。

list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针。list的最后一个节点的next指针指向头节点，形成一个环状的链表结构，这样可以方便地在头尾两端进行插入和删除操作。

list不像vector那样在空间不足时进行重新配置和数据移动的操作，因此在插入前的所有迭代器在插入操作之后仍然有效。由于list使用动态分配内存，并且节点的位置可以任意分布，因此在插入操作时并不需要重新分配内存或移动数据。

deque是一种双向开口的连续线性空间，可以在头尾两端进行元素的插入和删除操作。deque允许在起头端和末尾端常数时间内进行元素的插入和删除操作，这是deque和vector的一个重要差异。

deque和vector最大的差异在于，deque允许常数时间内对起头端进行元素的插入或移除操作，而vector只能在尾部进行常数时间内的插入或移除操作。此外，deque是动态地以分段连续空间组合而成的，可以随时增加新的空间段并链接起来，所以没有所谓的容量限制，不需要进行空间保留的操作。

12 常见容器性质总结

• vector: 底层数据结构为数组，支持快速随机访问，动态数组。
• list: 底层数据结构为双向链表，支持快速增删，不支持随机访问。
• deque: 底层数据结构为中央控制器和多个缓冲区，支持首尾快速增删，也支持随机访问。是一个双端队列。
• stack: 一般使用list或deque实现，封闭头部即可，用于实现栈的功能。
• queue: 一般使用list或deque实现，封闭头部即可，用于实现队列的功能。
• priority_queue: 底层数据结构一般为vector，使用堆heap作为处理规则来管理底层容器实现优先队列。
• set: 底层数据结构为红黑树，有序，不重复。
• multiset: 底层数据结构为红黑树，有序，可重复。
• map: 底层数据结构为红黑树，有序，不重复，存储键值对。
• multimap: 底层数据结构为红黑树，有序，可重复，存储键值对。
• unordered_set: 底层数据结构为哈希表，无序，不重复。
• unordered_multiset: 底层数据结构为哈希表，无序，可重复。
• unordered_map: 底层数据结构为哈希表，无序，不重复，存储键值对。
• unordered_multimap: 底层数据结构为哈希表，无序，可重复，存储键值对。

12-1 什么是有序容器？

在容器中，有序指的是容器中元素的排列顺序与插入顺序或者特定的排序规则相对应。

对于有序容器（如set、map等），它们会维护元素的有序性，这意味着元素在容器中按照一定的顺序排列。具体的排序方式可以是根据元素的比较运算符进行排序（默认是升序），或者通过自定义的比较函数来指定排序规则。

有序容器的特点是：

• 插入元素时会按照排序规则将元素放置在正确的位置，保持容器的有序性。
• 元素在容器中的位置是固定的，插入、删除元素不会改变其他元素的相对位置。
• 通过迭代器遍历有序容器时，可以按照元素的排序顺序逐个访问元素。
• 需要注意的是，有序容器的有序性是相对于元素的值而言的，而不是插入操作的顺序。因此，如果通过自定义的比较函数或者比较运算符来定义排序规则，那么容器中的元素将按照该规则进行排序，而不是按照插入顺序排列。

另外，还有无序容器（如unordered_set、unordered_map等），它们并不维护元素的有序性，元素在容器中的位置是无序的，主要通过哈希表实现高效的查找和插入操作。

13 STL 中每种容器对应的迭代器

vector：使用随机访问迭代器（Random Access Iterator）。随机访问迭代器允许通过指针算术运算来快速访问容器中的任意元素。

list：使用双向迭代器（Bidirectional Iterator）。双向迭代器支持向前和向后遍历容器中的元素，但不支持随机访问。

deque：使用随机访问迭代器（Random Access Iterator）。与vector相同，deque也支持通过指针算术运算来快速访问容器中的任意元素。

stack 和 queue：它们不提供公开的迭代器接口，因为它们是适配器而不是容器。它们使用底层容器的迭代器来实现功能。

set 和 multiset：使用双向迭代器（Bidirectional Iterator）。双向迭代器允许向前和向后遍历容器中的元素，并保持元素的有序性。

map 和 multimap：使用双向迭代器（Bidirectional Iterator）。类似于set，map和multimap也使用双向迭代器来遍历容器中的元素，同时保持元素的有序性。

unordered_set 和 unordered_multiset：使用正向迭代器（Forward Iterator）。正向迭代器允许向前遍历容器中的元素，但不支持反向遍历。

unordered_map 和 unordered_multimap：使用正向迭代器（Forward Iterator）。与unordered_set类似，unordered_map也使用正向迭代器来遍历容器中的元素。

14 STL 中 slist 的实现？

list 是双向链表，而 slist（单链表）是单向链表。它们的主要区别在于迭代器的类型，list 使用的是双向迭代器（Bidirectional iterator），而 slist 使用的是单向迭代器（Forward iterator）。双向迭代器可以向前和向后遍历容器中的元素，而单向迭代器只能向前遍历。

slist 的插入操作通常是将新元素插入到指定位置之前，而不是之后。由于 slist 是单向链表，无法回头，只能向后遍历，因此在其他位置插入或移除元素会很低效。然而，在 slist 的开头插入或移除元素是高效的，因此 slist 提供了 insert_after() 和 erase_after() 函数来支持在开头进行灵活的操作。

slist 提供了 push_front() 操作，将元素插入到链表的开头。需要注意的是，插入到 slist 中的元素的存储顺序和输入顺序是相反的，即后插入的元素会位于前面。

template <class T, class Allco = alloc>
class slist {
  ...
private:
  ...
  static list_node* create_node(const value_type& x) {} //配置空间、构造元素
  static void destroy_node(list_node* node) {} //析构函数、释放空间
private:
  list_node_base head; //头部
public:
  iterator begin() {}
  iterator end() {}
  size_type size() {}
  bool empty() {}
  void swap(slist& L) {} //交换两个slist，只需要换head即可
  reference front() {} //取头部元素
  void push_front(const value& x) {} //头部插入元素
  void pop_front() {} //从头部取走元素
  ...
}

#include <forward_list>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    forward_list<int> fl;
    fl.push_front(1);
    fl.push_front(3);
    fl.push_front(2);
    fl.push_front(6);
    fl.push_front(5);

    forward_list<int>::iterator ite1 = fl.begin();
    forward_list<int>::iterator ite2 = fl.end();
    for (; ite1 != ite2; ++ite1) {
        cout << *ite1 << " "; // 5 6 2 3 1
    }
    cout << endl;

    ite1 = find(fl.begin(), fl.end(), 2); //寻找2的位置

    if (ite1 != ite2)
        fl.insert_after(ite1, 99);
    for (auto it : fl) {
        cout << it << " "; // 5 6 2 99 3 1
    }
    cout << endl;

    ite1 = find(fl.begin(), fl.end(), 6); //寻找6的位置
    if (ite1 != ite2)
        fl.erase_after(ite1);
    for (auto it : fl) {
        cout << it << " "; // 5 6 99 3 1
    }
    cout << endl;

    return 0;
}

15 STL 中list的实现？

list确实是一个双向链表，每个节点包含一个元素和指向前一个节点和后一个节点的指针。与vector相比，list的好处在于插入和删除操作只影响一个元素的空间，因此对于任何位置的元素插入和删除都是常数时间的复杂度。list的迭代器支持双向移动，可以使用"++"和"--"操作来遍历链表。

与vector不同，list的插入和接合操作不会导致原有迭代器失效。这是因为list的节点在存储空间中不一定连续，插入和删除操作只需要调整节点的指针，而不需要移动其他元素。这使得list成为一个非常灵活的容器。

另一个特点是list是一个环形链表，即最后一个节点的指针指向第一个节点，形成一个闭环。这样只需要一个指针便可以完整表示整个链表。list的节点指针始终指向尾部的一个空白节点，所以可以称为“前闭后开”的区间结构。

list的空间管理通常使用alloc作为空间配置器，并提供了list_node_allocator函数用于一次性配置多个节点的空间。由于list的双向特性，它支持在头部和尾部进行push和pop操作。此外，list还提供了其他操作，如erase、splice、sort、merge、reverse等。

总的来说，list是一种非常灵活的容器，适用于需要频繁插入和删除元素的场景，尤其是在元素数量较大时，因为它的插入和删除操作的时间复杂度都是常数时间。

1	template <class T>
2	struct list_node{
3	typedef void* void_pointer;
4	void_pointer prev;
5	void_pointer next;
6	T data; 7	}

16 STL 中set的实现？

set是STL中的关联式容器，它的特点是元素会根据其值自动进行排序，默认情况下是升序排序。set的元素的键值就是实值，实值就是键值，不允许有两个相同的键值存在于set中。

set的迭代器是一种const_iterator，也就是说，它不允许通过迭代器修改元素的值，只能进行读取操作。

标准的STL set使用红黑树（RB-tree）作为底层数据结构来实现。红黑树是一种自平衡的二叉查找树，具有以下特性：

每个节点要么是红色，要么是黑色。 根节点是黑色的。 如果一个节点是红色的，则它的子节点必须是黑色的。 任意节点到其每个叶子节点的路径上包含相同数量的黑色节点。 红黑树的特性保证了树的平衡性，使得set的插入、查找和删除操作的时间复杂度都能保持在对数时间内。

通过调用红黑树的操作行为，set可以实现插入、删除、查找等操作，并且这些操作的行为与红黑树的操作行为相对应。这种将操作委托给底层红黑树的方式使得set的实现更加高效和灵活。

17 STL 中 deque 的实现？

vector是单向开口（尾部）的连续线性空间，而deque是双向开口的连续线性空间。虽然vector也可以在头部进行元素操作，但是头部操作的效率较低，因为它需要涉及整体的元素移动。

deque相对于vector的最大差异在于：

对头端进行元素操作的效率都是常数时间，即在头部和尾部插入或删除元素的操作具有较高的效率。

deque没有容量的概念，它是动态地以分段连续空间组合而成的。当需要增加新的空间时，可以配置一段定量的连续空间并连接在头部或尾部，从而实现动态扩展。

需要注意的是，尽管deque也提供了随机访问的迭代器，但它的迭代器并非普通指针，其实现比vector的迭代器复杂。

因此，除非必要，一般情况下推荐使用vector而非deque。

如果需要对deque进行排序，可以先将deque中的元素复制到vector中，利用vector的排序算法进行排序，然后再将结果复制回deque中。

由于deque的实现方式，它由一段一段的定量连续空间组成。当需要增加新的空间时，可以通过配置新的连续空间并将其拼接到头部或尾部来实现。因此，deque的主要任务是如何维护这种整体的连续性，以便实现高效的元素操作。

deque内部通常包含一个指针指向一块称为map的小型连续空间，而map中的每个元素都是一个节点（node）。每个节点都是一个指针，指向另一段较大的连续空间，称为缓冲区（buffer）。实际上，缓冲区是deque中存储数据的区域。

默认情况下，deque的缓冲区大小通常为512字节（具体大小可能有所不同，取决于编译器和实现）。这意味着每个节点所指向的缓冲区可以存储一定数量的元素。

通过使用这种结构，deque能够实现动态扩展，当需要增加新的空间时，它可以分配新的缓冲区，并将新的节点插入到map中。这种设计使得deque能够在两端高效地插入和删除元素，同时保持数据的连续性。

class deque {
    // ...
protected:
    typedef pointer* map_pointer; // 指向map指针的指针
    map_pointer map; // 指向map
    size_type map_size; // map的大小
public:
    // ...
    iterator begin();
    iterator end();
    // ...
}