【C++驾轻就熟】list深入了解及模拟实现
鲨鱼吃橘子 2024-10-23 10:35:07 阅读 76
目录
一、list的介绍及使用
二、标准库中的list类
2.1 list的常见接口说明
2.1.1 list对象的常见构造
1.无参构造函数
2.有参构造函数(构造并初始化n个val)
3.有参构造函数(使用迭代器进行初始化构造)
4.拷贝构造函数
2.1.2 list iterator的使用
1.begin() + end()
2.rbegin() + rend()
2.1.3 list对象的容量操作
1.empty()函数
2.size()函数
2.1.4 list对象的增删查改及访问
1.push_front()函数
2. pop_front()函数
3. push_back()函数
4. pop_back()函数
5. insert()函数
6. erase()函数
7. swap()函数
8. clear()函数
9. front()函数 + back()函数
三、list的迭代器失效
四、list与vector的对比
五、list的模拟实现
结尾
一、list的介绍及使用
list介绍文档
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
二、标准库中的list类
2.1 list的常见接口说明
2.1.1 list对象的常见构造
1.无参构造函数
int main()
{
list<int> l;
return 0;
}
2.有参构造函数(构造并初始化n个val)
<code>list (size_type n, const value_type& val = value_type());
int main()
{
list<int> l(5,10);
return 0;
}
3.有参构造函数(使用迭代器进行初始化构造)
<code>template <class InputIterator>
list (InputIterator first, InputIterator last);
int main()
{
string s("I LOVE YOU");
list<char> l(s.begin(), s.end());
return 0;
}
4.拷贝构造函数
int main()
{
list<int> s(5,10);
list<int> v(s);
return 0;
}
2.1.2 list iterator的使用
1.begin() + end()
<code> iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iterator
iterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator
int main()
{
list<int> l;
for (int i = 0; i < 10; i++)
{
l.push_back(i);
}
list<int>::iterator it = l.begin();
while (it != l.end())
{
*it+=100;
cout << *it << ' ';
++it;
}
cout << endl;
return 0;
}
2.rbegin() + rend()
<code> reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator
reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator
int main()
{
list<int> l;
for (int i = 0; i < 10; i++)
{
l.push_back(i);
}
list<int>::reverse_iterator it = l.rbegin();
while (it != l.rend())
{
*it += 100;
cout << *it << ' ';
++it;
}
cout << endl;
return 0;
}
【注意】 :
begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动 rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
2.1.3 list对象的容量操作
1.empty()函数
<code>bool empty() const; 判断是否为空
int main()
{
list<int> l;
cout << l.empty() << endl;
l.push_back(520);
cout << l.empty() << endl;
return 0;
}
2.size()函数
<code>size_type size() const; 获取数据个数
int main()
{
list<int> l;
cout << l.size() << endl;
for (int i = 0; i < 10; i++)
{
l.push_back(i);
}
cout << l.size() << endl;
return 0;
}
2.1.4 list对象的增删查改及访问
1.push_front()函数
<code>int main()
{
list<int> l;
l.push_front(1);
l.push_front(2);
l.push_front(3);
l.push_front(4);
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
void push_front (const value_type& val); 头插
2. pop_front()函数
<code>void pop_front(); 头删
int main()
{
list<int> l;
l.push_front(1);
l.push_front(2);
l.push_front(3);
l.push_front(4);
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
l.pop_front();
for (auto a : l)
{
cout << a << ' ';
}
return 0;
}
3. push_back()函数
<code>void push_back (const value_type& val); 尾插
int main()
{
list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
4. pop_back()函数
<code>void pop_back(); 尾删
int main()
{
list<int> l;
l.push_back(1);
l.push_back(3);
l.push_back(1);
l.push_back(4);
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
l.pop_back();
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
5. insert()函数
<code>iterator insert (iterator position, const value_type& val);
insert()函数能够在position之前插入val，并返回插入数据位置的 iterator
void insert (iterator position, size_type n, const value_type& val);
insert()函数能够在position之前插入 n 个 val
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
insert()函数能够在position之前插入一段迭代器区间的数据
int main()
{
list<char> l;
string s("Love");
l.push_back('y');
l.push_back('o');
l.push_back('u');
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
// insert()函数能够在position之前插入val，并返回插入数据位置的 iterator
//l.insert(v.begin() + 5, 'v');这是错误的，因为再list中没有支撑迭代器的加法
cout << *(l.insert(l.begin(), '#')) << endl;
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
// insert()函数能够在position之前插入 n 个 val
list<char>::iterator it = l.begin();
for (size_t i = 0; i < 1; i++)
{
++it;
}
l.insert(it, 3, '@');
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
// insert()函数能够在position之前插入一段迭代器区间的数据
l.insert(++l.begin(), s.begin(), s.end());
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
6. erase()函数
<code>iterator erase (iterator position);
erase()函数能够删除在position位的的数据，并返回删除数据后面数据位置的 iterator
iterator erase (iterator first, iterator last);
erase()函数能够删除在迭代器区间 [first,last) 的的数据，并返回删除数据后面数据位置的 iterator
int main()
{
list<int> l;
for (int i = 0; i < 10; i++)
{
l.push_back(i);
}
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
// erase()函数能够删除在position位的的数据
// 并返回删除数据后面数据位置的 iterator
cout << *(l.erase(l.begin())) << endl;
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
// erase()函数能够删除在迭代器区间 [first,last) 的的数据
// 并返回删除数据后面数据位置的 iterator
cout << *(l.erase(++l.begin(), --l.end())) << endl;
for (auto e : l)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
7. swap()函数
交换两个list的数据空间
int main()
{
list<int> l1(5, 20);
list<int> l2(7, 5);
//交换前
for (auto e : l1)
{
cout << "l1 :" << e << ' ';
}
cout << endl;
for (auto e : l2)
{
cout << "l2 :" << e << ' ';
}
cout << endl;
//交换中
l1.swap(l2);
//交换后
for (auto e : l1)
{
cout << "l1 :" << e << ' ';
}
cout << endl;
for (auto e : l2)
{
cout << "l2 :" << e << ' ';
}
cout << endl;
return 0;
}
8. clear()函数
<code>void clear();
清除list中的有效数据
int main()
{
list<int> l(4, 10);
cout << l.size() << endl;
l.clear();
cout << l.size() << endl;
return 0;
}
9. front()函数 + back()函数
reference front();
const_reference front() const;
访问list中的最后一个数据
reference back();
const_reference back() const;
int main()
{
list<int> l;
for (int i = 0; i < 5; i++)
{
l.push_back(i);
}
cout << "front:" << l.front() << endl;
cout << "back:" << l.back() << endl;
return 0;
}
三、list的迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
<code>int main()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后，it所指向的节点已被删除
// 因此it无效，在下一次使用it时，必须先给其赋值
l.erase(it);
++it;
}
return 0;
}
// 改正
int main()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}
四、list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不 同，其主要不同如下：
五、list的模拟实现
<code>#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using namespace std;
namespace lxp
{
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node(const T& val = T())
:_prev(nullptr)
, _next(nullptr)
, _val(val)
{}
};
// typedef __list_iterator<T, T&, T*> iterator;
// typedef __list_iterator<T, const T&, const T*> const_iterator;
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)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp = _node;
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp = _node;
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};
template<class T>
class list
{
public:
typedef list_node<T> Node;
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
list(const list<T>& lt)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* pre = cur->_prev;
Node* next = cur->_next;
pre->_next = cur->_next;
next->_prev = pre;
delete cur;
_size--;
return next;
}
size_t size()
{
return _size;
}
private:
Node* _head;
size_t _size;
};
}
结尾
如果有什么建议和疑问，或是有什么错误，希望大家可以在评论区提一下。
希望大家以后也能和我一起进步！！
如果这篇文章对你有用的话，请大家给一个三连支持一下！！
谢谢大家收看🌹🌹
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。