C++ 复习总结记录九
C++ 复习总结记录九
主要内容
1、list 介绍及使用
2、list 剖析及模拟实现
3、list 与 vector 对比
一 list 介绍及使用
List 相关文档
1、List 在任意位置进行插入和删除的序列式容器 O(1) ，且该容器可前后双向迭代
2、List 底层是带头双向循环链表，每个元素存储在互不相关的独立节点中，通过指针指向其前一个元素和后一个元素
3、List 与 Forward_List 相似，主要不同在于 Forward_List 是单链表，只能正向迭代更简单高效
4、与其他的序列式容器相比 ( array，vector，deque )，List 通常在任意位置进行插入、移除元素的执行效率更好。
但缺陷是不支持任意位置的随机访问，比如：要访问 List 的第 6 个元素，必须从已知位置 ( 比如头部或者尾部 ) 迭代到该位置，在这段位置上迭代需要线性的时间开销；List 还需要一些额外的空间，以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 List 来说这可能是一个重要的因素 )
1.1 list 构造
构造函数(constructor) 接口说明
list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list() 构造空的list
list (const list& x) 拷贝构造函数
list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
1.2 list iterator 的使用
迭代器其实就是节点的指针，但 list 指针的类型应该是 NODE* 而非 T* 需特别注意（像 string，vector 的迭代器就是 T*）
函数声明 接口说明
begin + end 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend 返回第一个元素的 reverse_iterator, 即 end 位置，返回最后一个元素下一个位置的 reverse_iterator, 即 begin 位置
begin 和 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动
rbegin 与 rend 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动
如下图，这里要注意 list 迭代器的 begin + end 和 vector 的区别（list 拥有头节点，所以 begin 返回第一个元素的迭代器，即头节点后一个位置）
1.3 list capacity
函数声明 接口说明
empty 检测 list 是否为空, 是返回 true, 否则返回 false
size 返回 list 中有效节点的个数
1.4 list element access
函数声明 接口说明
front 返回 list 的第一个节点中值的引用
back 返回 list 的最后一个节点中值的引用
1.5 list modifiers
函数声明 接口说明
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 中的有效元素
1.6 list 迭代器失效
迭代器失效即迭代器所指向的节点的无效，list 底层结构为带头结点的双向循环链表，因此在 list 中进行插入时不会导致 list 的迭代器失效，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
void TestListIterator()
{
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;
}
}
// 改正
void TestListIterator()
{
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 剖析及模拟实现
2.1 模拟实现
迭代器有两种实现方式，具体应根据容器底层数据结构实现
① 原生态指针，比如 vector
② 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法
- 指针可以解引用，迭代器的类中必须重载 operator*()
- 指针可以通过 -> 访问其所指空间成员，迭代器类中必须重载 oprator->()
- 指针可以 ++ 向后移动，迭代器类中必须重载 operator++() 与 operator++(int)，至于 operator–() / operator–(int) 根据具体结构抉择，双向链表可以向前移动，需要重载，forward_list 则不需重载
- 迭代器需要进行是否相等的比较，因此还需要重载 operator==() 与 operator!=()
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
namespace lucky
{
// List 的节点类
template<class T>
struct ListNode
{
ListNode(const T& val = T())
: _prev(nullptr)
, _next(nullptr)
, _val(val)
{}
ListNode<T>* _prev;
ListNode<T>* _next;
T _val;
};
template<class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
// Ref 和 Ptr 类型需要重定义下，实现反向迭代器时需要用到
public:
typedef Ref Ref;
typedef Ptr Ptr;
public:
// 构造
ListIterator(Node* node = nullptr)
: _node(node)
{}
// 具有指针类似行为
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(operator*());
}
// 迭代器支持移动
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self temp(*this);
_node = _node->_next;
return temp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self temp(*this);
_node = _node->_prev;
return temp;
}
// 迭代器支持比较
bool operator!=(const Self& l)const
{
return _node != l._node;
}
bool operator==(const Self& l)const
{
return _node == l._node;
}
Node* _node;
};
template<class Iterator>
class ReverseListIterator
{
// 注意：此处 typename 的作用是明确告诉编译器, Ref 是 Iterator 类中的一个类型，而不是静态成员变量
// 否则编译器编译时就不知道 Ref 是 Iterator 中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名的方式访问的
public:
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef ReverseListIterator<Iterator> Self;
public:
// 构造
ReverseListIterator(Iterator it)
: _it(it)
{}
// 具有指针类似行为
Ref operator*()
{
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->()
{
return &(operator*());
}
// 迭代器支持移动
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self temp(*this);
--_it;
return temp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
// 迭代器支持比较
bool operator!=(const Self& l)const
{
return _it != l._it;
}
bool operator==(const Self& l)const
{
return _it == l._it;
}
Iterator _it;
};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
// 正向迭代器
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;
// 反向迭代器
typedef ReverseListIterator<iterator> reverse_iterator;
typedef ReverseListIterator<const_iterator> const_reverse_iterator;
public:
// List 的构造
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
CreateHead();
for (int i = 0; i < n; ++i)
push_back(value);
}
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& l)
{
CreateHead();
// 用 l 中的元素构造临时的 temp, 然后与当前对象交换
list<T> temp(l.begin(), l.end());
this->swap(temp);
}
list<T>& operator=(list<T> l)
{
this->swap(l);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
// List 的迭代器
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());
}
// List 容量相关
size_t size() const
{
Node* cur = _head->_next;
size_t count = 0;
while (cur != _head)
{
count++;
cur = cur->_next;
}
return count;
}
bool empty() const
{
return _head->_next == _head;
}
void resize(size_t newsize, const T& data = T())
{
size_t oldsize = size();
if (newsize <= oldsize)
{
// 有效元素个数减少到newsize
while (newsize < oldsize)
{
pop_back();
oldsize--;
}
}
else
{
while (oldsize < newsize)
{
push_back(data);
oldsize++;
}
}
}
// List 元素访问操作
// 注意: List不支持 operator[]
T& front()
{
return _head->_next->_val;
}
const T& front() const
{
return _head->_next->_val;
}
T& back()
{
return _head->_prev->_val;
}
const T& back() const
{
return _head->_prev->_val;
}
// List 插入和删除
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)
{
Node* pNewNode = new Node(val);
Node* pCur = pos._node;
// 先将新节点插入
pNewNode->_prev = pCur->_prev;
pNewNode->_next = pCur;
pNewNode->_prev->_next = pNewNode;
pCur->_prev = pNewNode;
return iterator(pNewNode);
}
// 删除 pos 位置的节点, 返回该节点的下一个位置
iterator erase(iterator pos)
{
// 找到待删除的节点
Node* pDel = pos._node;
Node* pRet = pDel->_next;
// 将该节点从链表中拆下来并删除
pDel->_prev->_next = pDel->_next;
pDel->_next->_prev = pDel->_prev;
delete pDel;
return iterator(pRet);
}
void clear()
{
Node* cur = _head->_next;
// 采用头删除删除
while (cur != _head)
{
_head->_next = cur->_next;
delete cur;
cur = _head->_next;
}
_head->_next = _head->_prev = _head;
}
void swap(lucky::list<T>& l)
{
std::swap(_head, l._head);
}
private:
void CreateHead()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
private:
Node* _head;
};
}
// 对模拟实现的 list 进行测试
// 正向打印链表
template<class T>
void PrintList(const lucky::list<T>& l)
{
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
// 测试 List 的构造
void TestList1()
{
lucky::list<int> l1;
lucky::list<int> l2(10, 5);
PrintList(l2);
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
lucky::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
PrintList(l3);
lucky::list<int> l4(l3);
PrintList(l4);
l1 = l4;
PrintList(l1);
}
// PushBack() / PopBack() / PushFront() / PopFront()
void TestList2()
{
// 测试 PushBack 与 PopBack
lucky::list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
PrintList(l);
l.pop_back();
l.pop_back();
PrintList(l);
l.pop_back();
cout << l.size() << endl;
// 测试 PushFront 与 PopFront
l.push_front(1);
l.push_front(2);
l.push_front(3);
PrintList(l);
l.pop_front();
l.pop_front();
PrintList(l);
l.pop_front();
cout << l.size() << endl;
}
// 测试 insert 和 erase
void TestList3()
{
int array[] = { 1, 2, 3, 4, 5 };
lucky::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto pos = l.begin();
l.insert(l.begin(), 0);
PrintList(l);
++pos;
l.insert(pos, 2);
PrintList(l);
l.erase(l.begin());
l.erase(pos);
PrintList(l);
// pos 指向的节点已经被删除，pos迭代器失效
cout << *pos << endl;
auto it = l.begin();
while (it != l.end())
{
it = l.erase(it);
}
cout << l.size() << endl;
}
// 测试反向迭代器
void TestList4()
{
int array[] = { 1, 2, 3, 4, 5 };
lucky::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto rit = l.rbegin();
while (rit != l.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
const lucky::list<int> cl(l);
auto crit = l.rbegin();
while (crit != l.rend())
{
cout << *crit << " ";
++crit;
}
cout << endl;
}
2.2 list 反向迭代器
反向迭代器的 ++ 就是正向迭代器的 --，因此反向迭代器的实现可以借助正向迭代器，即反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可
template<class Iterator>
class ReverseListIterator
{
public:
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef ReverseListIterator<Iterator> Self;
public:
// 构造
ReverseListIterator(Iterator it): _it(it){}
// 具有指针类似行为
Ref operator*(){
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->(){ return &(operator*());}
// 迭代器支持移动
Self& operator++(){
--_it;
return *this;
}
Self operator++(int){
Self temp(*this);
--_it;
return temp;
}
Self& operator--(){
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
// 迭代器支持比较
bool operator!=(const Self& l)const{ return _it != l._it;}
bool operator==(const Self& l)const{ return _it ==l._it;}
Iterator _it;
};
三 list 与 vector 对比
vector 与 list 都是 STL 中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下
