前言

提示：list::insert(), list::erase(), list::splice(), std::iter_swap()

list作为C++中的链表容器，相较于vector容器的顺序结构优势在于插入和删除的常数开销。相比于元素这个词，我更喜欢用节点来表示list的独立单元。此篇文章将介绍如何在list内部实现元素（节点）的移动和交换。

提示：以下是本篇文章正文内容，下面案例可供参考

一、list是什么？

list是STL中常用的容器之一，list将元素按顺序储存到链表中，在快速删除和快速插入方面的效率比vector高出许多。STL中的list是一双向链表，具有指向前一节点和后一节点的指针。

二、元素移动

将list中的某一元素（节点）移动到某一位置。

1. 插入 + 删除

list容器提供了

insert(pos, beg, end); // 在pos位置插入[beg, end)区间的数据，无返回值
erase(pos); // 删除pos位置的数据，返回下一个数据的位置

代码如下（示例）：

void printList(const list<int> &l)
{
    for (auto i : l)
        cout << i << " ";

    cout << endl;
}

int main()
{
    list<int> l{1, 2, 3, 4};

    /* 将尾节点移动到头节点位置，即移动后的链表：{4, 1, 2, 3} */
    list<int>::iterator head = l.begin();
    list<int>::iterator tail = next(l.end(), -1);

    // 插入
    l.insert(head, tail, next(tail, 1));
    cout << "The list after insertion: ";
    printList(l);

    // 删除
    l.erase(tail);
    cout << "The list after deletion: ";
    printList(l);
    
	cout << "Iterator head and iterator of 1 in the current list are " << (head == next(l.begin(), 1) ? "" : "not ") << "the same" << endl;
    cout << "Iterator tail and iterator of 4 in the current list are " << (tail == l.begin() ? "" : "not ") << "the same" << endl;

    return 0;
}

输出：

The list after insertion: 4 1 2 3 4
The list after deletion: 4 1 2 3
Iterator head and iterator of 1 in the current list are the same
Iterator tail and iterator of 4 in the current list are not the same

我首先使用insert(pos, beg, end)函数，该函数将指定迭代器范围[beg, end)指向的元素值进行值拷贝，并生成新的元素（节点）然后插入到指定的迭代器pos位置。接下来，使用erase(pos)函数对指定迭代器pos位置进行删除。最后，经过上述操作，我对比了元素值为1和4的迭代器是否还保持一致？可以发现，元素值为4的迭代器因为insert()函数的值拷贝和生成新元素和插入元素，已经不再是原先的元素（节点）迭代器tail了。
这在某些情况下往往不符合开发者对于链表结构移动的操作，因为通常开发者在操作链表移动时，仅仅是将链表的节点进行移动就可以了，所以下面我介绍这种方法。

2. 切除 + 拼接

list容器提供了

l1.splice ( iterator l1_pos, list<T,Allocator>& l2, iterator l2_pos ); // 将l2的l2_pos指向元素（节点）切除，拼接到l1的l1_pos处（l1和l2可相同）

代码如下（示例）：

int main()
{
    list<int> l{1, 2, 3, 4};

    /* 将尾节点移动到头节点位置，即移动后的链表：{4, 1, 2, 3} */
    list<int>::iterator head = l.begin();
    list<int>::iterator tail = next(l.end(), -1);

    // 切除 + 拼接
    l.splice(head, l, tail);
    cout << "The list after splicing: ";
    printList(l);

    cout << "Iterator head and iterator of 1 in the current list are " << (head == next(l.begin(), 1) ? "" : "not ") << "the same" << endl;
    cout << "Iterator tail and iterator of 4 in the current list are " << (tail == l.begin() ? "" : "not ") << "the same" << endl;

    return 0;
}

输出：

The list after splicing: 4 1 2 3
Iterator head and iterator of 1 in the current list are the same
Iterator tail and iterator of 4 in the current list are the same

从上面的结果不难发现，在经过splice()函数后，元素值为4的节点被移动到了头节点的位置。同时，原先指向1和4元素值的迭代器head和tail依旧指向相同的节点，这非常好的满足了链表移动节点的操作。

三、元素交换

将list中的某两个元素进行交换。

1. 元素值交换

C++ algorithm库中提供了

void iter_swap ( Iterator it1, Iterator it2 ); // 用于交换两个迭代器所指向的值

代码如下（示例）：

int main()
{
    list<int> l{1, 2, 3, 4};

    /* 将尾节点和头节点进行交换，即交换后的链表：{4, 2, 3, 1} */
    list<int>::iterator head = l.begin();
    list<int>::iterator tail = next(l.end(), -1);

    // 交换元素值
    iter_swap(head, tail);
    cout << "The list after iter_swap: ";
    printList(l);

    cout << "Iterator head and iterator of 1 in the current list are " << (head == next(l.end(), -1) ? "" : "not ") << "the same" << endl;
    cout << "Iterator tail and iterator of 4 in the current list are " << (tail == l.begin() ? "" : "not ") << "the same" << endl;

    return 0;
}

输出：

The list after iter_swap: 4 2 3 1
Iterator head and iterator of 1 in the current list are not the same
Iterator tail and iterator of 4 in the current list are not the same

从上述结果不难看出头元素和尾元素的值的确进行了交换，但可以发现迭代器head不再是当前元素值为1的迭代器，迭代器tail也不再是当前元素值为4的迭代器。
事实上，头尾节点并没有进行交换，实际上交换的则是节点内部的值。这在某些情况下往往不符合链表的交换操作，开发者通常使用的链表交换是将两个节点进行互换，下面我将介绍这种方法。

2. 元素（节点）交换

list容器提供了

l1.splice ( iterator l1_pos, list<T,Allocator>& l2, iterator l2_pos ); // 将l2的l2_pos指向元素（节点）切除，拼接到l1的l1_pos处（l1和l2可相同）

代码如下（示例）：

int main()
{
    list<int> l{1, 2, 3, 4};

    /* 将尾节点和头节点进行交换，即交换后的链表：{4, 2, 3, 1} */
    list<int>::iterator head = l.begin();
    list<int>::iterator tail = next(l.end(), -1);

    // 交换元素（节点）
    list<int>::iterator it = next(tail, 1);
    
    l.splice(head, l, tail);
    l.splice(it, l, head);
    cout << "The list after swapping nodes: ";
    printList(l);

    cout << "Iterator head and iterator of 1 in the current list are " << (head == next(l.end(), -1) ? "" : "not ") << "the same" << endl;
    cout << "Iterator tail and iterator of 4 in the current list are " << (tail == l.begin() ? "" : "not ") << "the same" << endl;

    return 0;
}

输出：

The list after swapping nodes: 4 2 3 1
Iterator head and iterator of 1 in the current list are the same
Iterator tail and iterator of 4 in the current list are the same

其实，有了上面移动元素的经验，很容易用splice()实现元素的交换，即将两个待交换的节点分别移动到对应位置。