【STL】list的简单剖析以及各种函数的实现

STL中的list是比较常用的容器，对于任何位置的元素插入或元素移除，list永远是常数。

list中的迭代器在插入和删除后，仍然有效,但是耦合操作splice操作可能使迭代器失效，而vector就不成立了。

list节点

template <class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev; // 类型为void*。其实可设为 __list_node<T>*
    void_pointer next;
    T data;
};

显然这是一个双向链表，但其实是一个环状的双向链表
只需要一个指针，就可以完整的表现整个链表。
所以添加一个node节点，放置在尾端，符合前闭后开的区间，
这样是迭代器begin和end比较好完成。

4个构造

(1)explicit list ( const Allocator& = Allocator() );
(2)explicit list ( size_type n, const T& value = T(), const Allocator& = Allocator() );
(3)template < class InputIterator >
         list ( InputIterator first, InputIterator last, const Allocator& = Allocator() );
(4)list ( const list<T,Allocator>& x );

(1)是默认的构造函数，构造一个空的list对象，with no content and a size of zero。
空的list，前驱指向后继，后继指向前驱

(2)构造有n个T对象的list。
(3)迭代器的构造函数，区间[first,last),左闭右开
注迭代器构造函数的参数还可以用数组，可测试用例
(4)拷贝构造函数，

测试代码

// constructors used in the same order as described above:
  list<int> first;                                // empty list of ints
  list<int> second (4,100);                       // four ints with value 100
  list<int> third (second.begin(),second.end());  // iterating through second
  list<int> fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  list<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

  cout << "The contents of fifth are: ";
  for (list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
    cout << *it << " ";

  cout << endl;

迭代器操作函数：begin，end，rbegin，rend

begin和end

看上面list的节点的设计，知道有个头结点node放置在list的尾部，起始位置前驱指向node，list的尾指向node，node的前驱指向尾，后继指向起始节点。

所以begin和end函数中设计、前闭后开

iterator begin() {return (link_node*)((*node).next)}
iterator end() {return node;}

rbegin和rend

rbegin的位置相当于end的位置，
rend的位置相当于begin的位置。

Capacity操作函数

empty函数

看node节点的后继是否指向自己

bool empty()const { return node->next == node;}

size函数
返回lis的元素的个数

size_t size()const
{
    size_t result = 0;
    distance(begin(),end(),result);//全局函数，计算元素个数
    return result;
}

max_size和resize函数

max_size返回list中最大能包含元素个数。

reszie函数改变list中size的大小。
如果参数sz大于max_size，那么用c来构造；
如果参数sz小于max_size，那么进行切割。

void resize ( size_type sz, T c = T() );

测试

  list<int> mylist;

  unsigned int i;

  // set some initial content:
  for (i=1;i<10;i++) mylist.push_back(i);

  mylist.resize(5); //1 2 3 4 5
  mylist.resize(8,100);// 1 2 3 4 5 100 100 100
  mylist.resize(12); // 再加4个0

    //mylist contains: 1 2 3 4 5 100 100 100 0 0 0 0
  cout << "mylist contains:";
  for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
    cout << " " << *it;

  cout << endl;

Element access: front函数和back函数

利用那个node节点

reference front() {return *begin();}

reference back() {return *(--end());}

Modifiers:函数

先介绍insert函数和erase函数，这两个函数比较重要。

insert函数

insert函数其实是在pos位置之前插入元素的，返回的是新插入元素的 位置(看函数的实现)，但是pos位置仍然为之前节点的位置(看测试代码)

iterator insert ( iterator position, const T& x );
    void insert ( iterator position, size_type n, const T& x );
template <class InputIterator>
    void insert ( iterator position, InputIterator first, InputIterator last );

iterator insert ( iterator position, const T& x )
{
    link_node* tmp = create_node(x);//创建新的节点。
    //调整指针，使tmp插入进去
    tmp->next = position.next;
    tmp->prev = position.node->prev;
    (link_node*(position.node->prev))->next = tmp;
    position.node->prev = tmp;
    return tmp;
}

测试

list<int> mylist;
  list<int>::iterator it;

  // set some initial values:
  for (int i=1; i<=5; i++) mylist.push_back(i); // 1 2 3 4 5

  it = mylist.begin();
  ++it;       // it points now to number 2           

  mylist.insert (it,10);   // 1 10 2 3 4 5
    //注意看这
  // "it" still points to number 2                      
  mylist.insert (it,2,20);                      // 1 10 20 20 2 3 4 5

  --it;       // it points now to the second 20            

  vector<int> myvector (2,30);
  mylist.insert (it,myvector.begin(),myvector.end());
  // 1 10 20 30 30 20 2 3 4 5

erase函数

返回pos位置的下一个节点，pos变成next_node；即删除后两个表示的一样节点

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

//移除pos位置的节点
iterator erase ( iterator pos)
{
    link_node *next_node = (link_node*)pos.node->next;
    link_node *prev_node = (link_node*)pos.node->prev;
    prev_node->next = next_node;
    next_node_>prev = prev_node;
    destroy_node(pos.node);
    return iterator(next_node);
}

测试

int main ()
{
  unsigned int i;
  list<unsigned int> mylist;
  list<unsigned int>::iterator it1,it2;

  // set some values:
  for (i=1; i<10; i++) mylist.push_back(i*10);

                              // 10 20 30 40 50 60 70 80 90
  it1 = it2 = mylist.begin(); // ^^
  advance (it2,6);            // ^                 ^
  ++it1;                      //    ^              ^

  it1 = mylist.erase (it1);   // 10 30 40 50 60 70 80 90
                              //    ^           ^

  it2 = mylist.erase (it2);   // 10 30 40 50 60 80 90
                              //    ^           ^

  ++it1;                      //       ^        ^
  --it2;                      //       ^     ^

  mylist.erase (it1,it2);     // 10 30 60 80 90
                              //        ^

  cout << "mylist contains:";
  for (it1=mylist.begin(); it1!=mylist.end(); ++it1)
    cout << " " << *it1;
  cout << endl;
 //mylist contains: 10 30 60 80 90
  return 0;
}

push_back、push_front函数

调用insert函数

void push_front ( const T& x ){ insert(begin(),x);}

void push_back(const T& x){ insert(end(),x);}

pop_back、pop_front函数

调用erase函数

void pop_front () { erase(begin());}

void pop_back() 
{
    iterator tmp = end();
    erase(--tmp);
}

assign函数

重新写list，Assign new content to container，就像构造函数一样。

template <class InputIterator>
  void assign ( InputIterator first, InputIterator last );
void assign ( size_type n, const T& u );

list<int> first;
  list<int> second;

  first.assign (7,100);                      // 7 ints with value 100

  second.assign (first.begin(),first.end()); // a copy of first

  int myints[]={1776,7,4};
  first.assign (myints,myints+3);            // assigning from array

swap函数
Swap content，交换两个list

void swap ( list<T,Allocator>& lst );

  list<int> first (3,100);   // three ints with a value of 100
  list<int> second (5,200);  // five ints with a value of 200
  list<int>::iterator it;

  first.swap(second);
  //first contains: 200 200 200 200 200 
  //second contains: 100 100 100 

clear函数
清除整个链表

void clear()
{
 link_node *cur =(link_node*)node->next;//起始位置
 while(cur != node)
 {
   link_node *tmp = cur;
   cur = cur->next;
   destroy_node(tmp);
 }
 //恢复node原始状态，
 node->next = node;
 node->prev = node;

}

Operations函数

void reverse ( );
//Reverse the order of elements

remove
Remove elements with specific value
//删除所有的value值

void remove ( const T& value )
{
 iterator first = begin();
 iterator last = end();
 while(first != last)
 {
   iterator next = first;
   ++next;
   if(*first == value)
       erase(first);
   first = next;
 }
}

unique函数
//移除数值相同的连续元素，只有相同连续的元素，才会被移除剩一个

void unique()
{
 iterator first = begin();
 iterator last = end();
 if(first == last)
    return ;//空链表，返回
 iterator next = first;
 while(++next != last)
 {
   if(*first == *next)
       erase(next);
   else
       first = next;//调整指针，向后移动
   next = first;//修正区段，如果删除了，next指向下一个区域
 }
}

splice,sort,merge、reverse

这四个函数都需要调用，list内部提供的一个所谓的迁移操作(transfer)：将某连续范围的元素迁移到某个特定位置之前，就是一个指针的移动。

transfer函数
可以是同一个list，也可以是两条list

//将[first,last)内的所有元素都移到pos之前

//注：区间是左闭右开的，将first到last前一个插入pos之前
void transfer(iterator pos,iterator first,iterator last)
{
    //last等于pos，就不用移动
    if(pos != last)
    {
        //1-4从左向右断开
        //(1)将last的前一个节点后继指向pos位置
        (*((link_node*)(*last.node).prev)).next = pos.node;
        //(2)将firt到last摘出去
        (*((link_node*)(*fisrt.node).prev)).next = last.node;
        //(3)将摘出去的连接到pos之前
        (*((link_node*)(*pos.node).prev)).next = frst.nod;

        //从右向左链接
        //(4)标记pos之前的节点，因为(5)断开后找不到这个位置
        link_node* tmp = link_node*((*pos.node).prev);
        //(5)pos前驱指向last之前的节点
        (*pos.node).prev = (*last.node).prev;
        //(6)完全摘出去，last前驱指向fist之前的节点
        (*last.node).prev = (*first.node).prev;
        //(7)将frst节点连接到pos之前的tmp节点
        (*first.node).prev = tmp;

    }
}

reverse
将list中的原序列元素反序，调用transfer，

void reverse()
{
    //链表为空或者只有一个元素，什么不做
    //这样判断，速度较快
    if(node->next == node || (node->next)->next == node)
        return;

    iterator first = begin();
    ++first;//此时first指向第二个元素
    //
    while(first != end())
    {
        iterator old = first;
        ++first;
        //将后面的元素全部插入第一个元素之前。
        transfer(begin(),old,first);        
    }
}

splice函数

list提供的公共接口来将某些连续方位的元素从一个list移动到另一个list，封装了transfer。
另一个list中的元素已经被移走，

void splice ( iterator position, list<T,Allocator>& x );//移动整个x
void splice ( iterator position, list<T,Allocator>& x, iterator i );//只移动一个元素
void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );

测试

list<int> mylist1, mylist2;
  list<int>::iterator it;

  // set some initial values:
  for (int i=1; i<=4; i++)
     mylist1.push_back(i);      // mylist1: 1 2 3 4

  for (int i=1; i<=3; i++)
     mylist2.push_back(i*10);   // mylist2: 10 20 30

  it = mylist1.begin();
  ++it;                         // points to 2

  mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                // mylist2 (empty)
                                // "it" still points to 2 (the 5th element)

  mylist2.splice (mylist2.begin(),mylist1, it);
                                // mylist1: 1 10 20 30 3 4
                                // mylist2: 2
                                // "it" is now invalid.
  it = mylist1.begin();
  advance(it,3);                // "it" points now to 30

  mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                                // mylist1: 30 3 4 1 10 20

merge函数

注：必须两个list必须都已经递增排序，合并完后，参数x中没有元素

 void merge ( list<T,Allocator>& x )
template <class Compare>
  void merge ( list<T,Allocator>& x, Compare comp );

void merge ( list<T,Allocator>& x )
{
    iterator first1 = begin();
    iterator last1 = end();
    iteartor first2 = x.begin();
    iterator last2 = x.end();

    //注：两个list必须递增排序
    while(first1 != last1 && first2 != last2)
    {
        if(*first2 < *first1)
        {
            iterator next = first2;
            transfer(first1,fisrt2,++next);
            first2 = next;
        }
        else 
            ++first1;
    }
    if(first2 != last2)
        transfer(last1,first2,first2);
}

sort函数

list不能使用STL中的算法sort，必须使用自己的sort函数，
因为STL中的sort函数只接收RamdonAccessIterator

  void sort ( );
template <class Compare>
  void sort ( Compare comp );

void sort()
{
    //链表为空或者只有一个元素，什么不做
    //这样判断，速度较快
    if(node->next == node || (node->next)->next == node)
        return;

    //一些新的lists，作为中结数据存储区
    list<T> carry;
    list<T> counter[64];
    int fill = 0;

    //待排序的list不为空
    while(!empty())
    {
        //将待排序的list的首元素移动到carry中
        carry.splice(carry.begin(),*this,begin());

        //将carry中的元素放在桶counter[fill]中
        int i = 0; 
        while(i < fill && !counter[i].empty())
        {
            //合并到桶中，递增有序
            counter[i].merge(carry);

            carry.swap(counter[i++]);
        }

        //i ==fill跳出循环，说明当前桶放满，放在下个桶中
        //或者当前桶没放满，放在当前桶中
        carry.swap(counter[i]);
        //当前桶放满，放下个桶
        if(i == fill)
            ++fill;
    }

    for(int i = 1; i < fill; ++i)
        counter[i].merge(counter[i-1]);
    swap(counter[fill-1]);
}

这段代码长度不长，但是比较难理解。

fill–当前可以处理的元素个数为2^fill个

counter[fill]–可以容纳2^(fill+1)个元素
__counter[0]里存放2(0+1)次方个元素 1
__counter[1]里存放2(1+1)次方个元素 4
__counter[2]里存放2(2+1)次方个元素 8

carry–一个临时中转站，在处理的元素个数不足2^fill个时，在counteri之前转移元素

具体是显示步骤是：

1、每次读一个数据到carry中，并将carry的数据转移到counter[0]中

1)当counter[0]中的数据个数少于2时，持续转移数据到counter[0]中
2)当counter[0]的数据个数等于2时，将counter[0]中的数据转移到counter[1]…从counter[i]转移到counter[i+1],直到counter[fill]中数据个数达到2^(fill+1)个。

2、 ++fill,重复步骤1.

注：归并排序，先将前两个归并，然后再将后两个归并，再归并程4个元素；然后再两个两个归并，归并成4个，两个4个归并成8个；归并成16个。32个。。。。。

测试

list<double> first, second;

  first.push_back (3.1);
  first.push_back (2.2);
  first.push_back (2.9);

  second.push_back (3.7);
  second.push_back (7.1);
  second.push_back (1.4);

  first.sort();
  second.sort();

  first.merge(second);

  second.push_back (2.1);

  first.merge(second,mycomparison);