list

list (cplusplus.com)

list 是双向链表,forward_list 是单向链表。

template < 
	class T, //模板参数T
	class Alloc = allocator<T> //空间配置器
         > 
class list; //类模板

关于链表,数据结构处已经讨论过,不再赘述。

1. list的使用

1.1 基本接口

默认成员函数说明
list ()默认构造
list (size_type n, const value_type& val = value_type())填充构造
list (InputIter first, InputIter last)范围构造
list (const list& li)拷贝构造
list& operator= (const list& x)赋值重载
访问接口说明
reference front()取头元素
reference back()取尾元素
容量接口说明
bool empty() const判空
size_type size() const元素个数
void resize (size_type n, value_type val = value_type())修改元素个数
修改接口说明
void push_front (const value_type& val)头插
void pop_front()头删
void push_back (const value_type& val)尾插
void pop_back()尾删
iterator insert (iterator position, const value_type& val)迭代器插入
void insert (iterator position, size_type n, const value_type& val)迭代器插入
void insert (iterator position, InputIter first, InputIter last)迭代器插入
iterator erase (iterator position)迭代器删除
iterator erase (iterator first, iterator last)迭代器删除
void assign (InputIter first, InputIter last)重置链表
void assign (size_type n, const value_type& val)重置链表
void clear()清空链表

1.2 功能接口

功能接口说明
void reverse()逆置链表
void sort(Compare comp = cmp)排序链表
void unique()链表去重
void remove (const value_type& val)删除所有指定元素
void merge (list& x, Compare comp = cmp归并两个链表
void splice (iterator position, list& x)接合整个链表
void splice (iterator position, list& x, iterator i)接合单个元素
void splice (iterator position, list& x, iterator first, iterator last)接合一段区间
lt.sort();

list 不支持随机访问,所以不支持算法库中的 sort。

单独内置一个 sort 接口,使用的是归并排序,但效率不高。当需要对数据进行排序的时候,不要选择链表。

lt.sort();
lt.unique();

去重接口可以去掉链表中的重复元素,但前提是需先将链表排成有序状态

lt.remove(1);

删除链表中所有指定值的元素,不是指定下标位置的元素。

lt.splice(pos, list);              // 转移整个链表
lt.splice(pos, list, i);           // 转移单个节点
lt.splice(pos, list, first, last); // 转移一段区间

接合函数能将一个链表中的一个或多个节点,转移到另一个链表中的指定迭代器位置。可转移整个链表,可转移链表内的一个元素,转移一个迭代器区间。

splice 的功能是转移不是拷贝,原链表中的该节点将不复存在。

 

list 不支持随机访问,实际中用的不多。list 的重点在于模拟实现。

2. list的模拟实现

2.1 list的定义

// listnode
template <class T>
struct __list_node 
{ 
    listNode(T& x = T())
    	: _data(x)
        , _prev(nullptr)
        , _next(nullptr)
    {}
    
    T _data;
    __list_node<T>* _prev;
    __list_node<T>* _next;
};

// list
template <class T>
class list 
{ 
public:
    typedef __list_node<T> Node;
    list()
    	: _head(new Node)
    {
        _head->_prev = _head;
        _head->_next = _head;
    }
    
private:
    Node* _head;
}

__list_node 是链表节点类,list 是链表类,他的成员是 __list_node 类型的指针,作链表的带头节点。

一般供他人使用的类,都用 struct 定义,因为 struct 定义的类成员默认都是公有的。

2.2 默认成员函数

/* default constructor */
void empty_init()
{
	_head = new Node(x);
    _head->_prev = _head;
    _head->_next = _head;
}
list()
{
    empty_init();
}
/* copy constructor */  
//传统写法
list<T>(const list<T>& lt)
{
    empty_init();
    for (auto e : lt)
        push_back(e);
}
//现代写法
list<T>(const list<T>& lt)
{
	empty_init();
	list<T> tmp(lt.begin(), lt.end());
    swap(_head, tmp._head);
}


/* = operator */
//传统写法
list<T>& operator=(const list<T>& lt)
{	
    if (this != &lt) {
        clear();
        for (auto e : lt)
            push_back(e);
    }
    return *this;
}
//现代写法
list<T>& operator=(list<T> lt)
{
    swap(_head, lt._head);
    return *this;
}
/* deconstructor */
~list() 
{
    clear();
    delete _head;
}

2.3 迭代器

迭代器模拟指针,意图像指针一样遍历容器。

list 的底层实现并不是 vector 一样的连续空间,而是通过节点地址链接前后,故 list 实现上述操作就需要自行实现一个迭代器类再重载这些运算符。

正向迭代器
template <class T>
struct _list_iterator 
{
    typedef __list_node<T> Node;
    typedef __list_iterator<T> self;
    
    _list_iterator(Node* x)
    	: _node(x) // 用节点地址初始化迭代器成员,相当于成员节点指针指向了链表中的该节点。
    {}
    
    T&    operator* ();
    self& operator++();
    self  operator++(int);
    self& operator--();
    self  operator--(int);
    bool  operator==(const self& it);
    bool  operator!=(const self& it);

    Node* _node;
};

list 容器的迭代器是双向迭代器,不支持随机访问,没有重载+,+=,-,-=

迭代器的拷贝构造、赋值重载都只需要浅拷贝指针。析构函数无需释放任何资源,节点交由链表进行管理。所以这些编译器默认生成就可以。

解引用箭头
template <class T, class Ref, class Ptr> // 交由list类控制
struct __list_iterator 
{
	typedef __list_iterator<T, Ref, Ptr> iterator;
    Ref operator* () { return  _node->_data; }
    Ptr operator->() { return &_node->_data; }
    //...
};

class list
{
public:
    typedef __list_iterator<T, T&, T*> iterator;                   // 传入普通类型
    typedef __list_iterator<T, const T&, const T*> const_iterator; // 传入常量类型
}

可以给迭代器类增加引用和指针类型的模版参数,分别给*->重载函数返回值使用。

相当于把具体的元素引用和指针类型交给外界控制。就不需要单独实现一个常量迭代器了。

当元素是自定义类型时,箭头操作符可以让迭代器直接访问到自定义类型的内部成员。如:

struct AA
{
    AA(int a1 = 0, int a2 = 0) : _a1(a1), _a2(a2) {}
    int _a1;
    int _a2;
};

void test_list()
{
    list<AA> lt;
    lt.push_back(AA(1, 1));
    lt.push_back(AA(2, 2));

    list<AA>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << it->_a1 << ":" << it->_a2 << " "; // ->直接访问AA内部成员
        ++it;
    }
    cout << endl;
}

it->AA()->_a1,省略了一个->

反向迭代器

反向迭代器同样是个适配器,所以它被单独实现在一个文件中。

template <class Iterator, class Ref, class Ptr>
struct reverse_iterator
{
    typedef reverse_iterator self;

    reverse_iterator(Iterator it) // 利用正向迭代器构造出反向迭代器
        :_it(it) 
    {}
    
    self& operator++() // 反向迭代器++,就是正向迭代器--
    {
        --_it;
        return *this;
    }

    self& operator--() // 反向迭代器--,就是正向迭代器++
    {
        ++_it;
        return *this;
    }

    bool operator!=(const self& it) // 反向迭代器是否相等,就是正向迭代器是否相等
    {
        return _it != it._it;
    }
    
    Iterator _it;
};

反向迭代器的成员是正向迭代器,是对正向迭代器的一种封装,这是一种适配器模式。基本接口都可以复用正向迭代器的。

Ref operator*() 
{
    //return *_it;
    Iterator tmp = _it;
    return *--tmp;       // 前一个位置的迭代器
}
Ptr operator->()
{
    Iterator tmp = _it;
    return &*--tmp;
}

反向迭代器解引用和箭头不是访问当前位置,而是前一个位置

所有容器的正反向迭代器的begin(),end()rbegin(),rend()所指向的位置正好对应相反。目的是设计出对称形式,因此解引用时返回的是上一个位置的数据。

迭代器接口
class list 
{
    typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
    typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

    iterator begin() { return iterator(_head->_next); }
    iterator end()   { return iterator(_head); }
    
    const_iterator begin() const { return const_iterator(_head->_next); }
    const_iterator end()   const { return const_iterator(_head); }

    reverse_iterator rbegin() { return reverse_iterator(end()); }
    reverse_iterator rend()   { return reverse_iterator(begin()); }

    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    const_reverse_iterator rend()   const { return const_reverse_iterator(begin()); }
};

2.4 增删查改接口

插入删除
iterator insert(iterator pos, const T& x)
{
    Node* newNode = new Node(x);
    Node* prev = pos._node->_prev;
    Node* cur = pos._node;
    
    // prev - newNode - cur
    prev->_next = newNode;
    newNode->_prev = prev;
    
    cur ->_prev = newNode;
    newNode->_next =  cur;
    
    return iterator(newNode); //返回迭代器
}
iterator erase(iterator pos)
{
    assert(pos != end());
    
    Node* prev = pos._node->_prev;
    Node* next = pos._node->_next;
    
    delete pos._node;
    
    // prev - pos - after
    prev->_next = next;
    next->_prev = prev;
    
    return iterator(next);
}
  • list 的插入操作迭代器不会失效,因为迭代器 pos 的值不会改变,始终指向原来的节点。
  • list 的删除操作迭代器一定失效,因为节点已经被释放了,应修正为 pos 下一个位置。

 

3. list和vector对比

容器vectorlist
底层结构连续的物理空间,也就是数组带头双向循环链表,空间不连续
随机访问支持随机访问不支持随机访问
插入删除非尾部的插入删除都要移动数据,效率低 O ( n ) O(n) O(n)任意位置的插入删除,效率高
空间利用率增容代价大,倍数扩容存在一定的空间浪费按需申请空间,不存在浪费
迭代器原生指针支持随机访问构造迭代器类,模拟指针行为,支持双向访问
适用场景需要高效存储,随机访问,不关心增删效率频繁使用插入删除,不关心随机访问

vector 与 list 两种容器各有优劣,实际上 vector 用的更多些。因为 vector 支持随机访问这是最大的优点,其次,空间浪费也不是太严重的缺陷。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐