目录
目录
迭代器
1.意义
2.分类
（1）单向迭代器
（2）双向迭代器
（3）随机迭代器
list
list的使用
1.构造
2.容量
3.访问和遍历（list不支持[ ]下标访问）
4.修改
5.操作
list模拟实现
1.list结点
2.list的迭代器封装
3.list的反向迭代器封装
4.list的主体实现
小知识
1.类型判断
2.跨平台性
迭代器
1.意义
为了不暴露容器的底层结构，让使用者无需关心容器的底层结构，让使用变得简单。
2.分类
迭代器要么是指针，要么是指针的封装
（1）单向迭代器
只支持++操作的迭代器
例：单链表、哈希表等
（2）双向迭代器
支持++ --操作的迭代器
例：list、map、set等
（3）随机迭代器
支持++ -- + - [ ]操作，也就是随机访问操作。
例：vector、string、deque（双端队列）等
list
底层为双向带头循环链表
list的使用
1.构造
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
2.容量
（1）empty
判断容器是否为空
（2）size
返回容器有效数据个数
（3）max_size
返回理论上当前系统环境下能够容纳的最大元素个数。
3.访问和遍历（list不支持[ ]下标访问）
（1）front
返回list的第一个节点的值的引用
（2）back
返回list的最后一个节点的值的引用
（3）迭代器
begin（）
返回第一个元素的迭代器
end（）
返回最后一个元素下一个位置的迭代器
rbegin（）
返回第一个元素的reserve_iterator，即end（）的位置
rend（）
返回最后一个元素的reserve_iterator，即begin（）的位置
begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
（4）范围for
（5）迭代器失效
因为list底层结构为双向带头循环链表，所以插入数据是不会导致迭代器失效的，只有在删除时迭代器才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
4.修改
（1）push_front 头插
（2）push_back 尾插
（3）pop_front 头删
（4）pop_back 尾删
（5）insert 插入
（6）erase 删除
（7）swap 交换
（8）clear 清空
（9）assign 赋值
三种使用方式
（10）emplace 支持多参数的插入，但不支持初始化列表 还有emplace_front emplace_back
注意插入的数据要与类的参数列表相匹配。
5.操作
（1）find 使用算法库#include<algorithm>中的
（2）splice 移动某些节点到某个位置
（3）remove 删除全部指定值的节点
（4）merge 合并两个有序链表为一个
（5）unique 去重，只能去掉挨着的重复 通常与sort结合使用，先sort再unique去掉所有重复
（6）sort list的sort底层为归并排序，效率不如算法库中的sort
list模拟实现
1.list结点
template<class T>
struct list_node
{
list_node(const T& val = T()) //T() 为匿名对象
:_val(val)
{ }list_node<T>* _prev = nullptr;
list_node<T>* _next = nullptr;
T _val;
};
2.list的迭代器封装
template<class T,class ref,class ptr>
class Iiterator
{
typedef list_node<T> Node;typedef Iiterator<T, ref, ptr> Iterator;
public:
Node* _node;Iiterator(Node* node = nullptr)
:_node(node)
{}ref operator*()
{
return _node->_val;
}ptr operator->()
{
return &(operator*());
}Iterator& operator++()
{
_node = _node->_next;
return *this;
}Iterator operator++(int)
{
Iterator tmp(*this);
_node = _node->_next;
return tmp;
}Iterator& operator--()
{
_node = _node->_prev;
return *this;
}Iterator operator--(int)
{
Iterator tmp(*this);
_node = _node->_prev;
return tmp;
}bool operator!=(const Iterator& tmp) const
{
return _node != tmp._node;
}bool operator==(const Iterator& tmp) const
{
return _node == tmp._node;
}};
3.list的反向迭代器封装
template <class iterator, class ref, class ptr>
class Reverse_iterator
{
public:
iterator _it;
typedef Reverse_iterator<iterator, ref, ptr> self;Reverse_iterator(iterator it)
:_it(it)
{}ref operator*()
{
iterator tmp(_it);
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& that) const
{
return _it != that._it;
}bool operator==(const self& that) const
{
return _it == that._it;
}};
4.list的主体实现
template<class T>
class list
{typedef list_node<T> Node;
Node* _head;
size_t _size;void create_head()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}//正向迭代器
typedef Iiterator<T, T&, T*> iterator;
typedef Iiterator<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()
{
create_head();
}list(int n, const T& val = T())
{
create_head();
while (n--)
push_back(val);
}list(size_t n, const T& val = T())
{
create_head();
while (n--)
push_back(val);
}template<class Iterator>
list(Iterator first, Iterator last)
{
create_head();
while (first != last)
{
push_back(*first);
first++;
}
}list(const list<T>& l)
{
create_head();list<T> tmp(l.begin(), l.end());
this->swap(tmp);
}void swap(LList::list<T>& tmp)
{
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}~list()
{
clear();
delete _head;
_head = nullptr;
}
//迭代器
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(_head);
}reverse_iterator rend()
{
return reverse_iterator(_head->_next);
}const_reverse_iterator rbegin()const
{
return const_reverse_iterator(_head);
}const_reverse_iterator rend() const
{
return const_reverse_iterator(_head->_next);
}//容量
size_t size()
{
return _size;
}bool empty()
{
return _head == _head->next;
}void resize(size_t newsize, const T& data = T())
{
if (newsize <= size())
{
while (newsize < size())
pop_back();
}
else
{
while (size() < newsize)
{
push_back(data);
}
}
}
//访问
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;
}
//插入和删除
void push_back(const T& val)
{
insert(end(), val);
}void push_front(const T& val)
{
insert(begin(), val);
}void pop_back()
{
erase(--end());
}void pop_front()
{
erase(begin());
}iterator insert(iterator pos, const T& val)
{
Node* newnode = new Node;newnode->_val = val;
newnode->_prev = pos._node->_prev;
newnode->_next = pos._node;
pos._node->_prev->_next = newnode;
pos._node->_prev = newnode;_size++;
return iterator(newnode);
}iterator erase(iterator pos)
{
Node* tmpnode = pos._node;
pos++;tmpnode->_prev->_next = tmpnode->_next;
tmpnode->_next->_prev = tmpnode->_prev;delete tmpnode;
_size--;
return pos;
}void clear()
{
Node* cur = _head->_next;while (cur != _head)
{
_head->_next = cur->_next;
delete cur;
cur = _head->_next;
}
_size = 0;
_head->_prev = _head->_next = _head;
}};
}
小知识
1.类型判断
C++的<typeinfo> 头文件中的typeid函数可以判断类型
例： typeid（n）==typeid(int) 判断n这个数据的类型是否为int
2.跨平台性
因为不同平台命名可能不同，为了在不同平台上运行，不能直接访问vector的_size成员变量，而是用size（）成员函数
