c++ list详解

list

• 1. list的介绍
• 2. list常见重要的接口
• • 2.1 构造函数
  • 2.2 iterator
  • • 2.2.1 理解
    • 2.2.2 使用
    • 3. 容量和大小
    • 4. 查找元素
    • 5. 增、删、改
    • 3. 迭代器失效
    • 4. vector和list对比

      1. list的介绍

      list的底层结构是带头双向循环链表，因为该结构的特性，使list可以在常数范围内在任意位置进行插入和删除，但是不支持[]随机访问。

      2. list常见重要的接口

      2.1 构造函数

      默认构造	list()
      构造n个val	list（n,val_type = val_type()）
      拷贝构造	list（const list& l）
      迭代区间构造	list （InputIterator first,InputIterator last）

      代码演示

      int main(){//n个vallist li(5, 1);//拷贝构造list li1(li);//迭代器区间构造list li2(li.begin(), li.end());return 0;}

      2.2 iterator

      2.2.1 理解

      vector的iterator可以简单的理解成指针，事实上底层也是对指针typedef了，但是list的iterator不是这样，因为vector的空间是连续的，对iterator进行++或者–的操作是很自然的指向下一个或上一个元素，但是对于list的空间不是连续的，对list的iterator进行++或–是拿不到相应的元素，所以我们肯定要对++、–等操作符进行重载，但是对于内置类型，进行不了重载的操作，所以底层对该iterator进行了一层封装，变成了一个自定义的类，然后进行运算符重载，就可以得到理想的结果。

      //迭代器类templateclass ListIterator{typedef ListNode* PNode;typedef ListIterator Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_data;}Ptr operator->(){return &_pNode->_data;}Self& operator++(){_pNode = _pNode->_next;return *this;}Self operator++(int){Self tmp(*this);_pNode = _pNode->_next;return tmp;}Self& operator--(){_pNode = _pNode->_pre;return *this;}Self& operator--(int){Self tmp(*this);_pNode = _pNode->_pre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode}private:PNode _pNode;};

      2.2.2 使用

      begin()	返回第一个元素的迭代器
      end()	返回最后一个元素的下一个元素的迭代器
      rebegin()	返回end位置的反向迭代器
      rend（）	返回begin位置

      代码演示

      int main(){//n个vallist li(5, 1);list::iterator it = li.begin();while (it != li.end()){cout //n个vallist//n个vallistlistint array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值l.erase(it);++it;}}