list容器排序（deque容器和list容器）

deque:双端队列容器(队头队尾都可入,出)

底层数据结构情况

动态开辟的二维数组,一维数组从2开始,以2倍方式进行扩容,每次扩容后,原来第二维数组

从新的第一维数组的下标oldsize/2 开始存储

如下列图序

满了扩容,扩容第1维,2倍扩

deque deq;

增加:

deq.push_back(20)；从尾部添加,可能引起扩容 O(1)

deq.push_font(20); 从头部添加, O(1)

deq.insert(iterator,20);从迭代器指向的位置加入元素 O(N)

删除:

deq.pop_back();//从尾部删除元素 O(1);

deq.pop_front();//从头部删除元素O(1);

deq.erase(it);//从指向的位置删除元素O(n)

查询:

用 迭代器iterator遍历,如果涉及中间insert和erase   
    
    
    ，一定要考虑迭代器失效的问题

list：链表容器

底层数据结构:双向循环链表

list mylist;

增加:

mylist.push_back(20)；从尾部添加,可能引起扩容 O(1)

mylist.push_font(20); 从头部添加, O(1)

mylist.insert(iterator,20);从迭代器指向的位置加入元素 O(1),在insert前一般要经过查询操作


     


     


     


，查询操作是比较慢的,要一个一个比对

删除:

mylist.pop_back();//从尾部删除元素 O(1);

mylist.pop_front();//从头部删除元素O(1);

mylist.erase(it);//从指向的位置删除元素O(1); 在erase前一般要经过查询操作 




 




 




，查询操作是比较慢的,要一个一个比对