【C++笔记】list使用详解及模拟实现
前言
各位读者朋友们大家好！上期我们讲了vector的使用以及底层的模拟实现，这期我们来讲list。
目录
- 前言
- 一. list的介绍及使用
- 1.1 list的介绍
- 1.2 list的使用
- 1.2.1 list的构造
- 1.2.2 list iterator的使用
- 1.2.3 list capacity
- 1.2.4 list element access
- 1.2.5 list modifiers
- 二. list的模拟实现
- 2.1 list的底层结构
- 2.2 普通迭代器
- 2.3 const迭代器
- 2.4 insert
- 2.5 erase
- 2.6 迭代器失效
- 2.7 list的析构函数
- 2.9 list的构造函数
- 2.8 operator=
- 三. 按需实例化
- 四. initializer_list
- 五. list.h
- 结语
一. list的介绍及使用
1.1 list的介绍
list的文档
这里的list就是双向带头循环链表
1.2 list的使用
list的接口较多，我们要先掌握如何正确的使用，然后再去深入研究底层的原理，以达到可扩展的能力。以下是list的一些常见的重要接口。
1.2.1 list的构造
| 构造函数(Constructor) | 接口说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list(const list& x) | 拷贝构造 |
| list(InputItetator first,InputIterator last) | 用一段迭代器区间构造list |
- list (size_type n, const value_type& val = value_type())
- list()
- list(const list& x)
- list(InputItetator first,InputIterator last)
1.2.2 list iterator的使用
这里我们暂时将list的迭代器理解为指针，该指针指向list中的某一节点
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator，即end位置的迭代器+返回begin位置前一个位置的迭代器 |
可以看到这里的list的迭代器是双向的迭代器
如果想在某个位置插入元素就不能对迭代器进行+运算了
这里我们在第三个位置之前插入1314，要对begin进行三次自加，而不能使用begin+3
list<int> l(5, 520);
int k = 3;
list<int>::iterator it = l.begin();
while (k--)
{
++it;
}
l.insert(it, 1314);
for (auto a : l)
{
cout << a << " ";
}
cout << endl;
1.2.3 list capacity
| 函数声明 | 接口说明 |
|---|---|
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list的有效节点个数 |
void test_list2()
{
list<int> l1,l2;
if (l1.empty())
{
cout << "true" << endl;
cout << l1.size() << endl;
}
else
{
cout << "false" << endl;
cout << l1.size() << endl;
}
l2.push_back(1314);
cout << l2.size() << endl;
}
1.2.4 list element access
| 函数声明 | 接口说明 |
|---|---|
| front | 返回list的第一个节点中的值的引用 |
| back | 返回list的最后一个节点中的值的引用 |
void test_list3()
{
list<int> l;
l.push_back(520);
l.push_back(520);
l.push_back(520);
l.push_back(520);
for (auto a : l)
{
cout << a << " ";
}
cout << endl;
l.front() = 1314;
l.back() = 1314;
for (auto a : l)
{
cout << a << " ";
}
}
将第一个和最后一个位置的值改为了1314
1.2.5 list modifiers
| 函数声明 | 接口说明 |
|---|---|
| push_front | 在list首元素之前插入值为val的元素 |
| pop_front | 删除list的第一个元素 |
| push_back | 尾插值为val的元素 |
| emplace_back | 尾插一个元素 |
| pop_back | 将list的最后一个元素删除 |
| insert | 在pos位置插入值为val的元素 |
| erase | 删除pos位置的元素 |
-
push_front
-
pop_front
-
push_back 和 pop_back
-
emplace_back
emplace_back在功能上跟push_back类似。但是emplace_back支持直接构造，不用再拷贝构造了，在最后一种情况下emplace_back比push_back高效。 -
insert 和 erase
-
splice
将一个链表插到另一个链表的指定位置
void test_list4()
{
list<int> lt1,lt2;
lt1.push_back(520);
lt1.push_back(520);
lt2.push_back(1314);
lt2.push_back(1314);
lt1.splice(lt1.begin(), lt2);
for (auto a : lt1)
{
cout << a << " ";
}
cout << endl;
for (auto a : lt2)
{
cout << a << " ";
}
}
插入后lt2就被置空了。
这一接口也可以用来调整结点的顺序
- merge
这一功能的实现的是有序链表的合并
将大的尾插到一个头节点后最后将头节点接到lt1上
上面就讲完了list常用接口的使用，下面我们开始模拟实现list
二. list的模拟实现
2.1 list的底层结构
template <class T>// 链表的节点
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
private:
Node* _head;
size_t _size;
};
2.2 普通迭代器
因为list的节点在内存中不是连续存储的，因此不能使用原生指针作为迭代器，我们可以封装一个类来作为迭代器，通过运算符重载来实现迭代器的功能。
template <class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator -> ()
{
return &_node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator++(int)// 后置++
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return *this;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
};
2.3 const迭代器
但是这样要写成两个类，而且两个类的方法只有两个不同，很是冗余，有没有方法能实现成一个类呢？
我们看一下库里是如何实现的：
template <class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T,Ref,Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ptr operator -> ()
{
return &_node->_data;
}
Ref operator*()
{
return _node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator++(int)// 后置++
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return *this;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
};
写一段程序来体现一下实例化的过程
2.4 insert
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
// prev newnode cur
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
++_size;
return newnode;
}
有了insert我们可以服复用hinsert来实现push_back和push_front
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
2.5 erase
将pos节点的前节点和后节点相连然后将pos节点释放即可
iterator erase(iterator pos)
{
assert(pos != end());
Node* next = pos._node->_next;
Node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
--_size;
return next;
}
有了erase就可以复用erase来实现pop_back和pop_front了
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
2.6 迭代器失效
2.7 list的析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
将所有节点删除之后再将头结点释放
2.9 list的构造函数
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(const list<T>& tmp)
{
empty_init();
for (auto& a : tmp)
{
push_back(a);
}
}
构造一个头节点，将tmp的节点尾插到头节点后
2.8 operator=
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
依旧是现代写法
三. 按需实例化
编译器在对模板进行实例化的时候，使用哪些成员函数就实例化哪些成员函数，不会全部实例化。
四. initializer_list
C++11中支持下面的写法：
不需要一直push_back数据，这里是因为支持了initializer_list
initializer_list底层是两个指针，第一个指针指向第一个数据，第二个指针指向最后一个数据的下一位置
我们写的list如果要支持这种写法需要写一个新的构造函数
list(initializer_list<T> il)
{
empty_init();
for (auto& a : il)
{
push_back(a);
}
}
跟普通的构造函数一样，只是参数变了而已，最正确的写法应该如下，因为我们是构造函数
这样就是隐式类型转换了
所以就有了下面的玩法：
五. list.h
namespace Yuey
{
template <class T>// 链表的节点
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
};
template <class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ptr operator -> ()
{
return &_node->_data;
}
Ref operator*()
{
return _node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator++(int)// 后置++
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return *this;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
};
struct AA
{
int _a1 = 520;
int _a2 = 1314;
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(initializer_list<T> il)
{
empty_init();
for (auto& a : il)
{
push_back(a);
}
}
list(const list<T>& tmp)
{
empty_init();
for (auto& a : tmp)
{
push_back(a);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return _head;
}
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
// prev newnode cur
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
++_size;
return newnode;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* next = pos._node->_next;
Node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
--_size;
return next;
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
private:
Node* _head;
size_t _size;
};
}
结语
以上我们就讲完了list的用法以及模拟实现，希望对大家有所帮助，感谢大家的阅读，欢迎大家批评指正！