文章目录
- 1. 介绍
- 2. list类的使用
-
- 2.1 list类对象的构造函数
- 2.2 list类对象的容量操作
- 2.3 list类对象的修改操作
- 2.4 list类对象的访问及遍历操作
- 3. list类的模拟实现
1. 介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
与其他的序列式容器相比（array，vector，deque），list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息（对于存储类型较小元素的大list来说这可能是一个重要的因素）。
图示：
想要具体了解其底层数据结构可以参照：线性表之双向链表
2. list类的使用
2.1 list类对象的构造函数
| (constructor)构造函数代码 | 功能说明 |
|---|---|
| （默认构造函数）构造一个空的容器，没有任何元素。 | |
| （填充构造函数）构造一个具有 n 个元素的容器。每个元素都是 val 的副本。 | |
| （范围构造函数）构造一个与范围 |
|
| （拷贝构造函数）构造一个与 x 中的每个元素副本相同顺序的容器。 |
实例：
// constructing lists
#include <iostream>
#include <list>
int main()
{
// 按照上述描述的顺序使用的构造函数
std::list<int> first; // empty list of ints
std::list<int> second(4, 100); // four ints with value 100
std::list<int> third(second.begin(), second.end()); // iterating through second
std::list<int> fourth(third); // a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[] = { 16,2,77,29 };
std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
std::cout << "The contents of fifth are: ";
for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
std::cout << *it << ' ';
std::cout << '
';
return 0;
}
输出结果：
2.2 list类对象的容量操作
| 函数名称 | 代码 | 功能说明 |
|---|---|---|
| empty | 返回 list 容器是否为空（即其大小是否为0）。 | |
| size | 返回 list 容器中元素的个数。 | |
| max_size | 返回 list 容器中可以容纳的最大元素的数量。 |
2.3 list类对象的修改操作
| 函数名称 | 代码 | 功能说明 |
|---|---|---|
| assign | 对 list 容器进行赋值，替换其当前内容，并相应地修改其大小。 | |
| push_front | 在 list 容器开头插入一个新元素 val。 | |
| pop_front | 删除 list 容器中第一个元素。 | |
| push_back | 在 list 容器最后插入一个新元素 val。 | |
| pop_back | 删除 list 容器中最后一个元素。 | |
| insert | 在指定位置 position 之前插入新元素 val、n 个 val或者迭代器区间 |
|
| erase | 删除 position 位置的元素或者迭代器区间 |
|
| swap | 与另一个相同类型的 list 容器 x 交换内容。存在一个同名的非成员函数 swap，重载该算法的意义是优化交换时间。 | |
| resize | 改变容器的大小，使其包含 n 个元素。如果 n 小于当前容器的大小，则内容将被缩减为其前 n 个元素，并移除超出范围的元素。如果 n 大于当前容器的大小，则通过在末尾插入所需数量的元素来扩展内容，使其大小达到 n。如果指定了 val，则新元素将被初始化为 val 的副本；否则，它们将进行值初始化。 | |
| clear | 从 list 容器中移除所有元素，使容器的大小变为0。 |
2.4 list类对象的访问及遍历操作
| 函数名称 | 代码 | 功能说明 |
|---|---|---|
| front | 返回 list 容器中第一个元素的引用。 | |
| back | 返回 list 容器中最后一个元素的引用。 |
遍历操作
#include <iostream>
#include <list>
int main()
{
std::list<int> lt(10, 100);
// 1. 迭代器遍历
for (std::list<int>::iterator it = lt.begin(); it != lt.end(); ++it)
std::cout << *it << " ";
std::cout << '
';
// 2. 范围for遍历
for (auto e : lt)
std::cout << e << " ";
std::cout << '
';
return 0;
}
运行结果：
解释
- 迭代器遍历：
- 首先，通过
lt.begin() 获取列表的起始迭代器，lt.end() 获取列表的结束迭代器。- 使用
std::list<int>::iterator it 定义一个迭代器变量，并将其初始化为列表的起始迭代器。- 使用迭代器变量
it 进行循环迭代，从列表的起始位置迭代到结束位置（不包括结束位置）。- 在循环中，通过
*it 访问当前迭代器指向的元素，并输出到标准输出流std::cout 中。
- 范围for循环遍历：
- 使用
auto 关键字和范围for循环语法，遍历列表lt 中的每个元素。- 在每次迭代中，将当前元素赋值给变量
e 。- 在循环体内，输出变量
e 的值到标准输出流std::cout 中。
3. list类的模拟实现
#pragma once
#include<iostream>
using namespace std;
namespace my_list
{
// List的节点类
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_pPre(nullptr)
,_pNext(nullptr)
,_val(val)
{}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
//List的迭代器类
template<class T, class Ref, class Ptr>
class List_iterator
{
typedef ListNode<T>* PNode;
typedef List_iterator<T, Ref, Ptr> Self;
public:
List_iterator(PNode pNode = nullptr)
{
_pNode = pNode;
}
List_iterator(const Self& l)
{
_pNode = l._pNode;
}
Ref operator*()
{
return _pNode->_val;
}
Ptr operator->()
{
return &_pNode->_val;
}
Self& operator++()
{
_pNode = _pNode->_pNext;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_pNode = _pNode->_pNext;
return tmp;
}
Self& operator--()
{
_pNode = _pNode->_pPre;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_pNode = _pNode->_pPre;
return tmp;
}
bool operator!=(const Self& l)
{
return _pNode != l._pNode;
}
bool operator==(const Self& l)
{
return _pNode == l._pNode;
}
PNode GetNode()
{
return _pNode;
}
private:
PNode _pNode;
};
// 反向迭代器——对正向迭代器的接口进行包装
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Reverse_iterator() {}
Reverse_iterator(Iterator it)
: _it(it)
{}
Ref operator*()
{
Iterator tmp(_it);
--tmp;
return *tmp;
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--() {
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
bool operator==(const Self& s)
{
return _it == s._it;
}
};
//list类
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* PNode;
public:
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;
public:
///
// List Iterator
iterator begin()
{
return _pHead->_pNext;
}
iterator end()
{
return _pHead;
}
const_iterator begin() const
{
return const_iterator(_pHead->_pNext);
}
const_iterator end() const
{
return const_iterator(_pHead);
}
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());
}
///
// List 构造/赋值
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
CreateHead();
while (n--)
{
push_back(value);
}
_size = n;
}
list(int n, T& value = T())
{
CreateHead();
while (n--)
{
push_back(value);
}
_size = n;
}
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
while (first != last)
{
push_back(*first);
first++;
_size++;
}
}
list(const list<T>& l)
{
CreateHead();
for (auto it : l)
{
push_back(it);
_size++;
}
}
void swap(list<T>& l)
{
std::swap(this->_pHead, l._pHead);
std::swap(this->_size, l._size);
}
list<T>& operator=(list<T> l)
{
swap(l);
return *this;
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
///
// List Capacity
size_t size()const
{
return _size;
}
bool empty()const
{
return _size == 0;
}
// List Access
T& front()
{
assert(!empty());
return _pHead->_pNext->_val;
}
const T& front()const
{
assert(!empty());
return _pHead->_pNext->_val;
}
T& back()
{
assert(!empty());
return _pHead->_pPre->_val;
}
const T& back()const
{
assert(!empty());
return _pHead->_pPre->_val;
}
// List Modify
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode tmp = new Node(val);
PNode cur = pos.GetNode();
PNode pre = cur->_pPre;
tmp->_pNext = cur;
tmp->_pPre = pre;
pre->_pNext = tmp;
cur->_pPre = tmp;
_size++;
return tmp;
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode cur = pos.GetNode();
PNode next = cur->_pNext;
PNode pre = cur->_pPre;
delete cur;
pre->_pNext = next;
next->_pPre = pre;
_size--;
return next;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
private:
// 创建头结点
void CreateHead()
{
_pHead = new Node;
_pHead->_pNext = _pHead->_pPre = _pHead;
}
PNode _pHead;
size_t _size = 0;
};
};
注意
这里实现的反向迭代器类模板同样也可以适配到vector类和string类中。