毕节市网站建设_网站建设公司_jQuery_seo优化

1.list的使用方法（list 本质上是一个双链表 ）

list的迭代器类型是双向迭代器（支持++，--）

1）构造函数（）

默认构造函数

explicit list (const allocator_type& alloc = allocator_type());

这个构造就是构造出哨兵位（头节点） allocator_type() 这个是对于不同类型的0值，对于char就是‘0’

template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

list (const list& x);

range 构造函数的InputIterator是 C++ 标准中的输入迭代器（及兼容它的更高阶迭代器：前向、双向、随机访问迭代器），并非任意迭代器，输出迭代器不支持该构造

2）list的push

有push_back和push_front 这两个 对于双量表而言，时间复杂度都是O(1) 。

还有一种emplace_back 在某种情况下是比push_back 而言是高效一点的。这种特殊情况就是对要插入的元素没有操作时他就可以减少拷贝直接构造

3）迭代器访问

begin() end()

这里begin() 返回的是头节点的后面一个iterator（即第一个有效元素） end() 返回的是头节点iteraotr（最后一位有效元素的下一位）

4)任意位置的增加和删除 insert erase

iteraotr insert(iterator pos,T& val)

返回值仍是指向着新的元素，

iterator erase（iterator pos)

iterator erase（iterator first,iterator last)

这里的返回值是指向着擦除元素最后一位的下一位，对于第一个pos就是指向pos的下一位，这些和vector都是差不多的，同样需要防止迭代器失效！！！

这里的插入时前闭后开

5）splice

这个可以理解成 CTRL + C ,delete,到指向的位置CTRL+V,意思是将一段list拼接到另一个list的 pos 后面但是第一个list会被销毁。

来具体解析一下第三个，iterator position 代表的是我要插入到 list1 的哪个位置前，list&x代表的是我要把哪个list插入，iterator first，iterator last 指的是插入区间，同样是前闭后开；

6）merge 中文译为整合

他这个是针对于有序list之间的整合，比如有两个递增的list我想构造出一个递增的新list

来细讲一下2 这个就是list的引用，comp是排序规则，必须和list的排序规则相同！！！

7)sort

重点：标准库中有一个 sort ，list 中有一个sort，那为什么要设计这么多个sort，不能统一吗

可以明确的看出标准库的sort是只是用随机迭代器的，而list在开篇就讲过了这是双向迭代器，所以list要单独设计，问题就出现在这里，按照道理来说标准库应该是没有这个专门的为双向设计的迭代器效率高的，大数据量下，标准库的std::sort（用于vector等支持随机访问迭代器的容器）效率是std::list::sort的两倍以上（明确两个sort的区别，避免笔误混淆）。

所以我们要排序可以直接用构造函数，用list构造出一个vector，在进行排序，效率都比直接用list的库sort效率高很多！！！可以进行测试时间（用release模式，毕竟最后看的是这个模式的效率如何）。

2.底层代码

底层代码值得一聊的就是对iterator的封装，我们用一个类对list_node* 进行封装，这个行为使得我们可以进行运算符重载，从而实现 * ++ != == 这样的东西，也可使先const_iterator 和iterator,毫无疑问这个是list_node* 直接无法实现的东西，这个完美体现了封装的魅力。