欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

c++之stl_deque

程序员文章站 2024-02-12 22:19:28
...

c++之stl_deque

一、deque的内存结构

经查阅,deque容器并没有在c#中实现,c#中与其接近的容器是LinkedList,功能相似,但是内部结构完全不同。deque的结构相对vector、list复杂一些,并不是完全连续的,而是一段一段的,虽然底层也是c风格数组。

  1. 优点:
    • 随机存储。
    • 双向操作。
    • 在容器内部插入、删除操作效率优于vector,但没有list高效。
  2. 缺点:
    • 内存占用高。不仅要维护许多buffer,还要维护一个指针数组map。

接下来看看deque是怎么设计的。

c++之stl_deque

  1. deque需要一个指针数组作为控制中心map,这个map可以理解为存储指针的vector,它也可以动态扩容。为了能够更好的双向操作,两端都会预留出空位,方便插入数据。
  2. deque真正存储数据的地方是buffer。一个buffer的大小是固定的,当一个buffer无法再装数据的时候,会向map申请一个新的“节点”,重新分配一块内存给新的buffer使用,这个节点指针便指向新的buffer。
  3. deque的迭代器。由于deque的内存并非完全连续,为了给使用者造成连续空间的错觉,更容易使用,迭代器的设计是非常重要的。迭代器需要4根指针,cur、first、last、node(指针的指针)。cur指向当前元素(start 指向首元素,finish 指向末元素);first指向buffer首元素,last指向buffer末元素;node则是指向map中的元素。

二、具体实现

1. deque的迭代器

struct deque_iterator
{
    // ......
    // ptr *T
    // map_ptr **T
    ptr current;
    ptr first;
    ptr last;
    map_ptr node;

    ref operator*() const;
    ref operator->() const;
    size_type operator-(const self &ths);
    bool operator==(const self &ths) const;
    bool operator!=(const self &ths) const;
    self &operator++();
    self &operator--();
    self &operator+=(size_type n);
    ref operator[](size_type n);
    void set_node(map_ptr new_node);//跨buffer操作
};
  1. ++、–操作符需要考虑2种情况。第一种,在同一个buffer中,这种情况与vector类似,直接移动cur指针即可;第二种,跨buffer操作,存在越界的问题,需要进行边界检查,通过set_node方法移动迭代器,即将迭代器中的node指向map中的对应位置,是+、-操作,map内存是连续的。
  2. []、+=操作符同++、–,但是要复杂一些,需要根据buffer_size计算node在map中的位置,因为是随机存储,可能一下子跨好几个buffer。而++、–操作最多只会移动到相邻的buffer。
  3. 实现了反向迭代器,详细请看deque_reverse_iterator

2. deque的构造、析构

  1. 构造

deque需要一个map作为buffer的控制中心,map_size(map的大小)默认为8。确定迭代器start、finish的位置,决定buffer_size的大小,创建buffer。具体参见create_new_map_and_buffers方法。

  1. 析构

map、buffer都是指针类型,析构的时候需要delete。

3. deque的常用方法

void push_front(const value_type &val);
void push_back(const value_type &val);
iterator insert(iterator position, const value_type &val);
void pop_back();
void pop_front();
  1. 扩容。空间不足的情况有两种,一种是,buffer不够用了,map有多余空间,这时候申请新的buffer就能解决。另一种是map不够用了,这时候就需要,重新分配新map,进行浅拷贝

4. 完整代码

#if !defined(_M_DEQUE_)
#define _M_DEQUE_

#include <memory>

namespace learnCpp
{
template <typename T, size_t buf_size = 0>
class deque_iterator
{
  public:
    typedef T value_type;
    typedef T *ptr;
    typedef T &ref;
    typedef size_t size_type;
    typedef T **map_ptr;
    typedef deque_iterator self;

    ptr current;
    ptr first;
    ptr last;
    map_ptr node;

  public:
    size_type buffer_size() { return deque_buffer_size(buf_size, sizeof(T)); }

    size_type deque_buffer_size(size_type n, size_type elem)
    {
        return n != 0 ? n : (elem < 512 ? size_type(512 / elem) : size_type(1));
    }

    ref operator*() const
    {
        return *current;
    }

    ref operator->() const
    {
        return &(operator*());
    }

    size_type operator-(const self &ths)
    {
        //  med elements size    last - first - 1     last elements size      first elements size
        return buffer_size() * (node - ths.node - 1) + (current - first) + (ths.last - ths.current);
    }

    bool operator==(const self &ths) const
    {
        return current == ths.current;
    }

    bool operator!=(const self &ths) const
    {
        return !(*this == ths);
    }

    //先++,后判断
    self &operator++()
    {
        ++current;
        if (current == last)
        {
            set_node(node + 1);
            current = first;
        }
        return *this;
    }

    self operator++(int)
    {
        self tmp = *this;
        ++*this;
        return tmp;
    }

    //先判断,后 --
    self &operator--()
    {
        if (current == first)
        {
            set_node(node - 1);
            current = last;
        }
        --current;
        return *this;
    }

    self operator--(int)
    {
        self tmp = *this;
        --*this;
        return tmp;
    }

    self &operator+=(size_type n)
    {
        size_type offset = n + (current - first);
        //offset in this buffer
        if (offset >= 0 && offset < buffer_size())
            current += n;
        else
        {
            // size_type new_offset = offset > 0 ?
            // offset / buffer_size: //greater than zero;
            // -(offset-1)/buffer_size -1;//lower than zero;
            size_type node_offset = offset / buffer_size();
            set_node(node + node_offset);
            current = first + offset - node_offset * buffer_size();
        }
        return *this;
    }

    ref operator[](size_type n)
    {
        return *(*this + n);
    }

    self operator+(size_type n)
    {
        self tmp = *this;
        return tmp += n;
    }

    self operator-(size_type n)
    {
        self tmp = *this;
        return tmp += -n;
    }

    void set_node(map_ptr new_node)
    {
        node = new_node;
        first = *new_node;
        last = first + buffer_size();
    }
};

template <class Iterator, typename T>
class deque_reverse_iterator
{
  protected:
    Iterator current;

  public:
    typedef T value_type;
    typedef size_t size_type;
    typedef deque_reverse_iterator self;

  public:
    deque_reverse_iterator(Iterator x)
        : current(x)
    {
    }

    Iterator base() const
    {
        return current;
    }

    value_type &operator*() const
    {
        Iterator tmp = current;
        return *--tmp;
    }

    value_type *operator->() const
    {
        return &(operator*());
    }

    bool operator==(const self &x) const
    {
        return base() == x.base();
    }

    bool operator!=(const self &x) const
    {
        return !(*this == x);
    }

    self &operator++()
    {
        --current;
        return *this;
    }

    self operator++(int)
    {
        self tmp = *this;
        --current;
        return tmp;
    }

    self &operator--()
    {
        ++current;
        return *this;
    }

    self operator--(int)
    {
        self tmp = *this;
        ++current;
        return tmp;
    }

    self operator+(size_type n)
    {
        return self(current - n);
    }

    self &operator+=(size_type n)
    {
        current = current - n;
        return *this;
    }

    self operator-(size_type n)
    {
        return self(current + n);
    }

    value_type &operator[](size_type n)
    {
        return *(*this + n);
    }
};

template <class T, size_t buf_size = 0>
class m_deque
{
  public:
    typedef T value_type;
    typedef deque_iterator<T, buf_size> iterator;
    typedef deque_reverse_iterator<iterator, T> reverse_iterator;
    typedef T *ptr;
    typedef T &ref;
    typedef size_t size_type;

  protected:
    typedef ptr *map_ptr;

  protected:
    size_type map_size;
    map_ptr map;
    iterator start;
    iterator finish;

  public:
    m_deque()
    {
        create_new_map_and_buffers(0);
    }

    m_deque(const size_type n, const value_type &val)
    {
        create_new_map_and_buffers(n);
        for (size_t i = 0; i < n; i++)
        {
            start[i] = val;
        }
    }

    ~m_deque()
    {
        clear();
        for (map_ptr i = start.node; i <= finish.node; i++)
        {
            delete[] * i;
        }
        delete[] map;
    }

    size_type buffer_size()
    {
        return start.buffer_size();
    }

    iterator begin()
    {
        return start;
    }

    iterator end()
    {
        return finish;
    }

    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }

    size_type max_size()
    {
        return finish - start;
    }

    bool empty() const
    {
        return start == finish;
    }

    ref front()
    {
        return *start;
    }

    ref back()
    {
        iterator tmp = finish;
        --tmp;
        return *tmp;
    }

    void push_front(const value_type &val)
    {
        if (start.current != start.first)
        {
            // std::_Construct(start.current - 1,val);
            *(start.current - 1) = val;
            --start.current;
        }
        else
            push_front_aux(val);
    }

    void push_back(const value_type &val)
    {
        if (finish.current != finish.last - 1)
        {
            *(finish.current) = val;
            ++finish.current;
        }
        else
            push_back_aux(val);
    }

    iterator insert(iterator position, const value_type &val)
    {
        // 插入点在首尾,直接交给push_front、push_back去做
        // push_front、push_back里也会处理两种情况,有空间、无空间。
        if (position.current == start.current)
        {
            push_front(val);
            return start;
        }
        else if (position.current == finish.current)
        {
            push_back(val);
            iterator tmp = finish;
            return --tmp;
        }
        // 插入点不在首尾,在内部。
        // 调用辅助方法
        else
        {
            return insert_aux(position, val);
        }
    }

    void pop_back()
    {
        std::destroy_at(finish.current);
        --finish;
    }

    void pop_front()
    {
        std::destroy_at(start.current);
        ++start;
    }

    void clear()
    {
        for (map_ptr i = start.node + 1; i < finish.node; i++)
        {
            std::destroy(*i, *i + buffer_size());
            // delete[] * i;
        }

        if (start.node != finish.node)
        {
            std::destroy(start.current, start.last);
            std::destroy(finish.first, finish.current);
            // delete[] start.first;
            // delete[] finish.first;
        }
        else
        {
            std::destroy(start.current, finish.current);
        }

        start = finish;
        // delete[] map;
    }

  private:
    void create_new_map_and_buffers(size_type n)
    {
        size_type num_nodes = n / buffer_size() + 1;
        map_size = std::max(size_type(8), num_nodes + 2);
        map = new ptr[map_size];

        map_ptr tmp_start = map + (map_size - num_nodes) / 2;
        map_ptr tmp_finish = tmp_start + num_nodes - 1;

        for (map_ptr cur = tmp_start; cur <= tmp_finish; cur++)
        {
            *cur = new value_type[buffer_size()];
        }

        start.set_node(tmp_start);
        start.current = start.first;
        finish.set_node(tmp_finish);
        finish.current = finish.first + n % buffer_size();
    }

    iterator insert_aux(iterator pos, const value_type &val)
    {
        size_type index = pos - start;
        if (index < max_size() / 2)
        {
            push_front(front());

            iterator first = start + 1;
            for (iterator i = start + 2; i != pos; i++)
            {
                *first = *i;
                ++first;
            }
            *(pos - 1) = val;
            return ++pos;
        }
        else
        {
            push_back(back());

            reverse_iterator last = finish - 1;
            for (reverse_iterator i = finish - 2; i != pos; i++)
            {
                *last = *i;
                ++last;
            }
            *(pos) = val;
            return --pos;
        }
    }

    void push_front_aux(const value_type &val)
    {
        value_type val_copy = val;

        if (start.node - map < 1)
        {
            map_size *= 2;
            expand(map_size);
        }

        *(start.node - 1) = new value_type[buffer_size()];

        start.set_node(start.node - 1);
        start.current = start.last - 1;
        *start.current = val_copy;
    }

    // 当push_back时,空间不足的时候,就调用这个辅助函数
    void push_back_aux(const value_type &val)
    {
        value_type val_copy = val;

        // map空间不足
        if (map_size - (finish.node - map) < 2)
        {
            map_size *= 2;
            expand(map_size);
        }

        // buffer空间不足
        *(finish.node + 1) = new value_type[buffer_size()];

        *finish.current = val_copy;
        finish.set_node(finish.node + 1);
        finish.current = finish.first;
    }

    // 当map空间不足时
    void expand(size_type _size)
    {
        _size = _size > 0 ? _size : 8;
        map_ptr new_map = new ptr[_size];

        map_ptr tmp_start = (new_map + (_size - max_size() / buffer_size() + 1) / 2);
        map_ptr tmp_finish = tmp_start + (finish.node - start.node); /* + size() / buffer_size(); */

        // 对buffer指针进行拷贝
        map_ptr j = start.node;
        for (map_ptr i = tmp_start; i <= tmp_finish; i++)
        {
            *i = *j;
            ++j;
        }

        // 释放旧map
        delete[] map;
        // map = NULL;
        // 拷贝map指针
        map = new_map;

        // 更新迭代器
        start.set_node(tmp_start);
        finish.set_node(tmp_finish);
    }

    // deque会根据插入点左右元素的个数,进行拷贝操作。
    // 哪边元素少,就往哪边推动。
    iterator insert_aux(iterator pos, const value_type &val)
    {
        // 判断元素个数
        size_type index = pos - start;
        if (index < max_size() / 2)
        {
            // 先完成首元素的拷贝,当空间不足时,自动完成扩容。
            push_front(front());
            // 使用正向迭代器,对元素进行逐个拷贝,向左推动
            iterator first = start + 1;
            for (iterator i = start + 2; i != pos; i++)
            {
                *first = *i;
                ++first;
            }
            // 完成拷贝后,原pos的位置就空出来了,由于push,前面多了一个数据,所以现pos位置应该减一
            *(pos - 1) = val;
            return ++pos;
        }
        else
        {
            push_back(back());
            // 使用反向迭代器,将元素往右推动。
            reverse_iterator last = finish - 1;
            for (reverse_iterator i = finish - 2; i != pos; i++)
            {
                *last = *i;
                ++last;
            }
            *(pos) = val;
            return ++pos;
        }
    }
};
} // namespace learnCpp

#endif // _M_DEQUE_

三、测试

1. 测试代码

环境:mingw64
#include "m_deque.h"
#include "m_queue.h"
#include "m_stack.h"
#include <iostream>
#include <stack>
#include <deque>

using namespace std;
using namespace learnCpp;

int times = 10000;
int pp_time = 45;

void test4()
{
    m_deque<string> q;

    for (size_t i = 0; i < times; i++)
    {
        q.push_back(to_string(i));
    }

    auto ite = q.begin();
    for (size_t i = 0; i < pp_time; i++)
    {
        ite++;
    }

    q.insert(ite, "haha");

    deque<string> stl_q;

    for (size_t i = 0; i < times; i++)
    {
        stl_q.push_back(to_string(i));
    }

    auto stl_ite = stl_q.begin();
    for (size_t i = 0; i < pp_time; i++)
    {
        stl_ite++;
    }

    stl_q.insert(stl_ite, "haha");

    bool equal_r = true;
    auto m_ite = q.rbegin();
    for (auto i = stl_q.rbegin(); i != stl_q.rend(); i++)
    {
        if (*m_ite != *i)
        {
            cout << "not equal " << *m_ite << "," << *i << endl;
            equal_r = false;
            break;
        }
        m_ite++;
    }
    cout << "reverse equal ? " << equal_r << endl;

    bool equal_f = true;
    auto m_f_ite = q.begin();
    for (auto i = stl_q.begin(); i != stl_q.end(); i++)
    {
        if (*m_f_ite != *i)
        {
            cout << "not equal " << *m_f_ite << "," << *i << endl;
            equal_f = false;
            break;
        }
        m_f_ite++;
    }
    cout << "forward equal ? " << equal_f << endl;

    cout << "m_deque size: " << q.max_size() << endl;
    cout << "stl_deque size: " << stl_q.size() << endl;
}

int main(int argc, char const *argv[])
{
    test4();
    return 0;
}

2. 运行结果

c++之stl_deque