C++STL序列容器deque

C++STL序列容器

• deque
• • operator=
• Iterators
• • begin,rbegin,cbegin,crbegin
  • end,rend,cend,crend
• Capacity
• • size
  • max_size
  • resize
  • empty
  • shrink_to_fit（C++11）
• Element access
• • operator[]
  • at
  • front
  • back
• Modifiers
• • assign
  • push_back
  • push_front
  • pop_back
  • pop_front
  • insert
  • erase
  • swap
  • clear
  • emplace（C++11）
  • emplace_front（C++11）
  • emplace_back(C++11)
• Allocator
• • get_allocator

作为 cppreference以及 cplusplus的补充说明笔记。记录使用STL过程中cppreference文档示例没有举例的地方，以及重要知识点总结。

deque

双端队列，非连续存储，索引访问需要指针解引用两次。
随机访问 - 常数 O(1)
在末尾或开头插入或删除元素 - 常数 O(1)
元素的插入或移除 - 线性 O(n)

template<
    class T,
    class Allocator = std::allocator
> class deque;

operator=

copy (1)	deque& operator= (const deque& x);
move (2)	deque& operator= (deque&& x);
initializer list (3)	deque& operator= (initializer_list il);

Iterators begin,rbegin,cbegin,crbegin end,rend,cend,crend Capacity size

返回元素数

size_type size() const noexcept;

max_size

返回deque能容纳的最大值

size_type max_size() const noexcept;

resize

n小于size取前n个，n大于size则在队尾插入元素直到满足n，可指定初始化值，否则采用默认构造函数。

void resize (size_type n);
void resize (size_type n, const value_type& val);

empty

return size==0

bool empty() const noexcept;

shrink_to_fit（C++11）

交还未用内存以适应size大小，不会更改size大小

 void shrink_to_fit();

Element access operator[]

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

at

边界检查

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

front

      reference front();
const_reference front() const;

back

      reference back();
const_reference back() const;

Modifiers assign

range (1)	template  void assign (InputIterator first, InputIterator last);
fill (2)	void assign (size_type n, const value_type& val);
initializer list (3)	void assign (initializer_list il);

push_back

size增加1

void push_back (const value_type& val);
void push_back (value_type&& val);

push_front

size增加1

void push_front (const value_type& val);
void push_front (value_type&& val);

pop_back

size减一

void pop_back();

pop_front

void pop_front();

insert

single element (1)	iterator insert (const_iterator position, const value_type& val);
fill (2)			iterator insert (const_iterator position, size_type n, const value_type& val);
range (3)			template  
					iterator insert (const_iterator position, InputIterator first, InputIterator last);
move (4)			iterator insert (const_iterator position, value_type&& val);
initializer list (5)	iterator insert (const_iterator position, initializer_list il);

erase

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

swap

void swap (deque& x);

clear

void clear() noexcept;

emplace（C++11）

template 
  iterator emplace (const_iterator position, Args&&... args);

emplace_front（C++11）

template 
  void emplace_front (Args&&... args);

emplace_back(C++11)

template 
  void emplace_back (Args&&... args);

Allocator get_allocator

allocator_type get_allocator() const noexcept;