STL序列容器（二）

std::forward_list

概述

forward_list是c++11 STL提供的新容器类型，它也可以提供任何位置的常量时间的插入和删除操作，但是forward_list并没有提供list中类似的insert,emplace以及erase操作，而是定义了insert_after,emplace_after以及erase_after操作。原因和forward_list的内部实现有关。
实际上forwar_list底层是采用单向链表实现的，单向链表和双向链表的区别是：双向链表的每一个节点除了保存数据以外还保存了两根指针，分别指向前一个节点和后一个节点；而单向链表每个节点除了数据外只有一根指针指向后续节点。倘若forward_list要提供常规的insert等的操作的话，需要访问迭代器指向的节点的前一节点，这在单向链表中是十分困难的。
同样forward_list还提供特有的before_begin()和cbefore_begin()方法来返回第一个元素的前向迭代器，这个迭代器不能够被解引用，只是便于用作emplace_after,insert_after和erase_after的参数。forward_list提供的迭代器类型是Forward Iterator，这种迭代器只能执行自加操作，不能自减。

单向链表

常用接口

构造函数(和list基本一致)

//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 <class InputIterator>
  forward_list (InputIterator first, InputIterator last,
                const allocator_type& alloc = allocator_type());
//initializer list (6)    
forward_list (initializer_list<value_type> il,
              const allocator_type& alloc = allocator_type());

大小

1 2	bool empty() const noexcept; size_type max_size () const noexcept; //容器能够容忍的最大元素个数(注意，forward_list没有提供size函数)

插入/删除元素

void push_front (const value_type& val);  //在forward_list的头部插入元素，头迭代器之前添加元素
template <class... Args>
void emplace_front (Args&&... args);
void pop_front();

void clear() noexcept;

template <class... Args>
iterator emplace_after (const_iterator position, Args&&... args);  //在迭代器position后面插入，原地构造
iterator insert_after ( const_iterator position, const value_type& val );  //在迭代器position后面插入(这是单向链表特性导致的独有操作)
iterator insert_after ( const_iterator position, size_type n, const value_type& val );
template <class InputIterator>
iterator insert_after ( const_iterator position, InputIterator first, InputIterator last );
iterator insert_after ( const_iterator position, initializer_list<value_type> il );

iterator erase_after (const_iterator position);  //从position的位置往后删除一个元素
iterator erase_after (const_iterator position, const_iterator last);  //删除一段范围内的元素

获取元素或迭代器

reference front();

iterator before_begin() noexcept;
iterator begin() noexcept;
iterator end() noexcept;

const_iterator cbefore_begin() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend () const noexcept;

其它操作

void splice_after (const_iterator position, forward_list& fwdlst);  //将fwdlst中的所有元素转移至position之后，这同时改变了两个fordward_list的大小，且不涉及任何元素的构造和析构，这就是元素的位置转移
void splice_after (const_iterator position, forward_list& fwdlst, const_iterator i);  //将fwdlst中的单个元素转移至position之后
void splice_after (const_iterator position, forward_list& fwdlst,
                   const_iterator first, const_iterator last);  //将fwdlst中的一段元素转移至position之后
void remove (const value_type& val);  //删除forward_list中等于val的所有元素
template <class Predicate>
void remove_if (Predicate pred);  //删除forward_list中满足参数指定条件的所有元素，参数是一个仿函数或函数指针
void unique();  //删除相邻且重复的元素，这对排序后十分有用

void merge (forward_list& fwdlst);  //按序合并两个排序好的forward_list，执行完之后fwdlst元素被转移了

void sort();  //排序

void reverse() noexcept; //反转

std::priority_queue

概述

priority_queue也是一种容器适配器，它也是一个queue，也就是说数据只能从一端进，从另一端出。它的最大特点是内部的第一个元素总是容器中最大的元素，也就是说，从容器中取数的时候总是会取到最大的数。其声明如下：

1 2	template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

第一个模板参数和第二个模板参数和queue一致，第三个模板参数是一个仿函数类或函数指针，它作为容器中比较元素大小的依据。Compare接受容器中的两个元素a和b(类型为T)，返回bool型的变量，希望a排在b前则返回true。
priority_queue只是容器的包装，底层容器必须支持以下操作：

empty()
size()
front()
push_back()
pop_back()

标准库中的vector和deque都满足上述条件，如果没有指定底层容器，默认使用vector。priority_queue和queue一样不提供迭代器。

二叉堆(binary heap)

priority_queue底层通过heap来实现的，heap是一种特殊的数据结构，它用数组来实现了一颗完全二叉树(complete binary tree)，也叫做二叉堆(binary heap)。树上的每一个结点对应数组中的一个元素，除了最底层以外，该树是完全充满的。

上面就是一个完全二叉树，heap分为max-heap和min-heap，其中max-heap实现的完全二叉树保证每个节点的值大于它的两个子节点，即最大节点在根部，也就是在内部数组的第一个元素的位置；min-heap实现的完全二叉树保证每个节点的值小于它的两个子节点，最小节点在根部，也就是内部数组的第一个元素的位置。
关于如何实现一个heap中的相关算法可以参考《算法导论3th》第六章堆排序，这里不详细介绍，只做简单说明。
heap
如上图，以max-heap为例，如果数组下标从1开始，若将某个节点放在数组i的位置，那么其左子节点放在2i的位置，右子节点放在2i+1的位置，由于是完全二叉树，所有可以将所有节点放在相邻的位置。

考虑向上面的树中插入一个新的值a，a放在数组的最后一个元素右边，也就是完全二叉树的叶节点处，为了满足父节点比子节点大的规则，需要执行(percolate up)上溯程序，也就是将新的叶子节点和父节点比较大小，若比父节点大则父子交换顺序，层层上溯，直到不需要对换或到根节点为止。
从上面的树中取出元素(删除元素)时，由于是取出最大的元素，只需要取出二叉树的根节点即可，也就是底层数组中的第一个元素。为了满足堆的规则，需要执行(percolate down)下溯程序，将取走根节点后剩下的空间节点与其较大的子节点交换位置，一直到叶子节点为止。还有建堆和堆排序等建议查看算法导论中的介绍。

常用接口

priority_queue的接口和queue基本一致，只是出队的元素总是优先级最高的。

构造函数实例

// constructing priority queues
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs<rhs);
  }
};

int main ()
{
  int myints[]= {10,60,50,20};

  std::priority_queue<int> first;   //默认构造
  std::priority_queue<int> second (myints,myints+4);  //通过迭代器范围构造
  std::priority_queue<int, std::vector<int>, std::greater<int> >  //指定内部container和比较函数，这里出队的将是最小的元素
                            third (myints,myints+4);
  // using mycomparison:
  typedef std::priority_queue<int,std::vector<int>,mycomparison> mypq_type;

  mypq_type fourth;                       // less-than comparison
  mypq_type fifth (mycomparison(true));   // greater-than comparison

  return 0;
}

其它接口

void push (const value_type& val);
template <class... Args> void emplace (Args&&... args);
void pop();

bool empty() const;
size_type size() const;
const_reference top() const;  //注意这里返回的是const reference，不能更改内部的值

总结

文章比较短，主要是简单说了下forward_list和priority_queue两种序列容器的结构和接口，实际上forward_list使用并不是很多，而优先队列priority_queue在某些情况下比较有用，用这种数据结构实现排序算法也是很有名的。至此，STL中的常用序列容器就介绍完了，后面的文章会介绍STL容器中的另一类：关联式容器。

参考链接

《STL源码剖析》侯捷
http://www.cplusplus.com/reference/
《C++ Primer 5th》
《算法导论 3th》