赞
踩
deque 是 stl 的一个关联容器,名叫“双向队列”,何为“双向队列”?其实就是一个数组,但有了数组何必还需双向队列,这是一个高深的问题。
目录
“de” 是 “double end” 的缩写,指双向,双端,“que” ,是 “queue” 指队列,所以顾名思义,“deque” 就是双向队列,可以双向入队,出队的队列,换句话说,就是可以在开头、结尾添加、减少元素的数组。
deque 的实现,离不开 allocator ,即分配器,可以随意分配空间,使 deque 可以无限扩张,又不同于 new ,allocator 在前后可以均可扩张,时间负杂度只有 O(1) 。无需 copy 函数。实现在 <memory/alloctor.h> 头文件的 allocate 函数中:
- _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
- _Tp* allocate(size_t __n) {
- if (__n > allocator_traits<allocator>::max_size(*this))
- __throw_length_error("allocator<T>::allocate(size_t n)"
- " 'n' exceeds maximum supported size");
- if (__libcpp_is_constant_evaluated()) {
- return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
- } else {
- return static_cast<_Tp*>(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp)));
- }
- }
首先引用 deque 头文件,使用 std 库:
- #include <deque>
- using namespace std;
和一般模版类一样创建,1.类型,2.模版,3.变量名:
deque< int> q;
“iterator” 中文名为“迭代器”,访问方式如下:
- for(deque <int>::iterator it = s.begin();it != s.end();++ it)
- {
- cout << *it;
- }
c++11 以后,新增了一种 for 循环语法(如下), vector、list 等容器也可以这么访问:
- for (auto i : v)
- {
-
- }
1.在开头入队:push_front(x);
2.在开头出队:pop_front(x);
3.在结尾入队:push_back(x);
4.在结尾出队:pop_back(x);
“swap” 交换两个 list ,只能用他的内置函数,不能使用直接定义在 std 库中的 swap,如下:
q.swap(temp);
在一个指针插入一个元素:
d.insert(it,x);
清除一个指针指向的元素:
d.erase(it);
你学会了吗?
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。