C++ STL（二）deque

目录

deque（双端队列）

内存结构

验证地址不连续

使用详解

构造函数

元素访问

容量操作

修改

迭代器

迭代器失效

code实例

实现一个简单的deque

deque（双端队列）

std::deque（双端队列）是 C++ 标准模板库（STL）中的一个容器，支持在队列的两端高效地插入和删除元素。它的名字来源于 "Double-Ended Queue"。动态大小：deque可以根据需要动态调整大小。随机访问：支持通过下标访问元素，时间复杂度为 O(1)。非连续存储：deque的元素在内存中不一定是连续存储的，这使得它在两端的插入和删除操作更高效。与 std::vector 不同std::deque的底层实现通常基于分段连续内存，这使得它在两端操作时具有更高的效率。

内存结构

底层原理：std::deque 的底层实现通常是一个分段连续内存的结构。它由多个固定大小的内存块（称为缓冲区或块）组成，这些内存块通过一个中央控制器（通常是数组或指针数组）管理。分段连续内存：std::deque 的内存不是完全连续的，而是由多个连续的内存块组成。每个内存块可以存储固定数量的元素。中央控制器（如指针数组）记录了这些内存块的地址。

优点：在两端插入和删除元素的时间复杂度为 O(1)。不需要像 std::vector 那样在扩容时复制所有元素。缺点：随机访问的时间复杂度为 O(1)，但由于内存不连续，实际性能可能略低于std::vector。

内部实现：缓冲区大小：每个缓冲区的大小是固定的，通常是 512 字节或 1024 字节。缓冲区的大小由实现定义，用户无法直接控制。中央控制器：中央控制器是一个数组，存储了指向各个缓冲区的指针。通过中央控制器，std::deque 可以快速定位任意元素。

迭代器：std::deque 的迭代器是一个随机访问迭代器。迭代器需要记录当前元素所在的缓冲区以及元素在缓冲区中的位置。

验证地址不连续

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

int main() {
    std::deque<int> dq;
    std::vector<int> r;

    // 添加元素并观察内存地址
    for (int i = 0; i < 10; ++i) {
        dq.push_back(i);
        r.push_back(i);
    }
    // 在前端添加元素并观察内存地址
    for (int i = 10; i < 15; ++i) {
        dq.push_front(i);
        r.insert(r.begin(),i);
    }
    // 输出所有元素的地址
    std::cout << "All elements in deque:" << std::endl;
    for (const auto& elem : dq) {
        std::cout << "Element: " << elem << ", Address: " << &elem << std::endl;
    }
    std::cout << "All elements in vector:" << std::endl;
    for (const auto& elem : r) {
        std::cout << "Element: " << elem << ", Address: " << &elem << std::endl;
    }
    return 0;
}

All elements in deque:
Element: 14, Address: 0x1f84b78164c --- Element: 10, Address: 0x1f84b78165c
Element: 0, Address: 0x1f84b781250  --（连续段）----Element: 9, Address: 0x1f84b781274
All elements in vector:
Element: 14, Address: 0x1f84b786f70 ---连续空间）-Element: 9, Address: 0x1f84b786fa8

使用详解

构造函数

元素访问

容量操作

修改

迭代器

迭代器失效

code实例

#include <deque>
#include <iostream>

int main() {
    //构造函数
    std::deque<int> d1; // 空 deque
    std::deque<int> d2(5); // 包含 5 个默认初始化元素的 deque
    std::deque<int> d3(5, 10); // 包含 5 个值为 10 的元素的 deque
    std::deque<int> d = {1, 2, 3, 4, 5}; // 使用初始化列表创建 deque
    
    //元素
    std::cout << "d[2]: " << d[2] << std::endl; // 输出: 3
    std::cout << "d.at(3): " << d.at(3) << std::endl; // 输出: 4
    std::cout << "d.front(): " << d.front() << std::endl; // 输出: 1
    std::cout << "d.back(): " << d.back() << std::endl; // 输出: 5

    //容量
    std::cout << "d.empty(): " << d.empty() << std::endl; // 输出: 0 (false)
    std::cout << "d.size(): " << d.size() << std::endl; // 输出: 5
    std::cout << "d.max_size(): " << d.max_size() << std::endl; // 输出: 一个很大的数
    
    //修改
    d.push_back(6); // d: {1, 2, 3, 4, 5, 6}
    d.push_front(0); // d: {0, 1, 2, 3, 4, 5, 6}
    d.pop_back(); // d: {0, 1, 2, 3, 4, 5}
    d.pop_front(); // d: {1, 2, 3, 4, 5}

    d.insert(d.begin() + 2, 10); // d: {1, 2, 10, 3, 4, 5}
    d.erase(d.begin() + 3); // d: {1, 2, 10, 4, 5}

    //迭代器
    for (auto it = d.begin(); it != d.end(); ++it) {
        std::cout << *it << " "; // 输出: 1 2 10 4 5
    }
    for (auto it = d.rbegin(); it != d.rend(); ++it) {
        std::cout << *it << " "; // 输出: 5 4 10 2 1
    }
    return 0;
}

实现一个简单的deque

#include <iostream>
#include <vector>

class SimpleDeque {
private:
    std::vector<int*> blocks; // 存储内存块的指针
    size_t block_size = 4;    // 每个内存块的大小
    size_t start = 0;         // 第一个元素的位置
    size_t end = 0;           // 最后一个元素的位置

public:
    SimpleDeque() {
        blocks.push_back(new int[block_size]);
    }
    ~SimpleDeque() {
        for (auto block : blocks) {
            delete[] block;
        }
    }
    void push_back(int value) {
        if (end == block_size * blocks.size()) {
            blocks.push_back(new int[block_size]);
        }
        blocks[end / block_size][end % block_size] = value;
        end++;
    }
    void push_front(int value) {
        if (start == 0) {
            blocks.insert(blocks.begin(), new int[block_size]);
            end += block_size;
            start += block_size;
        }
        start--;
        blocks[start / block_size][start % block_size] = value;
    }
    int at(size_t index) {
        if (index >= end - start) {
            throw std::out_of_range("Index out of range");
        }
        return blocks[(start + index) / block_size][(start + index) % block_size];
    }
    size_t size() const {
        return end - start;
    }
};

int main() {
    SimpleDeque dq;
    dq.push_back(1);
    dq.push_back(2);
    dq.push_front(0);
    dq.push_front(-1);
    for (size_t i = 0; i < dq.size(); ++i) {
        std::cout << dq.at(i) << " "; // 输出: -1 0 1 2
    }
    std::cout << std::endl;
    return 0;
}