【STL基础】序列式容器之deque

参照自文档http://www.cplusplus.com/reference/array/，教程http://c.biancheng.net/view/6688.html，和书籍《STL源码剖析》（侯捷）

目录

• （一）初始化
• （二）迭代器函数
• （三） 容量函数
• （四）元素访问函数
• （五）修改器函数
• （六）重载运算符
• （七）示例

定义：

template < class T, class Alloc = allocator<T> > class deque;

vector是单向开口的连续线性空间，而deque则是双向开口的。

deque 容器擅长在序列两端添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

deque没有容量的概念，因为它是动态地将一段新的空间链接起来的，它不会像vector那样旧空间不足然后重新配置一块更大的空间。

使用需要引入头文件和使用std命名空间。

（一）初始化

方式一：创建了一个空的 deque容器，并未分配空间。

std::deque<int> values;

方式二：创建并指定元素个数，此时这十个元素都被初始化为0。

std::deque<int> values(10);

方式三：创建并指定元素个数和初始化值，此时这十个元素都被初始化为5。

std::deque<int> values(10, 5);

方式四：直接拷贝其他的deque。

std::deque<char> value1(5);
std::deque<char> value2(value1);

也可以选择性复制一部分元素（利用迭代器函数）。

std::array<int, 5>arr{11,12,13,14,15 };
std::deque<int>d(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

（二）迭代器函数

• begin()：返回指向容器中第一个元素的正向迭代器。
• end()：返回指向容器最后一个元素后一个位置的正向迭代器。
• rbegin()：返回指向最后一个元素的正向迭代器。
• rend()：返回指向第一个元素前一个位置的正向迭代器。
• cbegin()：和 begin() 功能相同，只不过在其基础上增加了 const 属性，不能用于修改元素。
• cend()、crbegin()、crend()：依此类推
  
  前缀带c的返回的迭代器是const类型，因此只能通过它读取而不能修改元素。另外，空的deque不能使用迭代器。当向 deque 容器添加元素时，deque 容器会申请更多的内存空间，同时其包含的所有元素可能会被复制或移动到新的内存地址（原来占用的内存会释放），这会导致之前创建的迭代器失效。

（三） 容量函数

• size()：返回容器中当前元素的数量，其值始终等于初始化 array 类的第二个模板参数 N。
• max_size()：返回元素个数的最大值。这通常是一个很大的值，一般是 2^32-1，所以我们很少会用到这个函数。
• resize()：改变实际元素的个数。
• capacity()：返回当前容量。
• empty()：判断容器是否为空。
• reserve()：增加容器的容量。
• shrink_to_fit()：将内存减少到等于当前元素实际所使用的大小。

（四）元素访问函数

• at(n)：使用经过边界检查的索引访问元素，获取指定位置的元素引用。当传给 at() 的索引会造成越界时，会抛出std::out_of_range异常。
• front()：返回第一个元素的引用，可以用于修改元素，但是也只能修改第一个元素（因为它是引用。。。）。
• back()：返回最后一个元素的引用，可以用于修改元素。

和 vector 容器不同，deque 容器没有提供 data() 成员函数，同时 deque 容器在存储元素时，也无法保证其会将元素存储在连续的内存空间中，因此尝试使用指针去访问 deque 容器中指定位置处的元素，是非常危险的。

（五）修改器函数

• assign()：用新元素替换原有内容。
• push_back()：在序列的尾部添加一个元素。
• push_front()：在序列的首部添加一个元素。
• pop_back()：移除序列尾部的元素。该容器的大小（size）会减 1，但容量（capacity）不会发生改变。
• pop_front()：移除序列首部的元素。
• insert()：在指定的位置插入一个或多个元素，具体用法如下：

//insert()源码
//从position开始，插入n个初值为x的元素
iterator insert(iterator position, const value_type& x){
    if(position.cur == start.curr){
        //如果插入点再最前端，则直接交给push_front()
        push_front(x);
        return start;
    }
    else if(position.cur == finish.curr){
        //如果插入点再最末端，则直接交给push_back()
        push_back(x);
        iterator tmp = finish;
        --tmp;
        return tmp;
    }
    else {
        return insert_aux(position, x);
    }
}
iterator deque<T, Alloc, BuffSize>::insert_aux(iterator pos, const value_type& x){
    difference_type index = pos - start;//插入点之前的元素个数
    value_type x_copy = x;
    if(index < size() / 2){
        //如果插入点前的元素比较少
        //在deque的最前端加入与第一个元素相同的元素，然后将插入点前的全部元素往前拷贝一份
        push_front(front());
        iterator front1 = start;
        ++front1;
        iterator front2 = front1;
        ++front2;
        pos = start + index;
        iterator pos1 = pos;
        ++pos1;
        copy(front2, pos1, front1);
    }
    else{
        push_back(back());
        iterator back1 = finish;
        --back1;
        iterator back2 = back1;
        --back2;
        pos = start + index;
        copy_backward(pos, back2, back1);
    }
    *pos = x_copy;
    return pos;
}
//使用示例
std::deque<int> d{ 1,2 };
//第一种格式用法
d.insert(d.begin() + 1, 3);//{1,3,2}
//第二种格式用法
d.insert(d.end(), 2, 5);//{1,3,2,5,5}
//第三种格式用法
std::array<int, 3>test{ 7,8,9 };
d.insert(d.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
//第四种格式用法
d.insert(d.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}
for (int i = 0; i < d.size(); i++) {
    cout << d[i] << " ";
}

• erase()：移除一个元素或一段元素。

//erase()源码
//1.清除删除位置为pos的元素
iterator erase(iterator pos){
    iterator next = pos;
    ++next;
    difference_type index = pos - start;//清除点前的元素个数
    if(index < (size() >> 1)){
        //如果清除点前的个数比较少
        //移动前面的元素
        copy_backward(start, pos, next);
        pop_front();
    }
    else{
        //如果清除点前的个数比较少
        //移动后面的元素
        copy(next, finish, pos);
        pop_back();
    }
    return start + index;
}
//2.清除[first, last)间的所有元素
iterator erase(iterator first, iterator last){
    if(first == start && last == finish){
        //如果整个区间都要清除
        clear();
        return finish;
    }
    else{
        difference_type n = last - first;//区间长度
        difference_type elems_before = first - start;//清除区间前面有多少个元素
        if(elem_before < (size() - n) / 2){
            //如果前方的元素比较少
            copy_backward(start, first, last);//后移覆盖清除空间
            iterator new_start = start + n;//deque的新起点
            //释放掉前面的元素
            destroy(start, new_start);
            for(map_pointer cur = start.node; cur < new_start.node ++cur){
                data_allocator::deallocate(*cur, buffer_size());
                start = new_start;
            }
        }
        else{
            //如果后方的元素比较少
            copy(last, finish, first);//前移覆盖清除空间
            iterator new_finish = finish - n;//deque的新尾点
            //释放掉后面的元素
            destroy(new_finish, finish);
            for(map_pointer cur = new_finish.node + 1; cur < finish.node ++cur){
                data_allocator::deallocate(*cur, buffer_size());
                start = new_finish;
            }
        }
        return start + elems_before;
    }
}
//使用示例
vector<int>demo1{ 1,2,3,4,5 };
auto iter = demo1.erase(demo1.begin() + 1);//删除元素 2
cout << endl << *iter << endl;//iter迭代器指向元素 3
vector<int>demo2{ 1,2,3,4,5 };
iter = demo2.erase(demo2.begin()+1, demo2.begin()+3);//删除元素2和3

• swap()：交换两个容器的所有元素。
• clear()：移除所有的元素，容器大小变为 0。

//clear()源码
void clear(){
		erase(begin(), end());
}

• emplace()：在指定位置之前生成一个新的元素。（与insert()区分开来）
• emplace_back()：在序列尾部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
• emplace_front()：在序列尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。

（六）重载运算符

• deque可以通过运算符[]以下标的形式访问元素。

（七）示例

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    //初始化一个空deque容量
    deque<int>d;
    //向d容器中的尾部依次添加 1，2,3
    d.push_back(1); //{1}
    d.push_back(2); //{1,2}
    d.push_back(3); //{1,2,3}
    //向d容器的头部添加 0 
    d.push_front(0); //{0,1,2,3}
    //调用 size() 成员函数输出该容器存储的字符个数。
    printf("元素个数为：%d\n", d.size());
   
    //使用迭代器遍历容器
    for (auto i = d.begin(); i < d.end(); i++) {
        cout << *i << " ";
    }
    cout << endl;
    return 0;
}

【STL基础】序列式容器之deque

原文：https://www.cnblogs.com/echizen/p/13966505.html