C++STL序列容器05-forward

C++STL序列容器

• forward_list（c++11）
• • (constructor)
  • (destructor)
  • operator=
• Iterators
• • before_begin
  • cbefore_begin
  • begin
  • cbegin
  • end
  • cend
• Capacity
• • empty
  • max_size
• Element access
• • front
• Modifiers
• • assign
  • emplace_front
  • push_front
  • pop_front
  • emplace_after
  • insert_after
  • erase_after
  • swap
  • resize
  • clear
• Operations
• • splice_after
  • remove
  • remove_if
  • unique
  • merge
  • sort
  • reverse
• Observers
• • get_allocator

forward_list（c++11）

1. 单链表实现
2. 允许在序列内的任何位置进行恒定时间插入和删除操作。（比单纯单链表插入删除快一些）
3. 与数组、向量和双端队列相比，通常在容器内任何位置插入、提取和移动元素表现更好。
4. 与双向链表比，插入和删除元素更有效
5. 主要缺点：无法随机访问、且需要指针空间
6. 无size方法

(constructor)

default (1)	
explicit forward_list (const allocator_type& alloc = allocator_type());

fill (2)	
explicit forward_list (size_type n);
explicit forward_list (size_type n, const value_type& val,const allocator_type& alloc = allocator_type());

range (3)	
template 
  forward_list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
  
copy (4)	
forward_list (const forward_list& fwdlst);
forward_list (const forward_list& fwdlst, const allocator_type& alloc);

move (5)	
forward_list (forward_list&& fwdlst);
forward_list (forward_list&& fwdlst, const allocator_type& alloc);

initializer list (6)	
forward_list (initializer_list il,const allocator_type& alloc = allocator_type());

(destructor)

~forward_list();

operator=

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

Iterators

只有六个

before_begin

返回指向容器中第一个元素之前位置的迭代器。

      iterator before_begin() noexcept;
const_iterator before_begin() const noexcept;

cbefore_begin

const_iterator cbefore_begin() const noexcept;

begin

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

cbegin

const_iterator cbegin() const noexcept;

end

如果容器为空，则此函数返回forward_list::begin 相同的值。

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

cend

const_iterator cend () const noexcept;

Capacity empty

return size==0

bool empty() const noexcept;

max_size

forward_list理论上所能存储的最大个数。

size_type max_size () const noexcept;

Element access front

返回第一个元素的引用。

      reference front();
const_reference front() const;

Modifiers assign

将新内容分配给 forward_list 容器，替换其当前内容，并相应地修改其大小。

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);

emplace_front

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

push_front

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

pop_front

void pop_front();

emplace_after

删除位置元素之后插入元素。返回删除元素的下一个元素的迭代器。

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

insert_after

依旧是位置元素之后。

(1)	
iterator insert_after ( const_iterator position, const value_type& val );
(2)	
iterator insert_after ( const_iterator position, value_type&& val );
(3)	
iterator insert_after ( const_iterator position, size_type n, const value_type& val );
(4)	
template 
iterator insert_after ( const_iterator position, InputIterator first, InputIterator last );
(5)	
iterator insert_after ( const_iterator position, initializer_list il );

erase_after

移除单个元素**（位置之后的元素）或一系列元素（position,last）（开区间）**，返回最后删除元素的下一个元素的迭代器。

iterator erase_after (const_iterator position);
iterator erase_after (const_iterator position, const_iterator last);

swap

交换容器中的内容。

void swap (forward_list& fwdlst);

resize

依旧是小于size则保留前n个，大于size填充新元素到n

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

clear

void clear() noexcept;

Operations splice_after

将元素从 fwdlst 传输到容器中，将它们插入到指向的位置元素之后。
第一个版本 (1) 将 fwdlst 的所有元素传输到容器中。
第二个版本 (2) 仅将 i 指向的元素从 fwdlst 传输到容器中。
第三个版本 (3) 将范围 (first,last) 从 fwdlst 传输到容器中。

entire list (1)	
void splice_after (const_iterator position, forward_list& fwdlst);
void splice_after (const_iterator position, forward_list&& fwdlst);
single element (2)	
void splice_after (const_iterator position, forward_list& fwdlst, const_iterator i);
void splice_after (const_iterator position, forward_list&& fwdlst, const_iterator i);
element range (3)	
void splice_after (const_iterator position, forward_list& fwdlst,const_iterator first, const_iterator last);
void splice_after (const_iterator position, forward_list&& fwdlst,const_iterator first, const_iterator last);

remove

删除具有特定值的元素**(所有）**

void remove (const value_type& val);

remove_if

删除满足条件（执行pred(*i)返回值为true的删除）的元素

template 
  void remove_if (Predicate pred);

unique

对于有序链表调用此方法，效率会提升。
方法二中对每个元素调用binary_pred(*i,*(i-1)) （其中 i 是元素的迭代器，从第二个开始），如果谓词返回 true，则从 forward_list 中删除 i。

(1)	
void unique();
(2)	
template 
void unique (BinaryPredicate binary_pred);

merge

合并有序链表，无序链表需使用list::splice方法实现

(1)	
 void merge (forward_list& fwdlst);
 void merge (forward_list&& fwdlst);
(2)	
template 
void merge (forward_list& fwdlst, Compare comp);
template 
void merge (forward_list&& fwdlst, Compare comp);

sort

稳定排序

(1)	
  void sort();
(2)	
template 
  void sort (Compare comp);

reverse

void reverse() noexcept;

Observers get_allocator

allocator_type get_allocator() const noexcept;