从零开始的 STL 实现记录：Container-3.2

前言

STL 中，deque 是一种双向开口连续线性空间（逻辑上），deque 和 vector 的最大差异，一在于 deque 允许于常数时间内对起头端进行元素的插入或移除操作，二在于 deque 没有所谓容量 (capacity) 观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，功能十分强大；但对应的代价则是：deque 的迭代器与数据结构为了维持其 “整体连续” 的假象，被设计得异常复杂。
———— 《STL源码剖析》侯捷

本节将会分析 deque 的插入与删除操作。

map 及 buffer (node) 的管理

由于 deque 采用分段式存储的方式，将数据存放在分段的缓冲区 ( node ) 中，并使用中控器 ( map ) 进行管理。而 map 与每个 node 本身也是有容量的概念的，在插入操作时必然会引起 map 及 node 的变化，在分析插入操作之前让我们先来分析一下 deque 是如何管理 map 及 node 的。

template <class T>
class deque<T> {

public:  // appendix

    /// @brief 为 node 分配存放元素的缓冲区
    /// @return 返回分配的缓冲区的首地址
    pointer     allocate_node() { return data_allocator::allocate(buffer_size); }

    /// @brief 释放 node 所指向的缓冲区
    /// @param p  缓冲区的首地址
    void        deallocate_node(pointer p) { data_allocator::deallocate(p, buffer_size); }

    /// @brief 分配一个大小为 n 的 map
    /// @param n  map 的大小
    /// @return  返回 map 的首地址
    map_pointer allocate_map(size_type n) { return map_allocator::allocate(n); }

    /// @brief 释放大小为 n 的 map
    /// @param p  map 的首地址
    /// @param n  map 的大小
    void        deallocate_map(map_pointer p, size_type n) { map_allocator::deallocate(p, n); }

    /// @brief 在 map 的尾部添加 nodes_to_add 个节点
    /// @param nodes_to_add 
    void reserve_map_at_back(size_type nodes_to_add = 1) {
        if (nodes_to_add + 1 > map_size_ - (finish_.node - map_)) {
            reallocate_map(nodes_to_add, false);
        }
    }

    /// @brief 在 map 的头部添加 nodes_to_add 个节点
    /// @param nodes_to_add 
    void reserve_map_at_front(size_type nodes_to_add = 1) {
        if (nodes_to_add > static_cast<size_type>(start_.node - map_)) {
            reallocate_map(nodes_to_add, true);
        }
    }

    void        reallocate_map(size_type nodes_to_add, bool add_at_front);

    /// @brief 在 deque 的头部预留 n 个元素的空间
    /// @param n  预留的元素个数
    /// @return  返回头部预留空间的起始迭代器
    iterator    reserve_elements_at_front(size_type n) {
        size_type vacancies = start_.cur - start_.first;
        if (n > vacancies) {
            new_elements_at_front(n - vacancies);
        }
        return start_ - static_cast<difference_type>(n);
    }
    
    /// @brief 在 deque 的尾部预留 n 个元素的空间
    /// @param n  预留的元素个数
    /// @return  返回尾部预留空间的起始迭代器
    iterator    reserve_elements_at_back(size_type n) {
        size_type vacancies = (finish_.last - finish_.cur) - 1;
        if (n > vacancies) {
            new_elements_at_back(n - vacancies);
        }
        return finish_ + static_cast<difference_type>(n);
    }

    void        new_elements_at_front(size_type new_elements);
    void        new_elements_at_back(size_type new_elements);

}

这些函数负责分配及释放 map 与 node 的空间。其中，reallocate_map() 负责在 map 空间不足时重新分配 map 的大小，看一下 reallocate_map() 的实现。

/// @brief 重新分配管控中心大小
/// @tparam T  deque 的元素类型
/// @param nodes_to_add  需要增加的节点个数
/// @param add_at_front  是否在头部增加节点
template <class T>
inline void deque<T>::reallocate_map(size_type nodes_to_add, bool add_at_front)
{
    const size_type old_num_nodes = finish_.node - start_.node + 1;  // 原始的节点个数
    const size_type new_num_nodes = old_num_nodes + nodes_to_add;    // 新的节点个数

    map_pointer new_nstart;

    // 如果原始的节点个数大于新的节点个数的两倍，就将管控中心的节点向中间移动
    // 会出现在一直向头部或尾部插入元素的情况下
    if (map_size_ > 2 * new_num_nodes) {
        // 将 new_nstart 置于中间位置
        new_nstart = map_ + (map_size_ - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
        if (new_nstart < start_.node) {
            tinystl::copy(start_.node, finish_.node + 1, new_nstart);
        }
        else {
            tinystl::copy_backward(start_.node, finish_.node + 1, new_nstart + old_num_nodes);
        }
    }
    // 否则重新分配管控中心
    else {
        // 新的管控中心的节点个数为原始的节点个数的两倍附加头尾两个节点
        const size_type new_map_size = map_size_ + tinystl::max(map_size_, nodes_to_add) + 2;
        map_pointer new_map = allocate_map(new_map_size);
        new_nstart = new_map + (new_map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
        
        // 将原始的管控中心的节点复制到新的管控中心
        tinystl::copy(start_.node, finish_.node + 1, new_nstart);
        // 释放原始的管控中心
        map_allocator::deallocate(map_, map_size_);
        // 更新管控中心的指针和节点个数
        map_ = new_map;
        map_size_ = new_map_size;
    }

    // 更新迭代器
    start_.set_node(new_nstart);
    finish_.set_node(new_nstart + old_num_nodes - 1);
}

reallocate_map 只是重新分配了 map 的大小，具体 map 中指向的每个 node 所需要的空间，还需要 new_elements_at_front() 与 new_elements_at_back() 以下函数负责分配。

/// @brief 在头部分配 n 个元素的空间
/// @tparam T  deque 的元素类型
/// @param new_elements  需要分配的元素个数
template <class T>
inline void deque<T>::new_elements_at_front(size_type new_elements)
{
    THROW_LENGTH_ERROR_IF(max_size() - size() < new_elements, "deque<T> too long");
    const size_type new_nodes = (new_elements + buffer_size - 1) / buffer_size;
    reserve_map_at_front(new_nodes);
    size_type i;
    try {
        for (i = 1; i <= new_nodes; ++i)
            *(start_.node - i) = allocate_node();
    }
    catch (...) {
        for (size_type j = 1; j < i; ++j)
            deallocate_node(*(start_.node - j));
        throw;
    }
}

/// @brief 在尾部分配 n 个元素的空间
/// @tparam T  deque 的元素类型
/// @param new_elements  需要分配的元素个数
template <class T>
inline void deque<T>::new_elements_at_back(size_type new_elements)
{
    THROW_LENGTH_ERROR_IF(max_size() - size() < new_elements, "deque<T> too long");
    const size_type new_nodes = (new_elements + buffer_size - 1) / buffer_size;
    reserve_map_at_back(new_nodes);
    size_type i;
    try {
        for (i = 1; i <= new_nodes; ++i)
            *(finish_.node + i) = allocate_node();
    }
    catch (...) {
        for (size_type j = 1; j < i; ++j)
            deallocate_node(*(finish_.node + j));
        throw;
    }
}

其中，allocate_node() 与 dellocate_node() 是两个用于分配与释放 node 空间的函数，就是简单地调用了 allocate 与 dellocate，根据 deque_buf_size::value 来确定每个 node 要分配多少空间。

/// @brief 确定 deque 的缓冲区大小
/// @tparam T 
template <class T>
struct deque_buf_size {
    static constexpr size_t value = sizeof(T) < 256 ? 4096 / sizeof(T) : 16;
};

static const size_type buffer_size = deque_buf_size<T>::value;

/// @brief 为 node 分配存放元素的缓冲区
/// @return 返回分配的缓冲区的首地址
pointer     allocate_node() { return data_allocator::allocate(buffer_size); }

/// @brief 释放 node 所指向的缓冲区
/// @param p  缓冲区的首地址
void        deallocate_node(pointer p) { data_allocator::deallocate(p, buffer_size); }

插入操作

deque 容器对外提供了许多插入操作的接口，这里我们挑其中的一部分讲解一下。

template <class T>
class deque<T> {

public:

    template <class ...Args>
    void emplace_front(Args&& ...args);

    template <class ...Args>
    void emplace_back(Args&& ...args);

    template <class ...Args>
    iterator emplace(iterator pos, Args&& ...args);

    void push_front(const value_type& value) { emplace_front(value); }
    void push_front(value_type&& value)      { emplace_front(tinystl::move(value)); }

    void push_back(const value_type& value)  { emplace_back(value); }
    void push_back(value_type&& value)       { emplace_back(tinystl::move(value)); }

    template <class ...Args>
    void push_back_aux(Args&& ...args);

    template <class ...Args>
    void push_front_aux(Args&& ...args);
    
    iterator insert(iterator pos, const value_type& value);
    iterator insert(iterator pos, value_type&& value);
    
    void insert(iterator pos, size_type n, const value_type& value);
    
    template <class InputIterator, typename std::enable_if<
        tinystl::is_input_iterator<InputIterator>::value, int>::type = 0>
    void insert(iterator pos, InputIterator first, InputIterator last) {
        insert_dispatch(pos, first, last, iterator_category(first));
    }

}

emplace & push

与 vector 相同，deque 也支持 emplace_back() 与 push_back() 两种不同的插入操作，关于二者的区别，已经在 上一篇博客 中说的十分清除了，这里就不再赘述。让我们直接看它们的实现。

/// @brief 在头部就地构造元素
template <class T>
template <class ...Args>
void deque<T>::emplace_front(Args&& ...args) {
    // 如果头部缓冲区还有空间，就在头部就地构造元素
    if (start_.cur != start_.first) {
        data_allocator::construct(start_.cur - 1, tinystl::forward<Args>(args)...);
        --start_.cur;
    }
    // 否则需要重新分配空间
    else {
        push_front_aux(tinystl::forward<Args>(args)...);
    }
}

/// @brief 在尾部就地构造元素
template <class T>
template <class ...Args>
void deque<T>::emplace_back(Args&& ...args) {
    // 如果尾部缓冲区还有空间，就在尾部就地构造元素
    if (finish_.cur != finish_.last - 1) {
        data_allocator::construct(finish_.cur, tinystl::forward<Args>(args)...);
        ++finish_.cur;
    }
    // 否则需要重新分配空间
    else {
        push_back_aux(tinystl::forward<Args>(args)...);
    }
}

/// @brief 在 pos 处就地构造元素
template <class T>
template <class ...Args>
typename deque<T>::iterator deque<T>::emplace(iterator pos, Args&& ...args) {
    if (pos.cur == start_.cur) {
        emplace_front(tinystl::forward<Args>(args)...);
        return start_;
    }
    else if (pos.cur == finish_.cur) {
        emplace_back(tinystl::forward<Args>(args)...);
        return finish_ - 1;
    }
    return insert_aux(pos, tinystl::forward<Args>(args)...);
}

emplace() 直接在指定位置构造一个元素，如果该位置是首或尾的话直接调用对应的函数，否则需要使用 insert_aux() 进行处理。
在 emplace_back() 与 emplace_front() 中，如果相应位置的缓冲区仍然有空间，就直接构造；否则需要调用 push_xxx_aux() 先重新分配 map 再插入元素。

/// @brief 重新分配 map 并在尾部添加元素
/// @tparam T  元素类型
/// @param ...args  元素的构造参数
template <class T>
template <class... Args>
inline void deque<T>::push_back_aux(Args &&...args)
{
    reserve_map_at_back();
    *(finish_.node + 1) = allocate_node();
    try {
        data_allocator::construct(finish_.cur, tinystl::forward<Args>(args)...);
        finish_.set_node(finish_.node + 1);
        finish_.cur = finish_.first;
    }
    catch (...) {
        deallocate_node(*(finish_.node + 1));
        throw;
    }
}

/// @brief 重新分配 map 并在头部添加元素
/// @tparam T  元素类型
/// @param ...args  元素的构造参数
template <class T>
template <class... Args>
inline void deque<T>::push_front_aux(Args &&...args)
{
    reserve_map_at_front();
    *(start_.node - 1) = allocate_node();
    try {
        start_.set_node(start_.node - 1);
        start_.cur = start_.last - 1;
        data_allocator::construct(start_.cur, tinystl::forward<Args>(args)...);
    }
    catch (...) {
        ++start_;
        deallocate_node(*(start_.node - 1));
        throw;
    }
}

/// @brief 在 pos 处插入 1 个元素
template <class T>
template <class ...Args>
typename deque<T>::iterator deque<T>::insert_aux(iterator pos, Args&& ...args) {
    const auto elem_before = pos - start_;
    // 如果前面的元素比较少，就从前面开始移动
    if (elem_before < (size() >> 1)) {
        emplace_front(front());  // 先在最前方插入一个与头部相同的元素
        auto front1 = start_;  ++front1;
        auto front2 = front1;  ++front2;
        pos = start_ + elem_before;
        auto pos1 = pos;  ++pos1;
        tinystl::copy(front2, pos1, front1);  // 将 [front2, pos1) 区间的元素向前移动一个位置
    }
    // 否则从后面开始移动
    else {
        emplace_back(back());  // 先在最后方插入一个与尾部相同的元素
        auto back1 = finish_;  --back1;
        auto back2 = back1;  --back2;
        pos = start_ + elem_before;
        tinystl::copy_backward(pos, back2, back1);  // 将 [pos, back2) 区间的元素向后移动一个位置
    }
    *pos = value_type(tinystl::forward<Args>(args)...);
    return pos;
}

在 insert_aux() 中，会根据插入位置前后元素的个数选择最优的移动方式。

insert

emplace 与 push 支持在指定位置插入一个元素，却不支持插入多个元素，这一任务由 insert 完成。插入多个元素的操作相对来说较为繁琐，这里仅介绍一部分内容。

/// @brief 在 pos 处插入元素
template <class T>
typename deque<T>::iterator deque<T>::insert(iterator pos, const value_type& value) {
    return emplace(pos, value);
}

/// @brief 在 pos 处插入元素
template <class T>
typename deque<T>::iterator deque<T>::insert(iterator pos, value_type&& value) {
    return emplace(pos, tinystl::move(value));
}

/// @brief 在 pos 处插入 n 个元素
template <class T>
void deque<T>::insert(iterator pos, size_type n, const value_type& value) {
    if (pos.cur == start_.cur) {
        // require_capacity(n, true);
        // auto new_start = start_ - static_cast<difference_type>(n);
        auto new_start = reserve_elements_at_front(n);
        tinystl::uninitialized_fill_n(new_start, n, value);
        start_ = new_start;
    }
    else if (pos.cur == finish_.cur) {
        // require_capacity(n, false);
        // auto new_finish = finish_ + static_cast<difference_type>(n);
        auto new_finish = reserve_elements_at_back(n);
        tinystl::uninitialized_fill_n(finish_, n, value);
        finish_ = new_finish;
    }
    else {
        fill_insert(pos, n, value);
    }
}

可以看出，insert 有多个重载，其中插入一个元素的操作都是直接调用 emplace()；当插入多个元素时，如果位置在头部或尾部就直接使用全局函数 uninitialized_fill_n() 在指定位置填充元素，其他情况则需要调用 fill_insert() 进行处理。

/// @brief 在 pos 处插入 n 个值为 value 的元素
/// @tparam T  元素类型
/// @param pos  插入的位置
/// @param n  插入的元素个数
/// @param value  插入的元素的值
template <class T>
void deque<T>::fill_insert(iterator pos, size_type n, const value_type& value) {
    const auto elem_before = pos - start_;
    const auto len = size();
    auto value_copy = value;

    // 如果前面的元素比较少，就从前面开始移动
    if (elem_before < (len >> 1)) {
        auto old_start = start_;  // 原始的 start_ 的位置
        auto new_start = reserve_elements_at_front(n);  // 插入新元素后的 start_ 的位置
        pos = start_ + elem_before;  // 要插入新元素在 pos 之前

        try {
            // 要填充的元素的个数小于 pos 之前的元素的个数
            if (elem_before >= n) {
                auto start_n = start_ + static_cast<difference_type>(n);
                tinystl::uninitialized_copy(start_, start_n, new_start);  // 复制前半部分
                start_ = new_start;
                tinystl::copy(start_n, pos, old_start);  // 复制后半部分
                tinystl::fill(pos - static_cast<difference_type>(n), pos, value_copy);  // 填充新元素
            }
            else {
                auto mid = tinystl::uninitialized_copy(start_, pos, new_start);  // 复制所有 pos 之前的元素
                tinystl::uninitialized_fill(mid, start_, value_copy);  // 填充前半部分新元素
                start_ = new_start; 
                tinystl::fill(old_start, pos, value_copy);  // 填充剩余的新元素
            }
        }
        catch (...) {
            if (new_start.node != start_.node) destroy_buffer(new_start.node, start_.node - 1);
            throw;
        }

    }
    // 否则从后面开始移动
    else {
        auto old_finish = finish_;  // 原始的 finish_ 的位置
        auto new_finish = reserve_elements_at_back(n);  // 插入新元素后的 finish_ 的位置
        const auto elem_after = len - elem_before;  // pos 之后的元素的个数
        pos = finish_ - elem_after;  // 要插入新元素在 pos 之前

        try {
            if (elem_after > n) {
                auto finish_n = finish_ - static_cast<difference_type>(n);
                tinystl::uninitialized_copy(finish_n, finish_, finish_);  // 复制后半部分
                finish_ = new_finish;
                tinystl::copy_backward(pos, finish_n, old_finish);  // 复制前半部分
                tinystl::fill(pos, pos + static_cast<difference_type>(n), value_copy);  // 填充新元素
            }
            else {
                tinystl::uninitialized_fill(finish_, pos + static_cast<difference_type>(n), value_copy);  // 填充后半部分新元素
                tinystl::uninitialized_copy(pos, finish_, pos + static_cast<difference_type>(n));  // 复制所有 pos 之后的元素
                finish_ = new_finish;
                tinystl::fill(pos, old_finish, value_copy);  // 填充剩余的新元素
            }
        }
        catch (...) {
            if (new_finish.node != finish_.node) destroy_buffer(finish_.node + 1, new_finish.node);
            throw;
        }
    }
}

fill_insert() 函数较为复杂，主要是要根据插入位置前后元素的个数来采取不同的移动策略，这一点在上面的 insert_aux() 中也有所体现。同时，还要根据 n ( 插入元素个数 ) 与 elems_before / back ( 之前或之后的元素个数 ) 之间的关系来进行不同的操作，因此会比较繁琐。但逻辑不是很复杂，画个图就能明白。

删除操作

deque 同样向外提供了一些负责删除元素的接口，以下也列举部分。

template <class T>
class deque<T> {

public:
    void pop_front();
    void pop_back();

    iterator erase(iterator pos);
    iterator erase(iterator first, iterator last);
    void     clear();
}

pop

pop 的逻辑比较简单，只是要额外考虑是否要释放缓冲区的问题。

/// @brief 弹出头部元素
template <class T>
void deque<T>::pop_front() {
    TINYSTL_DEBUG(!empty());
    // 如果头部缓冲区还有元素，就在头部就地销毁元素
    if (start_.cur != start_.last - 1) {
        data_allocator::destroy(start_.cur);
        ++start_.cur;
    }
    // 否则需要释放头部缓冲区
    else {
        data_allocator::destroy(start_.cur);
        ++start_;
        destroy_buffer(start_.node - 1, start_.node - 1);
    }
}

/// @brief 弹出尾部元素
template <class T>
void deque<T>::pop_back() {
    TINYSTL_DEBUG(!empty());
    // 如果尾部缓冲区还有元素，就在尾部就地销毁元素
    if (finish_.cur != finish_.first) {
        --finish_.cur;
        data_allocator::destroy(finish_.cur);
    }
    // 否则需要释放尾部缓冲区
    else {
        --finish_;
        data_allocator::destroy(finish_.cur);
        destroy_buffer(finish_.node + 1, finish_.node + 1);
    }
}

erase

/// @brief 清除 pos 处的元素
template <class T>
typename deque<T>::iterator deque<T>::erase(iterator pos) {
    auto next = pos; ++next;  // 尽量不要使用 pos + 1
    const auto elem_before = pos - start_;
    // 如果 pos 前面的元素比较少，就从前面开始移动
    if (elem_before < (size() >> 1)) {
        tinystl::copy_backward(start_, pos, next);
        pop_front();
    }
    // 否则从后面开始移动
    else {
        tinystl::copy(next, finish_, pos);
        pop_back();
    }
    return start_ + elem_before;
}

/// @brief 清除 [first, last) 内的元素
template <class T>
typename deque<T>::iterator deque<T>::erase(iterator first, iterator last) {
    if (first == start_ && last == finish_) {
        clear();
        return finish_;
    }
    else {
        const auto n = last - first;
        const auto elems_before = first - start_;
        // 如果前面的元素比较少，就从前面开始移动
        if (elems_before < (size() - n) / 2) {
            tinystl::copy_backward(start_, first, last);
            auto new_start = start_ + n;
            data_allocator::destroy(start_.cur, new_start.cur);
            // destroy_buffer(start_.node, new_start.node - 1);
            start_ = new_start;
        }
        // 否则从后面开始移动
        else {
            tinystl::copy(last, finish_, first);
            auto new_finish = finish_ - n;
            data_allocator::destroy(new_finish.cur, finish_.cur);
            // destroy_buffer(new_finish.node + 1, finish_.node);
            finish_ = new_finish;
        }
        return start_ + elems_before;
    }
}

erase() 函数同样会根据前后元素个数的关系来确定最佳的移动方式，也有两个重载，分别用于消除指定位置与区间的元素。当传给 erase() 的参数恰好是整个 deque 的区间时，会调用 clear()，clear() 的功能也已经在上一篇分析过，这里就不再赘述。