用empty()来代替size()判断容器是否为空

Code

http://blog.csdn.net/russell_tao/article/details/8572000
http://www.cplusplus.com/reference/list/list/splice/

• empty()是一个常数时间的操作，但对于一些list实现，size()花费线性时间。

常数时间：O(1)
线性时间：O(n)

list::splice()跟list::size()两者作为常数函数只能取其一，选择splice()为更简单的O(1)

list::splice()

entire list (1) 
void splice (const_iterator position, list& x);
void splice (const_iterator position, list&& x);
single element (2)  
void splice (const_iterator position, list& x, const_iterator i);
void splice (const_iterator position, list&& x, const_iterator i);
element range (3)   
void splice (const_iterator position, list& x,
             const_iterator first, const_iterator last);
void splice (const_iterator position, list&& x,
             const_iterator first, const_iterator last);

Transfer elements from list to list
Transfers elements from x into the container, inserting them at position.

This effectively inserts those elements into the container and removes them from x, altering the sizes of both containers. The operation does not involve the construction or destruction of any element. They are transferred, no matter whether x is an lvalue or an rvalue, or whether the value_type supports move-construction or not.

The first version (1) transfers all the elements of x into the container.
The second version (2) transfers only the element pointed by i from x into the container.
The third version (3) transfers the range [first,last) from x into the container.

TIPS:插入的时候会改变当前指针position所指向的数据，而不是position的下一个

// splicing lists
#include <iostream>
#include <list>
int main ()
{
  std::list<int> mylist1, mylist2;
  std::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();
  std::advance(it,3);           // "it" points now to 30
  mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                                // mylist1: 30 3 4 1 10 20
  std::cout << "mylist1 contains:";
  for (it=mylist1.begin(); it!=mylist1.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
  std::cout << "mylist2 contains:";
  for (it=mylist2.begin(); it!=mylist2.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
  return 0;
}