面试题：C++顺序容器在复杂场景下的操作与设计

容器分析
- vector：
  - 头部和尾部插入删除：在头部插入元素时，由于vector内存是连续的，插入头部元素需要移动所有现有元素，时间复杂度为O(n)；在尾部插入元素，若容量足够，时间复杂度为O(1)，若容量不足需要重新分配内存并拷贝所有元素，时间复杂度为O(n)。删除头部或尾部元素同样存在移动元素的问题，时间复杂度也较高。
  - 随机访问：vector支持高效的随机访问，时间复杂度为O(1)，因为其元素在内存中是连续存储的，可以通过指针偏移直接访问。
- deque：
  - 头部和尾部插入删除：deque（双端队列）在头部和尾部插入和删除元素的时间复杂度都是O(1)。它内部采用分段连续的内存存储，通过一个映射表来管理这些分段内存，使得在两端操作元素时无需移动大量元素。
  - 随机访问：deque也支持随机访问，但其随机访问性能略低于vector。因为deque的元素不是完全连续存储，需要通过映射表来定位元素，时间复杂度仍然是O(1)，但存在一些额外开销。
- list：
  - 头部和尾部插入删除：list（双向链表）在头部和尾部插入和删除元素的时间复杂度都是O(1)。链表结构通过指针连接节点，在头部或尾部操作节点只需要修改几个指针即可。
  - 随机访问：list不支持高效的随机访问。如果要访问第n个元素，需要从链表头（或尾）开始遍历，时间复杂度为O(n)。
综合考虑，deque更适合该场景。它在头部和尾部插入删除元素效率高，同时也能较好地支持随机访问。
基于标准容器的设计扩展（若现有容器不完全满足需求）
- 设计方案：
  - 可以基于deque进行扩展。例如，如果对随机访问的性能要求极高，而deque的随机访问性能略有不足，可以在deque的基础上，维护一个额外的数据结构，如vector，用于快速定位deque中的元素。当在deque中插入或删除元素时，同步更新这个vector的索引信息。这样既利用了deque在头部和尾部操作的高效性，又通过额外的vector索引结构提高了随机访问的性能。
- 关键代码片段：

#include <deque>
#include <vector>
#include <iostream>

template<typename T>
class CustomContainer {
private:
    std::deque<T> data;
    std::vector<typename std::deque<T>::iterator> index;

public:
    // 在头部插入元素
    void push_front(const T& value) {
        data.push_front(value);
        index.insert(index.begin(), data.begin());
    }

    // 在尾部插入元素
    void push_back(const T& value) {
        data.push_back(value);
        index.push_back(std::prev(data.end()));
    }

    // 删除头部元素
    void pop_front() {
        if (!data.empty()) {
            data.pop_front();
            index.erase(index.begin());
        }
    }

    // 删除尾部元素
    void pop_back() {
        if (!data.empty()) {
            data.pop_back();
            index.pop_back();
        }
    }

    // 随机访问
    T& operator[](size_t indexValue) {
        if (indexValue < index.size()) {
            return *index[indexValue];
        }
        throw std::out_of_range("Index out of range");
    }
};

int main() {
    CustomContainer<int> cc;
    cc.push_back(1);
    cc.push_back(2);
    cc.push_front(0);
    std::cout << cc[0] << std::endl; // 输出0
    std::cout << cc[1] << std::endl; // 输出1
    std::cout << cc[2] << std::endl; // 输出2
    cc.pop_back();
    std::cout << cc[1] << std::endl; // 输出0
    return 0;
}

在上述代码中，CustomContainer类内部维护了一个deque用于存储数据，以及一个vector用于记录deque中每个元素的迭代器，从而实现高效的头部和尾部操作以及快速的随机访问。

星途面试题库

面试题：C++顺序容器在复杂场景下的操作与设计

知识考点

面试题答案