list的基本使用以及模拟实现

list的基本使用

本质为双向带头循环列表

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向带头循环链表，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
4. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list<int> lst;
list<char> lst2(5, 'a');//五个a
char str[] = "12345";
list<char> lst3(str, str + 5);//12345
list<int> lst4(list2.begin(), list2.end());//aaaaa
list<char> copy(lst3);//12345
list<char>::iterator it = lst3.begin();
while( it != lst3.end() )
{
  cout << *it << " ";
  it++;
}
cout << endl;

list<int> lst5(3, 1);
list<int>::iterator it2 = lst5.brgin();
while(it2 != lst5.end())
{
  cout << *it << " ";
  it++;
}
cout << endl;

• list迭代器在插入元素之后==不会失效==

• 删除元素会导致迭代器失效，调用删除接口之后，需要重新更新迭代器

  • 获取erase返回值，其指向下一个元素的位置
  • 调用迭代器接口

remove：删除指定值，如果有多个，全部删除，如果没有，不做操作

splice：拼接，拼接时，被拼接的元素直接存入第一个list，第二个list中不再保留被拼接的元素

unique：去重，使用之前需要lst元素有序，先调sort，再unique，如果自定义类型需要排序，则自定义类型需要支持比较运算

list迭代器

list迭代器不是原生态指针实现的，一般通过封装节点，定义一个自定义类型，通过运算符重载函数完成迭代器规定的操作，例如：

• *iterator：operator*( )—-> _node->_val
• ++iterator：operator++( ) —-> _node = _node->_next
• iterator->：operator->( )—-> &_node->_val
• !=iterator：operator!=( )—-> _node != iterator2._node;

即list迭代器不是一个指针，而是一个对象，以下为一个模拟实现

template<class T, class Ref, class Ptr>//迭代器
class ListIterator
{
	typedef ListNode<T>* PNode;
	typedef ListIterator<T, Ref, Ptr> Self;
public:
	ListIterator(PNode pNode = nullptr)
		: _pNode(pNode)
	{ }
	ListIterator(const Self& ls)
		: _pNode(ls._pNode)
	{ }
	T& operator*()
	{
		return _pNode->_val;
	}	
	T* operator->()
	{
		return *this;
	}
	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 _pNode;
};

list与vector的差异

1. list底层结构为带头双向循环链表，vector则为顺序表
2. 由第一条，vector支持随机访问，访问某个元素效率为O(1)，而list则不支持，访问某个元素效率为O(n)
3. 在插入或删除时，vector的效率为O(n)，并且可能涉及搬移元素、增容的问题，而list插入删除不需要搬移元素或增容等，效率为O(1)
4. 由于vector低层为顺序表，所以内存上是连续空间，不容易造成内存碎片，缓存利用率低，list恰恰相反
5. vector的迭代器是原生态指针实现，而list则对原生态指针进行了封装
6. 对于vector来说，插入元素时，要给所有迭代器重新赋值，因为插入元素可能导致增容，使原来的迭代器失效，删除时，当前迭代器需要重新赋值，否则会失效；对于list来说，插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
7. 使用场景：vector适合需要高效存储，随机访问，不关心插入删除效率；list适合需要大量插入删除操作，不进行随机访问的场景

list的模拟实现

list的模拟实现)