STL

vector

vector属于std命名域的,因此需要通过命名限定,如下完成你的代码:

using std::vector;

vector vInts;

或者连在一起,使用全名:

std::vector vInts;

建议使用全局的命名域方式:using namespace std;

函数

c.assign(beg,end)c.assign(n,elem)

   将[beg; end)区间中的数据赋值给c。将n个elem的拷贝赋值给c。

c.at(idx)

   传回索引idx所指的数据,如果idx越界,抛出out_of_range。

c.back()

   传回最后一个数据,不检查这个数据是否存在。

c.begin()

   传回迭代器中的第一个数据地址。

c.clear()

   移除容器中所有数据。

c.empty()

   判断容器是否为空。

c.end()

   指向迭代器中末端元素的下一个,指向一个不存在元素。

c.erase(pos)

c.erase(beg,end)

   删除pos位置的数据,传回下一个数据的位置。

删除[beg,end)区间的数据,传回下一个数据的位置。

c.front()

   传回第一个数据。

get_allocator

使用构造函数返回一个拷贝。

c.insert(pos,elem)

c.insert(pos,n,elem)

c.insert(pos,beg,end)

   在pos位置插入一个elem拷贝,传回新数据位置。在pos位置插入n个elem数据。无返回值。在pos位置插入在[beg,end)区间的数据。无返回值。

c.max_size()

   返回容器中最大数据的数量。

c.pop_back()

   删除最后一个数据。

c.push_back(elem)

   在尾部加入一个数据。

c.rbegin()

   传回一个逆向队列的第一个数据。

c.rend()

   传回一个逆向队列的最后一个数据的下一个位置。

c.resize(num)

   重新指定队列的长度。

c.reserve()

   保留适当的容量。

c.size()

   返回容器中实际数据的个数。

c1.swap(c2)

swap(c1,c2)

将c1和c2元素互换。同上操作。

set

实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,把元素放到适当的位置,以保证每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值;另外,还得保证根节点左子树的高度与右子树高度相等。

平衡二叉检索树使用中序遍历算法,检索效率高于vector、deque和list等容器,另外使用中序遍历可将键值按照从小到大遍历出来。

构造set集合主要目的是为了快速检索,不可直接去修改键值。

函数

begin() 返回指向第一个元素的迭代器

clear() 清除所有元素

count() 返回某个值元素的个数

empty() 如果集合为空,返回true

end() 返回指向最后一个元素的迭代器

equal_range() 返回集合中与给定值相等的上下限的两个迭代器

erase() 删除集合中的元素

find() 返回一个指向被查找到元素的迭代器

get_allocator() 返回集合的分配器

insert() 在集合中插入元素

lower_bound() 返回指向大于(或等于)某值的第一个元素的迭代器

key_comp() 返回一个用于元素间值比较的函数

max_size() 返回集合能容纳的元素的最大限值

rbegin() 返回指向集合中最后一个元素的反向迭代器

rend() 返回指向集合中第一个元素的反向迭代器

size() 集合中元素的数目

swap() 交换两个集合变量

upper_bound() 返回大于某个值元素的迭代器

value_comp() 返回一个用于比较元素间的值的函数

常用操作

1.元素插入:insert()

2.中序遍历:类似vector遍历(用迭代器)

3.反向遍历:利用反向迭代器reverse_iterator。

   例:

 

4.元素删除:与插入一样,可以高效的删除,并自动调整使红黑树平衡。

 

5.元素检索:find(),若找到,返回该键值迭代器的位置,否则,返回最后一个元素后面一个位置。

 

6.自定义比较函数

   (1)元素不是结构体:

       例:

 

   (2)如果元素是结构体,可以直接将比较函数写在结构体内。

       例:

 

具体用法

定义

 

添加元素

 

获取元素

 

map

map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小,除了那个操作节点,对其他的节点都没有什么影响。对于迭代器来说,可以修改实值,而不能修改key。

(妈的这个东西看了一下午才有点明白了吧貌似……效率有点低啊,而且网上也找不到什么好一点的解释啊貌似……)

基本操作函数

     C++ Maps是一种关联式容器,包含“关键字/值”对

     begin()          返回指向map头部的迭代器

     clear()         删除所有元素

     count()          返回指定元素出现的次数

     empty()          如果map为空则返回true

     end()            返回指向map末尾的迭代器

     equal_range()    返回特殊条目的迭代器对

     erase()          删除一个元素

     find()           查找一个元素

     get_allocator()  返回map的配置器

     insert()         插入元素

     key_comp()       返回比较元素key的函数

     lower_bound()    返回键值>=给定元素的第一个位置

     max_size()       返回可以容纳的最大元素个数

     rbegin()         返回一个指向map尾部的逆向迭代器

     rend()           返回一个指向map头部的逆向迭代器

     size()           返回map中元素的个数

     swap()            交换两个map

     upper_bound()     返回键值>给定元素的第一个位置

     value_comp()      返回比较元素value的函数

操作符的重载如Set。

stacks

C++ Stack(堆栈) 是一个容器类的改编,为程序员提供了堆栈的全部功能,——也就是说实现了一个先进后出(FILO)的数据结构。

stack模板类的定义在头文件中。

stack模板类需要两个模板参数,一个是元素类型,一个容器类型,但只有元素类型是必要的,在不指定容器类型时,默认的容器类型为deque。

操作

语法:   ==

<=

>=

<<o:p> 

!=

所有的这些操作可以被用于堆栈. 相等指堆栈有相同的元素并有着相同的顺序。

empty

语法:   bool empty();

如当前堆栈为空,empty() 函数返回 true 否则返回false.

pop

语法:   void pop();

pop() 函数移除堆栈中最顶层元素。

push

Syntax:   void push( const TYPE &val );

push() 函数将 val 值压栈,使其成为栈顶的第一个元素。如:

size

语法:   size_type size();

size() 函数返当前堆栈中的元素数目。如:

 

top

语法:    TYPE &top();

top() 函数返回对栈顶元素的引用. 举例,如下代码显现和清空一个堆栈。

 

queue

queue模板类的定义在头文件中。

与stack模板类很相似,queue模板类也需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque类型。

基本操作

入队:q.push(x)        将x接到队列的末端。

出队:q.pop()            弹出队列的第一个元素,注意,并不会返回被弹出元素的值。

访问队首元素:q.front() 即最早被压入队列的元素。

访问队尾元素:q.back() 即最后被压入队列的元素。

判断队列空:q.empty()         当队列空时,返回true。

访问队列中的元素个数:q.size()

priority_queue

Priority Queue中的元素根据优先级被读取,它的接口和queue非常相近但是其top()/pop()的对象并非第一个置入的元素,而是优先级最高的元素。换句话说,Priority Queue内的元素已经跟去其值和排序准则进行了排序。

排序准则有template参数确定,缺省是operator<<o:p>

缺省内部实现容器为vector

那么top()/pop()的对象就是元素值最大的元素。如果同时存在多个元素,则不确定哪一个会被选择(类似于不稳定排序)!

声明

(这部分来自http://blog.csdn.net/sup_heaven/article/details/8036982

他的模板声明带有三个参数,priority_queue

Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。

Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list。

如果把后面俩个参数 缺省的话,优先队列就是大顶堆,队头元素最大。

 

如果要用到小顶堆,则一般要把模板的三个参数都带进去。

STL里面定义了一个仿函数 greater<>,对于基本类型可以用这个仿函数声明小顶堆。

 

对于自定义类型,则必须自己重载 operator< 或者自己写仿函数先看看例子:

 

自定义类型重载 operator< 后,声明对象时就可以只带一个模板参数。

此时不能像基本类型这样声明priority_queue, greater >;

原因是 greater 没有定义,如果想用这种方法定义

则可以按如下方式

例子:(个人喜欢这种方法,因为set的自定义比较函数也可以写成这种形式)

 

基本操作

c.top()           返回队列头部数据

c.push(elem)       在队列尾部增加elem数据

c.pop()          队列头部数据出队

c.empty()      判断队列是否为空

c.size()          返回队列中数据的个数

另外推荐一个网上其他的STL,里面有一点list和deque的介绍,可以了解一下。