C++中的list是一个双向链表,也是一种序列容器,它可以在任何位置高效地插入和删除元素,支持正向迭代和反向迭代。在list中,每个元素保存在一个结点中,相邻的结点使用指针连接起来(前一个结点的后向指针指向后一个结点,后一个结点的前向指针指向前一个结点)。因此,要想找到位于第i个位置的元素,需要从第一个元素开始,顺着指针依次找下去,导致该操作的时间复杂度为O(n)。

list包含在<list>头文件中,它是一个类模板,因此在定义list类的对象时,需要指明容器需要保存的对象的类型(除特殊情况外,本文均以int类型为例)。对于标注C++11的内容,需要支持C++11标准的编译器来编译。

构造与析构

  1. list() 默认构造函数,构造一个空的容器,不包含任何元素;
  2. list(size_type n, value_type &val) 填充构造函数,构造一个含有n个val的容器;
  3. list(iterator first, iterator last) 范围构造函数,构造一个包含[first, last)的容器;
  4. list(const list<value_type> &x) 复制构造函数,构造一个与x相同的容器;
  5. list(list<value_type> &&x) (C++11)移动构造函数,如果指定的分配器与x相同,则直接引用x中的内容,而不是逐个分配;
  6. list(initializer_list<value_type> il) (C++11)初始化列表构造函数;
  7. ~list() 析构函数,释放内存并销毁对象。
#include <list>
using std::list;
int main()
{
    list<int> l1; // 空容器
    list<int> l2(4, 1); // 4个1
    list<int> l3(l2.begin(), l2.end()); // 和l2相同
    list<int> l4(l3); // 和l3相同
    list<int> l5(std::move(l4)); // 执行后l4为空
    list<int> l6({1, 2, 3, 4});
}

迭代器

  1. begin() 返回第一个元素的迭代器;
  2. end() 返回最后一个元素后面的迭代器(而不是最后一个元素);
  3. rbegin() 返回最后一个元素的反向迭代器;
  4. rend() 返回第一个元素前面的迭代器;
  5. cbegin()、cend()、crbegin()、crend()(C++11) 表示对应的常量(const)迭代器。
#include<iostream>
#include<list>

using std::cout;
using std::endl;
using std::list;
int main()
{
    list<int> ls({1, 2, 3, 4});
    cout << "The list contains:";
    for(auto it = ls.begin(); it != ls.end(); ++it)
        cout << ' ' << *it;
    cout << endl;

    cout << "The reversed list contains:";
    for(auto it = ls.rbegin(); it != ls.rend(); ++it)
        cout << ' ' << *it;
    cout << endl;
    return 0;
}
/*
The list contains: 1 2 3 4
The reversed list contains: 4 3 2 1
*/

容量相关

  1. size() 获取容器中元素个数;
  2. max_size() 返回在当前的系统环境下,容器最多可以容纳的元素个数,但并不一定可以达到这么多;
  3. empty() 若容器为空则返回true,否则返回false。
#include<iostream>
#include<list>
 
using std::cout;
using std::endl;
using std::list;
int main()
{
    list<int> ls({1, 2, 3, 4});
    cout << "ls contains " << ls.size() << " elements.\n";
    if(ls.empty()) cout << "ls is empty.\n";
    else cout << "ls is not empty.\n";
    return 0;
}
/*
ls contains 4 elements.
ls is not empty.
*/

元素访问

  1. front() 返回第一个元素的引用;
  2. back() 返回最后一个元素的引用。
#include<iostream>
#include<list>
 
using std::cout;
using std::endl;
using std::list;
int main()
{
    list<int> ls({1, 2, 3, 4});
    ls.front() = 4;
    ls.back() = 1;
    cout << "The front of ls is " << ls.front() << ".\n";
    cout << "The back of ls is " << ls.back() << ".\n";
    return 0;
}
/*
The front of ls is 4.
The back of ls is 1.
*/

增删元素

  1. assign(…) 为容器重新赋值;(使用…表示有多种参数不同的函数,在代码中给出示例);
  2. emplace_front(Args&&… args) (C++11)使用args构造并在容器前插入元素,没有返回值;
  3. push_front(value_type &val) 在容器前增加元素;
  4. pop_front() 删除第一个元素;
  5. emplace_back(Args&&… args) (C++11)使用args构造并在容器后插入元素,没有返回值;
  6. push_back(value_type &val) 在容器后增加元素;
  7. pop_back() 删除最后一个元素;
  8. emplace(const_iterator pos, Args&&… args) (C++11)使用args构造并在pos位置插入元素,返回新元素的迭代器;
  9. insert(…) 在当前位置插入元素,返回第一个插入元素的迭代器;
  10. erase(…) 删除当前位置的元素,返回下一个元素的迭代器;
  11. swap(list<value_type> &ls) 交换两个容器的内容;
  12. resize(size_type n, const value_type &val) 将容器大小置为n,若n小于当前元素数量,则只保存前n个元素,若n大于当前元素数量,则使用val填充;
  13. clear() 清空容器。
#include<iostream>
#include<list>
 
using std::cout;
using std::endl;
using std::list;
 
void show(list<int> &ls)
{
    for(auto i : ls)
        cout << ' ' << i;
    cout << endl;
}
int main()
{
    list<int> ls({1, 2, 3, 4});
 
    // assign:
    list<int> ls2(2, 0);
    cout << "Before assign, the elements in ls2 are: ";
    show(ls2);
    auto it = ls.end();
    --it;
    // assign(InputIterator first, InputIterator last)
    ls2.assign(ls.begin(), it); // 1 2 3
    // assign(size_type n, const value_type &val)
    ls2.assign(4, 0); // 4个0
    // assign(initializer_list<value_type> il) (C++11)
    ls2.assign({3, 2, 1}); // 3 2 1 (C++11)
    cout << "After assign, the elements in ls2 are: ";
    show(ls2);
 
    // 带有emplace的函数可参见vector,此处不再赘述
    // https://blog.kedixa.top/2016/cpp-container-vector/
 
    // insert
    // insert(const_iterator it, const value_type &val)
    ls2.insert(ls2.begin(), 4); // 4 3 2 1
    // insert(const_iterator it, size_type n, const value_type &val)
    ls2.insert(ls2.end(), 2, 0); // 4 3 2 1 0 0
    // insert(const_iterator it, InputIterator first, InputIterator last)
    ls2.insert(ls2.end(), ls.begin(), ls.end()); // 4 3 2 1 0 0 1 2 3 4
    // insert(const_iterator it, value_type &&val) (C++11)
    // 将val移动(move)到it位置,关于移动语义暂不讨论,省略
    // insert(const_iterator it, initializer_list<value_type> il) (C++11)
    it = ls2.begin();
    ++it;
    ls2.insert(it, {5});
    cout << "After insert, the elements in ls2 are: ";
    show(ls2);
 
    // erase
    // erase(const iterator it) 删除it指向的内容
    it = ls2.end();
    --it;
    ls2.erase(it);
    // erase(const_iterator first, const_iterator last) 删除区间[first, last)
    it = ls2.end();
    --it, --it;
    ls2.erase(ls2.begin(), it);
    cout << "After erase, the elements in ls2 are: ";
    show(ls2);
 
    // swap
    ls2.swap(ls); // 1 2 3 4
    cout << "After swap, the elements in ls are: ";
    show(ls);
 
    // resize
    ls2.resize(7, 10);
    cout << "After swap and resize, the elements in ls2 are: ";
    show(ls2);
 
    ls2.clear(); // 清空容器
    if(ls2.empty()) cout << "After clear, ls2 is empty.\n";
    return 0;
}
/*
Before assign, the elements in ls2 are:  0 0
After assign, the elements in ls2 are:  3 2 1
After insert, the elements in ls2 are:  4 5 3 2 1 0 0 1 2 3 4
After erase, the elements in ls2 are:  2 3
After swap, the elements in ls are:  2 3
After swap and resize, the elements in ls2 are:  1 2 3 4 10 10 10
After clear, ls2 is empty.
*/

其他操作

  1. splice(…) 从另一个链表剪下一段并拼接到容器中;
  2. remove(const value_type &val) 删除所有值为val的元素;
  3. remove_if(Predicate pred) 删除所有使谓词为真的元素;
  4. unique(…);
  5. merge(list<value_type> &b, Compare cmp) 需要两个链表都是有序的,将该链表与b归并,函数返回后b容器为空,该函数可以指定比较函数;
  6. sort(Compare cmp) 将链表排序,若不指定排序函数,则按照operator<排序;
  7. reverse() 反转链表。
#include<iostream>
#include<list>
 
using std::cout;
using std::endl;
using std::list;
 
void show(list<int> &ls)
{
    for(auto i : ls)
        cout << ' ' << i;
    cout << endl;
}
bool is_odd(int i)
{
    return i%2==1;
}
bool diff(int x, int y)
{
    return y - x == 1;
}
 
int main()
{
    list<int> ls({1, 2, 3, 4});
    list<int> ls2;
    // splice
    // splice(const_iterator it, list &x) 将x的内容插入到迭代器it指向的位置
    ls2.splice(ls2.end(), ls); // ls2: 1 2 3 4, ls为空
    ls.swap(ls2);
    // splice(const_iterator it, list &x, const_iterator i) 将i指向的内容插入到it指向的位置
    ls2.splice(ls2.end(), ls, ls.begin()); // ls2: 1, ls: 2 3 4
    // splice(const_iterator it, list &x, const_iterator first, const_iterator last)
    // 将x的[first, last) 插入到 it指向的位置
    ls2.splice(ls2.begin(), ls, ls.begin(), ls.end());
    cout << "After splice, the elements in ls are: ";
    show(ls);
    cout << "After splice, the elements in ls2 are: ";
    show(ls2);
 
    // remove
    ls2 = list<int>({1, 1, 2, 3, 4, 5});
    ls2.remove(1); // 2 3 4 5
    ls2.remove_if(is_odd); // 2 4
    cout << "After remove, the elements in ls2 are: ";
    show(ls2);
 
    // unique
    ls2 = list<int>({1, 1, 1, 2, 2, 3, 4, 6, 7});
    // unique() 相邻的相同元素只保留一个
    ls2.unique(); // 1 2 3 4 6 7
    // unique(BinaryPredicate pred) 若pred(*it, *(it-1))返回真,则删除it指向的内容
    ls2.unique(diff);
    cout << "After unique, the elements in ls2 are: ";
    show(ls2);
 
    // merge
    ls.assign({1, 3, 5});
    ls2 = list<int>({2, 4});
    ls2.merge(ls);
    cout << "After merge, the elements in ls2 are: ";
    show(ls2);
 
    // reverse
    ls2.reverse();
    cout << "After reverse, the elements in ls2 are: ";
    show(ls2);
 
    // sort
    ls2.sort();
    cout << "After sort, the elements in ls2 are: ";
    show(ls2);
    return 0;
}
/*
After splice, the elements in ls are: 
After splice, the elements in ls2 are:  2 3 4 1
After remove, the elements in ls2 are:  2 4
After unique, the elements in ls2 are:  1 3 6
After merge, the elements in ls2 are:  1 2 3 4 5
After reverse, the elements in ls2 are:  5 4 3 2 1
After sort, the elements in ls2 are:  1 2 3 4 5
*/

总结

list适用于需要频繁地在中间进行插入或删除操作的情况。当向某个位置插入元素时,该位置以及之后的元素仍保存原来的顺序,由于链表使用指针将所有元素“串”起来,因此插入操作只需要修改几个相邻的指针,不需要像vector那样移动元素,因此这个操作是常数复杂度。

需要谨记的是,如果需要随时获取位于某个下标的元素,list的效率会很差,需要从开始位置一个一个地找下去,如果需要频繁执行这样地操作,使用list可能不是一个好想法。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注