【C++】STL

1. list的介绍及使用 1.1. list的介绍

list官方文档

list是能够在常数范围内任意位置进行插入和删除的序列容器，并且能够进行双向迭代list的底层是双向链表，双向链表中的每一个元素都储存在独立的节点中，每个节点通过指针进行前后联系list和forward_list相似，不同的地方在于forward_list是单链表，只能够向前迭代与其他容器相比（vector、array、deque），list通常在任意位置插入和删除的执行效率更好与其他序列式容器相比，list、forward_list的最大缺陷在于不能够做到对任意位置的随机访问。例如：我要访问第六个元素，那就必须要从已知的位置（头或尾）开始，迭代到这个位置，这一操作需要线性的开销。并且list中的每一个节点还需要额外的空间来存储关联的信息（这一点在小数据的大链表中体现的比较多） 1.2. list的常见接口

list中接口比较多，我们学习常见的接口并且了解它的底层原理即可：

2. list的迭代器在开始讲解list的常见接口之前，我们先来了解一下list中的迭代器：list中的指针是一个自定义类型的指针，该指针指向list中的某一个节点。

这里补充一个知识，迭代器的实现有两种方式：

直接使用原生指针，如：vector对原生指针进行封装，然后重载原生指针需要用到的运算符list迭代器：

因为指针支持解引用，所以自定义的类中需要重载operator*()可以通过->来访问成员，所以需要重载operator->()指针可以++向后移动，所以需要重载operator++()/operator(int)；至于向前移动，需要根据需要选择呢是否重载operator--()/operator(int)，因为如果是forward_list就不需要这个操作迭代器需要进行是否相等的比较，所以需要重载operator==()和operator!=()我们首先实现一个简单的list的iterator：

函数声明

接口说明

begin+ end

返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器

rbegin+ rend

返回第一个元素的 reverse_iterator, 即 end 位置 ， 返回最后一个元素下一个位置的 reverse_iterator, 即 begin 位置

注意：

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。rebegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。代码语言：javascript复制//节点类

template

struct ListNode

{

ListNode(const T& val = T())

:_pre(nullptr)

,_next(nullptr)

,_val(val)

{ }

ListNode* _pre;

ListNode* _next;

T _val;

};

//迭代器类

template

struct ListIterator

{

typedef ListNode* PNode;

//下面不需要用指针，因为我们要的就是迭代器本身，而并不是迭代器指针

typedef ListIterator Self;

/*typedef T& Ref;

typedef T* Ptr;*/

PNode _node;

ListIterator(PNode node)

:_node(node)

{ }

Ref operator * ()

{

return _node->_val;

}

Ptr operator -> ()

{

//返回的节点数据的地址

return &_node->_val;

}

Self& operator ++ ()

{

_node = _node->_next;

return *this;

}

Self operator ++ ()

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self& operator -- ()

{

_node = _node->_pre;

return *this;

}

Self operator -- ()

{

Self tmp(*this);

_node = _node->_pre;

return tmp;

}

bool operator == (const Self& it)

{

return _node == it._node;

}

bool operator != (const Self& it)

{

return _node != it._node;

}

};3. list的构造

构造函数(constructor)

接口说明

list()

构造空的 list

list (size_type n, const value_type& val = value_type())

构造的 list 中包含 n 个值为 val 的元素

list (const list& x)

拷贝构造函数

list (InputIterator first, InputIterator last)

用 [first, last) 区间中的元素构造 list

构造空的list：

//构造空的list list() { _head = new Node(); _head->_next = _head; _head->_pre = _head; }

拷贝构造函数

//拷贝构造 list(const list& it) { _head = new Node(); _head->_next = _head; _head->_pre = _head; for (auto i : it) { push_back(i); } }

使用first、last区间构造

//使用first、last区间构造 template list(InputIterator first, InputIterator last) { _head = new Node(); _head->_next = _head; _head->_pre = _head; while (first != last) { push_back(*first); ++first; } }

析构函数

~list() { clear(); delete _head; _head = nullptr; }

4. list capacity

函数声明

接口说明

empty

检测 list 是否为空，是返回 true ，否则返回 false

size

返回 list 中有效节点的个数

5. list常见接口函数声明

接口说明

push_front

在 list 首元素前插入值为 val 的元素

pop_front

删除 list 中第一个元素

push_back

在 list 尾部插入值为 val 的元素

pop_back

删除 list 中最后一个元素

insert

在 list position 位置中插入值为 val 的元素

erase

删除 list position 位置的元素

swap

交换两个 list 中的元素

clear

清空 list 中的有效元素

5.1. insert步骤：

先创建一个newnode来接收x然后创建两个指针pre（指向pos位置的前一个结点），cur（指向pos位置）然后进行newnod、cur、pre三个结点的连接代码语言：javascript复制iterator insert(iterator pos, const T& x)

{

Node* newnode = new Node(x);

Node* cur = pos._node;

Node* pre = cur->_pre;

//连接

pre->_next = newnode;

newnode->_pre = pre;

newnode->_next = cur;

cur->_pre = newnode;

return newnode;

}

5.2. push_front、push_back代码语言：javascript复制//push_front

void push_front(const T& x)

{

inserta(begin(), x);

}

//push_back

void push_back()

{

insert(end(), x);

}

5.3. earse步骤：

首先创建三个指针cur（pos位置）、pre（pos前一个位置）、next（pos后一个位置）然后连接pre和next释放掉cur指针，然后返回next指向结点的迭代器代码语言：javascript复制//earse

iterator earse(iterator pos)

{

assert(pos != end());

Node* cur = pos->_node;

Node* pre = cur->_pre;

Node* next = cur->_next;

//连接pre、next

pre->_next = next;

next->_pre = pre;

delete cur;

return iterator(next);

}

5.4. pop_front、pop_back代码语言：javascript复制//头删

void pop_front()

{

earse(begin());

}

//尾删

void pop_back()

{

earse(end());

}

5.5. swap其实list的交换非常简单，因为我们发现，list类中只有一个成员变量_head，所以我们只需要交换_head的值即可：

代码语言：javascript复制void Swap(list& l)

{

std::swap(_head, l->_head);

}

5.6. clear将链表的每一个节点释放掉即可，可是使用迭代器然后earse：

代码语言：javascript复制void clear()

{

iterator it = begin();

while (it != end())

{

it = erase(it);

}

}6. list的迭代器失效

之前和大家讲过，我们可以将迭代器粗浅地先看做指针，而迭代器失效是因为是迭代器指向的空间被释放了。但是list的底层是一个包含头结点的双向链表，所以在插入元素的时候不存在扩容的操作，所以是不会导致迭代器失效的。只有在删除结点的时候才会导致迭代器失效，并且失效的只有被删除的一个结点，其他迭代器不会受到影响。

来看一下这段代码：

代码语言：javascript复制void TestListIterator1()

{

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };

list l(array, array + sizeof(array) / sizeof(array[0]));

auto it = l.begin();

while (it != l.end())

{

// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值

l.erase(it);

++it;

}

}会出现访问异常：

修改之后的代码：

代码语言：javascript复制void TestListIterator1()

{

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };

list l(array, array + sizeof(array) / sizeof(array[0]));

auto it = l.begin();

while (it != l.end())

{

// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值

l.erase(it++);

//++it;

}

}7.list和vector的对比 vectorlist 底

层

结

构

动态顺序表，一段连续空间

带头结点的双向循环链表

随

机

访

问支持随机访问，访问某个元素效率 O(1)不支持随机访问，访问某个元素

效率 O(N) 插

入

和

删

除

任意位置插入和删除效率低，需要搬移元素，时间复杂

度为 O(N) ，插入时有可能需要增容，增容：开辟新空

间，拷贝元素，释放旧空间，导致效率更低

任意位置插入和删除效率高，不 需要搬移元素，时间复杂度为

O(1)

空

间

利

用

率

底层为连续空间，不容易造成内存碎片，空间利用率

高，缓存利用率高

底层节点动态开辟，小节点容易 造成内存碎片，空间利用率低，缓存利用率低

迭

代

器

原生态指针

对原生态指针 ( 节点指针 ) 进行封装

迭

代

器

失

效

在插入元素时，要给所有的迭代器重新赋值，因为插入

元素有可能会导致重新扩容，致使原来迭代器失效，删

除时，当前迭代器需要重新赋值否则会失效

插入元素不会导致迭代器失效，

删除元素时，只会导致当前迭代

器失效，其他迭代器不受影响

使

用

场

景

需要高效存储，支持随机访问，不关心插入删除效率 大量插入和删除操作，不关心随

机访问

（本篇完）