CPP|简单实现Deque容器

引言

好耶,大灌特灌

Deque

std::deque其实为了兼顾list的插入删除,和vector随机访问的优点,底层机制实现的比较复杂,本质上通常采用一种称为“分段数组”的数据结构,这种结构结合了连续数组的高效访问和链表的高效插入删除特点.实现细节概括为,使用多个分散的内存块,内部维护着一个map来做结构控制.

要简单模拟实现一个deque,实际上可以使用ring buffer来做,当然也可以确实使用stl的方式使用一个可动态增长的map做中央控制器,管理不连续的内存.当然,简单实现仅当实验玩具.

RingBuffer方式

ringbuffer 实际上其实也只是一个简单的数组,但是在执行删除和插入本质上还是使用模运算来进行处理指针,来模拟前后两端的修改,实际上动态变化与std::vector相同.

template <typename T>
class Deque {
private:
    T* elements;  // 就是一个循环一维数组
    size_t capacity;  // 数组的总容量
    size_t frontIndex;  // deque的前端索引
    size_t backIndex;  // deque的后端索引
    size_t size;  // deque中的元素数量

public:
    // 构造函数
    Deque() : elements(nullptr), capacity(0), frontIndex(0), backIndex(0), size(0) {}

    // 析构函数
    ~Deque() {
        clear();
        delete[] elements;
    }

private:
    // 扩展数组容量
    void resize() {
        // 计算新的容量
        size_t newCapacity = (capacity == 0) ? 1 : capacity * 2;

        // 创建新的数组
        T* newElements = new T[newCapacity];

        // 复制元素到新数组
        size_t index = frontIndex;
        for (size_t i = 0; i < size; ++i) {
            newElements[i] = elements[index];
            index = (index + 1) % capacity;
        }

        // 释放旧数组的内存
        delete[] elements;

        // 更新成员变量
        elements = newElements;
        capacity = newCapacity;
        frontIndex = 0;
        backIndex = size;
    }
};

做个ringbuffer ,需要设定变量存储两端下标.利用模运算来实现''双端''

 // 在deque的前端插入元素
    void push_front(const T& value) {
        // 检查是否需要扩展数组容量
        if (size == capacity) {
            resize();
        }
        // 计算新的前端索引
        frontIndex = (frontIndex - 1 + capacity) % capacity;
        // 在新的前端位置插入元素
        elements[frontIndex] = value;

        // 增加deque的元素数量
        ++size;
    }

    // 在deque的后端插入元素
    void push_back(const T& value) {
        // 检查是否需要扩展数组容量
        if (size == capacity) {
            resize();
        }
        // 在当前后端位置插入元素
        elements[backIndex] = value;
        // 计算新的后端索引
        backIndex = (backIndex + 1) % capacity;
        // 增加deque的元素数量
        ++size;
    }

    // 从deque的前端移除元素
    void pop_front() {
        // 检查deque是否为空
        if (size == 0) {
            throw std::out_of_range("Deque is empty");
        }
        // 删除元素不需要显式地删除, 以后新追加元素会自动覆盖
        // 计算新的前端索引
        frontIndex = (frontIndex + 1) % capacity;
        // 减少deque的元素数量
        --size;
    }

    // 从deque的后端移除元素
    void pop_back() {
        // 检查deque是否为空
        if (size == 0) {
            throw std::out_of_range("Deque is empty");
        }
        // 删除元素不需要显式地删除, 以后新追加元素会自动覆盖
        // 计算新的后端索引
        backIndex = (backIndex - 1 + capacity) % capacity;
        // 减少deque的元素数量
        --size;
    }

    // 随机访问元素
    T& operator[](int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of range");
        }
        return elements[(frontIndex + index) % capacity];
    }

    // 清空deque
    void clear() {
        while (size > 0) {
            pop_front();
        }
    }

分段存储方式

STL deque 使用多个小数组（块）来存储元素,每个块的大小是固定的,

我们使用一个std::vector来对扩充内存管理.

template <typename T>
class Deque {
private:
    using value_type = T;
    using const_value_type = const value_type;
    using pointer = value_type*;
    using reference = value_type&;
    using const_reference  = const T&;

    const static std::size_t initial_size = 4;
    std::size_t pivot = 0;
    std::size_t current_first = (initial_size - 1) / 2 - 1;
    std::size_t current_last = (initial_size - 1) / 2;
    std::size_t first_storage = 0;
    std::size_t last_storage = 0;
    std::size_t external_storage_size = 0;
    std::size_t external_capacity = initial_size;
    std::vector<pointer> external_storage; //使用vector来管理多个分区的指针指针
    //创建内存区
private:
    pointer make_storage() noexcept {
        pointer new_storage = reinterpret_cast<T*>(new char[this->initial_size * sizeof(value_type)]); //按字节转换
        return new_storage;
    }

    void resize() noexcept {
        std::size_t new_size = this->external_storage.size() * 2;  //内存扩增*2
        std::vector<pointer> new_external_storage(new_size);
        std::size_t new_pivot = new_size / 2 - 1; //管理内存块map中点
        int upper_offset = static_cast<int>(this->first_storage - this->pivot); //记录偏移量 
        int lower_offset = static_cast<int>(this->last_storage - this->pivot);  
        this->pivot = new_pivot;
        std::size_t storage = new_pivot + upper_offset;
        //迁移原有区间
        for (std::size_t i = this->first_storage; i <= this->last_storage; i++, storage++) {  
            new_external_storage[storage] = this->external_storage[i];
        }
        //释放旧区间
        for (std::size_t i = 0; i < this->first_storage; i++) {
            delete [] this->external_storage[i];                                   
        }
        for (std::size_t i = this->last_storage + 1; i < this->external_storage.size(); i++) {
            delete [] this->external_storage[i];
        }
        //重设分区指向
        this->first_storage = new_pivot + upper_offset;
        this->last_storage = new_pivot + lower_offset;

        for (auto& storage : new_external_storage) {                               
            if (storage == nullptr) {                                              
                storage = this->make_storage();                                  
            }
        }

        this->external_storage = new_external_storage;
        this->external_capacity = this->external_storage.size() * this->initial_size;
    }

public:

     Deque() noexcept {
        this->external_storage.resize(EXTERNAL_INIT_SIZE);
        this->external_capacity = this->initial_size * 2;
        this->external_storage[0] = make_storage();
        this->external_storage[1] = make_storage();
    }

     Deque(pointer source, std::size_t size) {
        for (std::size_t i = 0; i < size; i++) {
            this->push_back(source[i]);
        }
    }
     Deque(std::initializer_list<T> init_list):Deque() {
         for (const T& value : init_list) {
           this->push_back(value);
        }
    }
    ~Deque() {
        for (auto& storage : this->external_storage) {
            delete storage;
        }
    }

    inline std::size_t get_size() const noexcept { return this->external_storage_size; }
    inline std::size_t get_capacity() const noexcept { return this->external_storage_capacity; }
    inline bool empty() const noexcept { return this->external_storage_size == 0; }

    reference operator[](std::size_t index) {
        index++;
        std::size_t offset = 0;

        if (this->current_first >= this->initial_size) {
            offset++;
            index -= (this->initial_size - this->current_first);
        } else {
            index += this->current_first;
        }

        offset += index / this->initial_size;
        index %= this->initial_size;

        return this->external_storage[this->first_storage + offset][index];
    }

    reference at(std::size_t index) {
        assert(index <= this->external_storage_size);
        return (*this)[index];
    }

    reference front() {
        assert(!this->empty());
        return this->operator[](0);
    }

    reference back() {
        assert(!this->empty());
        return this->operator[](this->external_storage_size - 1);
    }

    void push_front(const_reference source) {
        int current_first_int = this->current_first;//当前值_记录

        this->external_storage[this->first_storage][this->current_first] = source;
        this->external_storage_size++;
        current_first_int--;

        if (current_first_int < 0) {
            this->current_first = this->initial_size - 1;
            int first_storage_int = this->first_storage;

            if ((first_storage_int - 1) < 0) {
                this->resize();
            }

            this->first_storage--;
        } else {
            this->current_first = static_cast<std::size_t>(current_first_int);
        }
    }

    void push_back(const_reference source) {
        int current_last_int = this->current_last;
        //值保存
        this->external_storage[this->last_storage][this->current_last] = source;
        this->external_storage_size++;
        current_last_int++;

        if (current_last_int >= this->initial_size) {
            this->current_last = 0;
            int last_storage_int = this->last_storage;
            //当前容器尾是否填满.填满则大小重设
            if (last_storage_int + 1 >= static_cast<int>(this->external_storage.size())) {
                this->resize();
            }
            this->last_storage++;//缓冲区后移
        } else {
            this->current_last = static_cast<std::size_t>(current_last_int);
        }
    }

    void pop_back() {
        if (!this->empty()) {
            int current_last_int = this->current_last;
            current_last_int--;

            if (current_last_int < 0) {
                this->current_last = this->initial_size - 1;
                this->last_storage--;
            } else {
                this->current_last = static_cast<std::size_t>(current_last_int);
            }

            this->external_storage_size--;
        }
    }

    void pop_front() {
        if (!this->empty()) {
            int current_first_int = this->current_first;
            current_first_int++;

            if (current_first_int >= this->initial_size) {
                this->current_first = 0;
                this->first_storage++;
            } else {
                this->current_first = static_cast<std::size_t>(current_first_int);
            }

            this->external_storage_size--;
        }
    }

};

与循环数组不同的关键在于,动态扩充内存方式不同.分段存储的方式,首先是预先开辟好一个较大的存储空间,填充区块内存时,只需要判定填满就再分配一个新的内存块.当然了,只需要保持内存两端预留好实际的空间既可以做到O(1)的插入.删除只需要偏移暴露给迭代器的指针值就可以.实际上也没必要删除.

迭代器部分,模板式写法,.

    class Iterator {
    private:
        std::size_t current_position;
        Deque<T> *deque;
    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        Iterator() : deque(nullptr), current_position(0) {}
        Iterator(Deque<T> *_deque, std::size_t position) : deque(_deque), current_position(position) {}

        Iterator &operator=(const Iterator &other) {
            this->current_position = other.current_position;
            this->deque = other.deque;
            return *this;
        }

        Iterator &operator+=(const std::size_t &offset) {
            *this = (*this).operator+(offset);
            return *this;
        }

        Iterator &operator-=(const std::size_t &offset) {
            *this = (*this).operator-(offset);
            return *this;
        }

        Iterator operator+(const std::size_t &offset) {
            return Iterator(this->deque, this->current_position + offset);
        }

        Iterator operator-(const std::size_t &offset) {
            return Iterator(this->deque, this->current_position - offset);
        }

        T& operator*() const {
            return (*deque)[current_position];
        }

        Iterator &operator++() {
            return (*this).operator+=(1);
        }

        Iterator &operator--() {
            return (*this).operator-=(1);
        }

        bool operator==(const Iterator &other) {
            return (this->deque == other.deque) && (this->current_position == other.current_position);
        }

        bool operator!=(const Iterator &other) {
            return (this->deque != other.deque) || (this->current_position != other.current_position);
        }
    };

    friend std::ostream &operator<<(std::ostream& out, Deque<T>* source) noexcept {
        if (source == NULL) {
            return out;
        }
        for (auto it = source->begin(); it != source->end(); it.operator++()) {
            out << it.operator*() << " ";
        }
        out << std::endl;
        return out;
    }
    void insert(Iterator it, const T& source) {
        if (it == this->end()) {
            this->push_back(source);
        } else {
            T copy = it.operator*();
            it.operator*() = source;

            for (auto deque_iterator = it.operator++(); deque_iterator != this->end(); deque_iterator.operator++()) {
                T buffer = deque_iterator.operator*();
                deque_iterator.operator*() = copy;
                copy = buffer;
            }

            this->push_back(copy);
        }
    }

    void erase(Iterator it) {
        for (auto deque_iterator = it; deque_iterator != this->end(); deque_iterator.operator++()) {
            *(deque_iterator - 1) = *(deque_iterator);
        }

        this->pop_back();
    }

Q&A

Q1: 解释 deque 和 vector 的主要区别是什么？

A:

• 内存分配：vector 使用单一连续的内存空间来存储元素，而 deque 使用多个分散的内存块。这意味着 deque 可以在两端进行高效的插入和删除操作，而 vector 只能在尾部高效地进行这些操作。
• 插入效率：在 deque 的前端和后端插入或删除元素的操作效率很高，但在中间插入或删除元素效率较低，因为它需要移动多个内存块中的元素。而 vector 在尾部插入和删除元素高效，但在前端或中间进行这些操作效率较低，因为可能需要移动大量元素。
• 随机访问：vector 提供了更快的随机访问性能，因为它使用连续内存，而 deque 由于其分散的内存块，随机访问性能稍低。
• 内存耗费：vector 在扩展时可能会有较大的内存重新分配成本，而 deque 因为是分块存储，所以通常不需要大量的内存重新分配。

Q2: 可以用 deque 实现一个固定大小的滑动窗口吗？如果可以，请演示如何实现。

A: 是的，可以使用 deque 实现一个固定大小的滑动窗口。以下是一个简单的示例：

#include <iostream>
#include <deque>

void slidingWindowMaximum(const std::vector<int>& nums, int k) {
    std::deque<int> window;

    for (size_t i = 0; i < nums.size(); ++i) {
        // 移除窗口左边界之外的元素
        if (!window.empty() && window.front() == i - k) {
            window.pop_front();
        }

        // 保持 `deque` 的递减顺序
        while (!window.empty() && nums[i] > nums[window.back()]) {
            window.pop_back();
        }

        // 添加当前元素的索引
        window.push_back(i);

        // 从窗口开始时输出最大值
        if (i >= k - 1) {
            std::cout << nums[window.front()] << " ";
        }
    }
    std::cout << std::endl;
}

这个函数接受一个整数数组 nums 和一个整数 k 作为窗口大小，然后打印出每次滑动窗口中的最大值。

Q3: 在 deque 的前端插入一个元素时，迭代器会发生什么？

A: 在 C++ STL 中，对于 std::deque，在前端插入元素通常会导致所有迭代器、引用和指针失效。这是因为 deque 可能会在内部进行重新分配，特别是当没有足够的前端空间来容纳新元素时。这与 std::vector 在尾部插入元素时迭代器保持有效的行为不同。

Q4: 在 deque 中使用 [] 操作符和 at() 方法有何区别？

A:

• operator[] 提供对元素的无检查访问，这意味着如果使用超出范围的索引，它不会抛出异常，而是导致未定义行为。
• at() 方法提供边界检查的访问。如果指定的索引超出了 deque 的范围，at() 方法会抛出一个 std::out_of_range 异常。因此，at() 比 operator[] 更安全，但可能会略微降低性能。

使用 at() 方法可以帮助调试中发现越界错误，而 operator[] 在确定不会越界时可以提供更好的性能。

Q5: 解释 deque 的内部工作机制。它是如何实现两端插入和删除操作的高效性的？

A: std::deque 维护了一系列定长数组（称为块或缓冲区），并且有一个中央控制器（通常是指针数组）来管理这些块。每个块可以独立地增长和收缩，这意味着当在两端添加或删除元素时，只有相关联的块受到影响。

• 在前端插入：如果第一个块有空间，则在该块的开始插入新元素。如果没有空间，deque 会分配一个新块并将其链接到现有的块序列中。
• 在后端插入：如果最后一个块有空间，则在该块的末尾插入新元素。如果没有空间，deque 会分配一个新块并将其链接到现有的块序列中。
• 在前端删除：移除第一个块的第一个元素。如果该块变空，则释放该块资源并更新中央控制器。
• 在后端删除：移除最后一个块的最后一个元素。如果该块变空，则释放该块资源并更新中央控制器。

通过这种方式，deque 可以在两端进行高效的插入和删除操作，而不需要移动除了操作点之外的其他元素，这在 vector 中是必须的。

Q6: deque 有多少种构造函数，它们分别是用来做什么的？

A: std::deque 提供了多种构造函数，允许以不同的方式创建 deque 对象：

1. 默认构造函数：创建一个空的 deque。

   std::deque dq;

2. 填充构造函数：创建一个包含给定数量元素的 deque，每个元素都是拷贝自给定的初始值。

   std::deque dq(10, 5); // 10个元素，每个都是5

3. 范围构造函数：使用两个迭代器作为参数，创建一个新的 deque，复制给定迭代器范围内的元素。

   std::vector vec{1, 2, 3, 4, 5};
   std::deque dq(vec.begin(), vec.end());

4. 拷贝构造函数：创建一个新的 deque，为另一个 deque 的拷贝。

   std::deque dq1(10, 5);
   std::deque dq2(dq1); // 拷贝dq1

5. 移动构造函数（C++11 引入）：从另一个 deque 移动元素，这通常涉及移动内部指针，而不是复制元素。

   std::deque dq1(10, 5);
   std::deque dq2(std::move(dq1)); // 移动dq1

6. 初始化列表构造函数（C++11 引入）：使用一个初始化列表来创建 deque。

   std::deque dq{1, 2, 3, 4, 5};

7. 带有分配器的默认构造函数：创建一个空的 deque，但是使用自定义的分配器来分配内存。

   std::allocator alloc;
   std::deque> dq(alloc);

8. 带有分配器的填充构造函数：创建一个包含给定数量元素的 deque，每个元素都是拷贝自给定的初始值，并使用自定义的分配器来分配内存。

   std::allocator alloc;
   std::deque> dq(10, 5, alloc); // 10个元素，每个都是5，使用自定义分配器

9. 带有分配器的范围构造函数：使用两个迭代器作为参数，并使用自定义的分配器来分配内存，创建一个新的 deque，复制给定迭代器范围内的元素。

   std::vector vec{1, 2, 3, 4, 5};
   std::allocator alloc;
   std::deque> dq(vec.begin(), vec.end(), alloc);

10. 带有分配器的拷贝构造函数：创建一个新的 deque，为另一个 deque 的拷贝，并使用自定义的分配器来分配内存。

    std::deque dq1(10, 5);
    std::allocator alloc;
    std::deque> dq2(dq1, alloc); // 拷贝dq1，使用自定义分配器

11. 带有分配器的移动构造函数（C++11 引入）：从另一个 deque 移动元素，并使用自定义的分配器来分配内存。这通常涉及移动内部指针，而不是复制元素。

    std::deque dq1(10, 5);
    std::allocator alloc;
    std::deque> dq2(std::move(dq1), alloc); // 移动dq1，使用自定义分配器

12. 带有分配器的初始化列表构造函数（C++11 引入）：使用一个初始化列表来创建 deque，并使用自定义的分配器来分配内存。

    std::allocator alloc;
    std::deque> dq({1, 2, 3, 4, 5}, alloc);

引用

https://kamacoder.com/