vector常用的函数

?

• begin()

• end()

• size()

• empty()

• capacity()

• front()

• back()

• push_back()

• pop_back()

• erase(iterator position)
  ?

• erase(iterator first, iterator last) //迭代器last指向的那个元素是不清除的
  ?

• insert(position,n,x)
  ?
  ?

?

• resize()
• clear()
• 提供随机存取迭代器

list容器

• STL中list是一个环状双向链表，插入和接合操作都不会造成原有的list失效。而vector的插入操作可能使原有的迭代器全部失效。 ?

如上图所示，如果让指针node指向刻意置于尾端的一个空白节点,node便能符合STL对于 前闭后开区间 的要求,成为last迭代器。

• list 提供的是双向迭代器

• begin(): 返回第一个元素的迭代器（*node)->next

• end(): 直接返回node

• size()

• empty()
  ?

• insert: 新插入节点将位于哨兵节点(标示出插入点)所指节点的前方，这是STL对“插入操作” 的标准规范。
  ?

• push_front()

• push_back()

• pop_front()

• pop_back()

• unique() ：移除数值相同的连续元素，只有 “连续而相同" 的元素，才会被移除只剩一个

• remove(const T & value): 将数值为value的所有元素移除

• erase(iterator)
  ?

• clear(): 清除所有的元素

• transfer(position, first, last): list内部提供了一个所谓的迁移操作(transfer):将某连续范围内的元素迁移到某个特点的位置之前。
  ?
  注意迁移区间是 半闭半开区间 ,这个transfer不是公开的接口，公开的接口是space

• space() : space将某连续范围的元素从一个list移到另一个(同一个)list的某个点
  ?

• merge()

• sort()

• resverse()

deque容器操作

vector是一种单向开口的连续线性空间，deque是一种双向开口的连续线性空间。双向开口是指在头尾两端分别做元素的插入和删除操作。

??
?

deque与vector的区别

• deque允许于常量时间内对头端进行元素的插入或移除操作

• deque没有容量的概念
  ?

?

?

stack

修改某物接口，形成另一种风貌的性质 称为配接器。?

?

• pop()
• push(const value_type & x)
• top(): 返回栈顶元素?- stack不提供迭代器 ?

SGI 以deque作为缺省情况下的stack底部结构

queue

?

• 入队操作称为push(const value_type & x)

• 出队操作称为pop()

• front()取队首元素

• back() 取队尾元素

?

set

标准的STL关联式容器分为set和map两大类，以及他们的衍生体multiset（多键集合）以及multimap（多键隐射表）。这些容器的底层都是以红黑树完成。RB-tree也是一个独立的容器，但并不开放给外界使用。??

STL小结