C++ deque 底层原理及 queue、stack 容器的使用详解

双端队列 (double-ended queue，缩写为deque)是一个容量可以动态变化，并且可以在两端插入或删除的顺序容器。既然它是顺序容器，那么容器中的元素就是按照严格的线性顺序排序，可以使用类似数组的方法访问对应的元素。deque 实际分配的内存数超过容纳当前所有有效元素的数量，因为空闲的空..

Tyler_Zx

7968人浏览 · 2020-05-15 17:30:24

Tyler_Zx · 2020-05-15 17:30:24 发布

简介

双端队列 (double-ended queue，缩写为deque)是一个容量可以动态变化，并且可以在两端插入或删除的顺序容器。既然它是顺序容器，那么容器中的元素就是按照严格的线性顺序排序，可以使用类似数组的方法访问对应的元素。deque 实际分配的内存数超过容纳当前所有有效元素的数量，因为空闲的空间会在增加元素的时候被利用。双端队列提供了类似 vector 的功能，不仅可以在容器末尾，还可以在容器开头高效地插入或删除元素。

底层结构

这里需要简单的了解 deque 的底层结构，从而更好的理解和使用 deque 。deque 是由一段一段的定量连续空间构成。一旦有必要在 deque 的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个 deque 的头端或尾端。deque 的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器结构。

deque 采用一块所谓的 map (不是STL的map容器) 作为主控。map 是一小块连续空间，其中每个元素 (此处称为一个节点，node)都是指针，指向另一段(较大的)连续线性空间，称为缓冲区，而缓冲区才是deque的储存空间主体。

deque 和 vector 的不同点从上述图片就可以体现出来，vector 的存储空间是连续的，而 deque 的存储空间是由若干个连续空间组成的。deque 巧妙的引入了 map 作为主控，让使用者以为使用的空间是完全连续的。这就好比我们使用的笔记本一样，我们不需要为了做笔记而买一个几百页的笔记本，只需要准备若干个小笔记本即可。当一个笔记本使用完毕后，开始使用下一个笔记本。此时，只要对笔记本进行编号就可以正确无误的使用它们了。比如，看完了第二本笔记本的内容，那么还需要继续往下看，那么理所当然的去使用第三本笔记本。

deque 的分段连续空间，维持其"整体连续"假象的这一艰巨的任务，落在了迭代器的 operator++ 和 operator-- 两个运算符重载身上。仔细琢磨上图就很容易理解了。还是以笔记本为例，当看到第二本的末尾时，还需要查看后面的内容，那么就需要找到第三本笔记本。或者是看某一本笔记本时，突然要查阅基础知识 (往前查看内容)。完成这两个操作最重要的就是要知道笔记本的编号。在 deque 中由 map 主控完成这一任务，因为它的存在，迭代器才能找到某一连续空间的前一段或后一段的地址，而这一过程是较为复杂的。deque 的中控器、缓冲区、迭代器的相互关系如下：

适配器概念

适配器(配接器)在STL组件中，扮演者轴承、转换器的角色。adapter这个概念，事实上是一种设计模式。定义如下：将一个class 的接口转换为另一个 class 的接口，使原本因接口不兼容而不能合作的 class，可以一起运作。其中改变容器接口的，我们称之为容器适配器(container adapter)。源自：《STL源码剖析》

下面的 queue 和 stack，其实是一种适配器。它们修饰 deque 的接口而成就出另一种容器风貌。由于 deque 两端都可以完成插入和删除操作，那么如果限制只能在一端完成插入和删除，这样便提供了栈的功能。如果限制只能在一端只能插入，而另一端只能删除，便提供了队列的功能。

std::stack 类是容器适配器，它给予程序员栈的功能—— FILO （先进后出）数据结构。

std::queue 类是容器适配器，它给予程序员队列的功能—— FIFO （先进先出）数据结构。

元素访问

at用于返回位于指定位置 pos 的元素的引用

reference       at( size_type pos );
const_reference at( size_type pos ) const;

使用 at 时，会有有边界检查。若 pos 不在容器范围内，则抛出 std::out_of_range 类型的异常。

operator[]用于返回位于指定位置 pos 的元素的引用

reference       operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;

使用以上形式，不进行边界检查。

#include <deque>
#include <iostream>
 
int main()
{
    std::deque<int> numbers {2, 4, 6, 8};
 
    std::cout << "Second element: " << numbers[1] << '\n';
 
    numbers[0] = 5;
 
    std::cout << "All numbers:";
    for (auto i : numbers) {
        std::cout << ' ' << i;
    }
    std::cout << '\n';
}

输出：
Second element: 4
All numbers: 5 4 6 8

front用于返回到容器首元素的引用

reference front();
const_reference front() const;

back用于返回容器最后一个元素的引用

reference back();
const_reference back() const;

#include <deque>
#include <iostream>
 
int main()
{
    std::deque<char> letters {'o', 'm', 'g', 'w', 't', 'f'};
 
    if (!letters.empty()) {
        std::cout << "The first character is: " << letters.front() << '\n';
        std::cout << "The last character is: " << letters.back() << '\n';
    }  
}

输出：
The first character is o
The last character is f

迭代器

begin() & cbegin()

iterator begin() noexcept;
const_iterator begin() const noexcept;
const_iterator cbegin() const noexcept;

返回指向 deque 首元素的迭代器。若 deque 为空，则返回的迭代器将等于 end()。

end() & cend()

iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cend() const noexcept;

返回指向 deque 末尾元素后一元素的迭代器。此元素表现为占位符，试图访问它导致未定义行为。

#include <iostream>
#include <deque>
#include <string>
 
int main()
{
	std::deque<int> ints {1, 2, 4, 8, 16};
	std::deque<std::string> fruits {"orange", "apple", "raspberry"};
	std::deque<char> empty;
 
	// 求和 deque ints 中的所有整数（若存在），仅打印结果。
	int sum = 0;
	for (auto it = ints.cbegin(); it != ints.cend(); it++)
		sum += *it;
	std::cout << "Sum of ints: " << sum << "\n";
 
	// 打印 deque fruits 中的首个水果，而不检查是否有一个。
	std::cout << "First fruit: " << *fruits.begin() << "\n";
 
	if (empty.begin() == empty.end())
		std::cout << "deque 'empty' is indeed empty.\n";
}

输出：
Sum of ints: 31
First fruit: orange
deque 'empty' is indeed empty.

rbegin() & crbegin()

reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
const_reverse_iterator crbegin() const noexcept;

返回指向逆向 deque 首元素的逆向迭代器。它对应非逆向 deque 的末尾元素。若 deque 为空，则返回的迭代器等于 rend() 。

rend() & crend()

reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;
const_reverse_iterator crend() const noexcept;

返回指向逆向 deque 末元素后一元素的逆向迭代器。它对应非逆向 deque 首元素的前一元素。此元素表现为占位符，试图访问它导致未定义行为。

容量

empty()

[[nodiscard]] bool empty() const noexcept;

检查容器是否无元素，即是否 begin() == end() 。

#include <deque>
#include <iostream>
 
int main()
{
    std::deque<int> numbers;
    std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';
 
    numbers.push_back(42);
    numbers.push_back(13317); 
    std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n';
}

输出：
Initially, numbers.empty(): 1
After adding elements, numbers.empty(): 0

size()

size_type size() const noexcept;

返回容器中的元素数，即 std::distance(begin(), end()) 。

max_size()

size_type max_size() const noexcept;

返回根据系统或库实现限制的容器可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end()) 。

#include <deque>
#include <iostream>
 
int main()
{
    std::deque<int> numbers;
    std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';
 
    numbers.push_back(42);
    numbers.push_back(13317); 
    std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n';
}

输出：
Initially, numbers.empty(): 1
After adding elements, numbers.empty(): 0

shrink_to_fit()

void shrink_to_fit();

请求移除未使用的空间。它是减少使用内存而不更改序列的大小非强制性请求，请求是否达成依赖于实现。

#include <deque>
 
int main() {
    std::deque<int> nums(1000, 42);
    nums.push_front(1);
    nums.pop_front();
 
    nums.clear();
 
    // nums 现在不含项目，但它仍保有分配的内存。
    // 调用 shrink_to_fit 可能会释放任何不使用的内存。
    nums.shrink_to_fit();
}

修改操作

clear()

void clear() noexcept;

从容器擦除所有元素。此调用后 size() 返回零。

insert()

(1)terator insert( const_iterator pos, const T& value );
(2)iterator insert( const_iterator pos, T&& value );
(3)iterator insert( const_iterator pos, size_type count, const T& value );
(4)template< class InputIt >
   iterator insert( const_iterator pos, InputIt first, InputIt last );
(5)iterator insert( const_iterator pos, std::initializer_list<T> ilist );

插入元素到容器中的指定位置。

(1-2) 在 pos 前插入 value 。

(3) 在 pos 前插入 value 的 count 个副本。

(4) 在 pos 前插入来自范围 [first, last) 的元素。

(5) 在 pos 前插入来自 initializer_list ilist 的元素。

所有迭代器，含尾后迭代器，都被非法化。引用亦被非法化，除非 pos == begin() 或 pos == end() ，该情况下它们不被非法化。

emplace()

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

直接于 pos 前插入元素到容器中。通过 std::allocator_traits::construct 构造元素，它典型地用布置 new 在容器所提供的位置原位构造元素。将参数 args... 作为 std::forward<Args>(args)... 转发给构造函数。所有迭代器，含尾后迭代器，都被非法化。引用亦被非法化，除非 pos == begin() 或 pos == end() ，该情况下它们不被非法化。

emplace_back()

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

添加新元素到容器尾。元素通过 std::allocator_traits::construct 构造，它典型地用布置 new 于容器所提供的位置原位构造元素。参数 args... 以 std::forward<Args>(args)... 转发到构造函数。所有迭代器，包含尾后迭代器，都被非法化。没有引用被非法化。

#include <deque>
#include <string>
#include <iostream>
 
struct President
{
    std::string name;
    std::string country;
    int year;
 
    President(std::string p_name, std::string p_country, int p_year)
        : name(std::move(p_name)), country(std::move(p_country)), year(p_year)
    {
        std::cout << "I am being constructed.\n";
    }
    President(President&& other)
        : name(std::move(other.name)), country(std::move(other.country)), year(other.year)
    {
        std::cout << "I am being moved.\n";
    }
    President& operator=(const President& other) = default;
};
 
int main()
{
    std::deque<President> elections;
    std::cout << "emplace_back:\n";
    elections.emplace_back("Nelson Mandela", "South Africa", 1994);
 
    std::deque<President> reElections;
    std::cout << "\npush_back:\n";
    reElections.push_back(President("Franklin Delano Roosevelt", "the USA", 1936));
 
    std::cout << "\nContents:\n";
    for (President const& president: elections) {
        std::cout << president.name << " was elected president of "
                  << president.country << " in " << president.year << ".\n";
    }
    for (President const& president: reElections) {
        std::cout << president.name << " was re-elected president of "
                  << president.country << " in " << president.year << ".\n";
    }
}

输出：
emplace_back:
I am being constructed.
 
push_back:
I am being constructed.
I am being moved.

Contents:
Nelson Mandela was elected president of South Africa in 1994.
Franklin Delano Roosevelt was re-elected president of the USA in 1936.

emplace_front()

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

插入新元素到容器起始。通过 std::allocator_traits::construct 构造元素，它典型地用布置 new 在容器所提供的位置原位构造元素。将参数 args... 作为 std::forward<Args>(args)... 转发给构造函数。

erase()

iterator erase( const_iterator pos );
iterator erase( const_iterator first, const_iterator last );

从容器去除指定的元素。

(1) 移除位于 pos 的元素。

(2) 移除范围 [first; last) 中的元素。

所有迭代器和引用都被非法化，除非被擦除的元素在容器的首或尾，该情况下仅指向被擦除元素的迭代器或引用被非法化。迭代器 pos 必须合法且可解引用。从而不能以 end() 迭代器（合法，但不可解引用）为 pos 的值。若 first==last 则迭代器 first 不必可解引用：擦除空范围是无操作。

#include <deque>
#include <iostream>
 
int main( )
{
    std::deque<int> c{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (auto &i : c) {
        std::cout << i << " ";
    }
    std::cout << '\n';
 
    c.erase(c.begin());
 
    for (auto &i : c) {
        std::cout << i << " ";
    }
    std::cout << '\n';
 
    c.erase(c.begin()+2, c.begin()+5);
 
    for (auto &i : c) {
        std::cout << i << " ";
    }
    std::cout << '\n';
}

输出：
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 6 7 8 9

push_back()

void push_back( const T& value );
void push_back( T&& value );

将给定元素 value 附到容器最后一个元素之后。

(1) 初始化新元素为 value 的副本。

(2) 移动 value 进新元素。

#include <deque>
#include <iostream>
#include <iomanip>
 
int main()
{
    std::deque<std::string> numbers;
 
    numbers.push_back("abc");
    std::string s = "def";
    numbers.push_back(std::move(s));
 
    std::cout << "deque holds: ";
    for (auto&& i : numbers) std::cout << std::quoted(i) << ' ';
    std::cout << "\nMoved-from string holds " << std::quoted(s) << '\n';
}

输出：
deque holds: "abc" "def" 
Moved-from string holds ""

push_front()

void push_front( const T& value );
void push_front( T&& value );

将给定元素 value 附到容器第一个元素之前。

pop_back()

void pop_back();

移除容器的最末元素，在空容器上调用 pop_back 是未定义的。

#include <deque>
#include <iostream>
 
template<class T>
void print(T const & xs)
{
    std::cout << "[ ";
    for(auto && x : xs) {
        std::cout << x << ' ';
    }
    std::cout << "]\n";
}
 
int main()
{
    std::deque<int> numbers;
 
    print(numbers); 
 
    numbers.push_back(5);
    numbers.push_back(3);
    numbers.push_back(4);
 
    print(numbers); 
 
    numbers.pop_back();
 
    print(numbers); 
}

输出：
[ ]
[ 5 3 4 ]
[ 5 3 ]

pop_front()

void pop_front();

移除容器首元素，若容器中无元素，则行为未定义。

resize()

void resize( size_type count );
void resize( size_type count, const value_type& value );

重设容器大小以容纳 count 个元素。若当前大小大于 count ，则减小容器为其首 count 个元素。

若当前大小小于 count ，

(1) 则后附额外的默认插入的元素

(2) 则后附额外的 value 的副本

#include <iostream>
#include <deque>
int main()
{
    std::deque<int> c = {1, 2, 3};
    std::cout << "The deque holds: ";
    for(auto& el: c) std::cout << el << ' ';
    std::cout << '\n';
    c.resize(5);
    std::cout << "After resize up to 5: ";
    for(auto& el: c) std::cout << el << ' ';
    std::cout << '\n';
    c.resize(2);
    std::cout << "After resize down to 2: ";
    for(auto& el: c) std::cout << el << ' ';
    std::cout << '\n';
}

输出：
The deque holds: 1 2 3
After resize up to 5: 1 2 3 0 0
After resize down to 2: 1 2

swap()

void swap( deque& other ) noexcept();

将内容与 other 的交换。不在单个元素上调用任何移动、复制或交换操作。所有迭代器和引用保持合法，尾后迭代器被非法化。

std::erase, std::erase_if (std::deque)

(1)template< class T, class Alloc, class U >
   typename std::deque<T,Alloc>::size_type
       erase(std::deque<T,Alloc>& c, const U& value);
(2)template< class T, class Alloc, class Pred >
   typename std::deque<T,Alloc>::size_type
       erase_if(std::deque<T,Alloc>& c, Pred pred);

(1) 从容器中擦除所有比较等于 value 的元素。等价于

auto it = std::remove(c.begin(), c.end(), value);
auto r = std::distance(it, c.end());
c.erase(it, c.end());
return r;

(2) 从容器中擦除所有满足 pred 的元素。等价于

auto it = std::remove_if(c.begin(), c.end(), pred);
auto r = std::distance(it, c.end());
c.erase(it, c.end());
return r;

#include <iostream>
#include <numeric>
#include <deque>
 
void print_container(const std::deque<char>& c)
{
    for (auto x : c) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}
 
int main()
{
    std::deque<char> cnt(10);
    std::iota(cnt.begin(), cnt.end(), '0');
 
    std::cout << "Init:\n";
    print_container(cnt);
 
    auto erased = std::erase(cnt, '3');
    std::cout << "Erase \'3\':\n";
    print_container(cnt);
 
    std::erase_if(cnt, [](char x) { return (x - '0') % 2 == 0; });
    std::cout << "Erase all even numbers:\n";
    print_container(cnt);
    std::cout << "In all " << erased << " even numbers were erased.\n";
}

输出：
Init:
0 1 2 3 4 5 6 7 8 9 
Erase '3':
0 1 2 4 5 6 7 8 9 
Erase all even numbers:
1 3 7 9
In all 5 even numbers were erased.

std::swap(std::deque)

(1)template< class T, class Alloc >
   void swap( deque<T,Alloc>& lhs, 
           deque<T,Alloc>& rhs );

(2)template< class T, class Alloc >
   void swap( deque<T,Alloc>& lhs, 
           deque<T,Alloc>& rhs ) noexcept();

为 std::deque 特化 std::swap 算法。交换 lhs 与 rhs 的内容。调用 lhs.swap(rhs) 。

stack

top用于返回 stack 中顶元素的引用

reference top();
const_reference top() const;

它是最近推入的元素。此元素将在调用 pop() 时被移除。等效于调用 deque 中的 c.back()，之后的函数都是调用deque中与之功能对应的函数。

empty()检查底层容器是否为空

[[nodiscard]] bool empty() const;

size()返回底层容器中的元素数

size_type size() const;

push()推入给定的元素 value 到栈顶

void push( const value_type& value );
void push( value_type&& value );

emplace()

template< class... Args >
decltype(auto) emplace( Args&&... args );

推入新元素到 stack 顶。原位构造元素，即不进行移动或复制操作。以与提供给函数者准确相同的参数调用元素的构造函数。

等效地调用 c.emplace_back(std::forward<Args>(args)...); 。

pop()从栈顶移除元素

void pop();

swap()交换容器适配器的内容

void swap( stack& other ) noexcept();

#include <stack>
#include <iostream>
 
int main()
{
    std::stack<int>   s;
 
    s.push( 2 );
    s.push( 6 );
    s.push( 51 );
 
    std::cout << s.size() << " elements on stack\n";
    std::cout << "Top element: "
	      << s.top()         // 保留元素在 stack 上
	      << "\n";
    std::cout << s.size() << " elements on stack\n";
    s.pop();
    std::cout << s.size() << " elements on stack\n";
    std::cout << "Top element: " << s.top() << "\n";
 
    return 0;
}

输出：
3 elements on stack
Top element: 51
3 elements on stack
2 elements on stack
Top element: 6

queue

front()返回到 queue 中首个元素的引用

reference front();
const_reference front() const;

此元素将是调用 pop() 时第一个移除的元素。等效于调用deque中的 front() 。

back()返回到 queue 中末尾元素的引用

reference back();
const_reference back() const;

empty()检查底层容器是否为空

[[nodiscard]] bool empty() const;

size()返回底层容器中的元素数

size_type size() const;

push()推入给定的元素 value 到队尾

void push( const value_type& value );
void push( value_type&& value );

emplace()

template< class... Args >
decltype(auto) emplace( Args&&... args );

推入新元素到 queue 结尾。原位构造元素，即不进行移动或复制操作。以与提供给函数者准确相同的参数调用元素的构造函数。

pop()从队首移除元素

void pop();

swap()交换容器适配器的内容

void swap( queue& other ) noexcept();

参考：《STL源码剖析》

https://www.wandouip.com/t5i250718/

向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

云原生

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...