一、基本概念

容器：可容纳各种数据类型的通用数据结构，是类模板

迭代器：可用于依次存取容器中的元素，类似与指针

算法：用于操作容器中的元素的函数模板

• sort()  对一个vector中的数据进行排序
• find()  搜索一个list中的对象

例 int array[100];

sort(array,array+70); 对前70个元素排序

 

二、容器

容器类型

• 顺序容器

vector,  deque,  list

动态数组，双向队列，双向链表

• 关联容器

通常以平衡二叉树方式实现，插入和检索时间都是O(log(N))

set,  multiset,  map,  multimap

multiset允许相同元素存在

map有点像python中的dictionary，multimap允许key值相同的元素存在

• 容器适配器

stack,  queue,  priority_queue

栈， 单向队列，优先级队列

stack后进先出，queue先进先出，priority_queue优先级最高的元素第一个出列

顺序容器和关联容器中都有的成员函数

begin          返回第一个元素的迭代器

end             返回最后一个元素后面的迭代器    访问会出错

rbegin        返回最后一个元素的迭代器

rend           返回第一个元素前面的迭代器

erase        从容器中删除一个或几个元素

clear          从容器中删除所有元素

顺序容器常用成员函数

front               返回容器中第一个元素的引用

back              返回容器中最后一个元素的引用

push_back   在容器末尾增加新元素

pop_back     删除容器末尾的元素

erase            删除迭代器指向的元素，返回删除元素后面的那个元素的迭代器

 

三、迭代器

• 用法和指针类似
• 有const和非const两种

定义方法

容器类名::iterator   变量名;

或

容器类名::const_iterator  变量名;

访问一个迭代器指向的元素：

* 迭代器变量名

迭代器使用示例：

#include <vector>
#include <iostream>
using namespace std;

int main(){
    vecotr<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::const_iterator i;  
    //const_iterator不能通过访问修改
    //iterator  可以通过*i来修改容器内的元素
    //reverse_iterator  反向迭代器
    for(i=v.begin();i!=v.end();++i)
        cout<<*i<<",";
    cout<<endl;
}
输出结果：
1,2,3,4，

迭代器类型

分为双向和随机访问

vector   随机访问

deque   随机访问

list         双向

set        双向

map      双向

stack、queue、priority_queue  不支持迭代器

双向迭代器没什么特殊，但随机访问迭代器很骚：

遍历vector的迭代器的几种做法（deque类似）

vector<int> v(100);
int i;
for(i=0;i<v.size();i++)
    cout<<v[i];

vector<int>::const_iterator ii;
for(ii=v.begin();ii!=v.end();ii++)
//用小于号比较也行  <   因为是vector的迭代器是随机访问类型
    cout<< *ii;

遍历list的方法

list<int> v;
list<int>::const_iterator ii;
for(ii=v.begin();ii!=v.end();ii++)
//      这里不能用  <   因为是list的迭代器是双向类型，不支持比较
    cout<< *ii;

而且list没有[]成员函数，所以不能通过v[i]来访问

四、算法

大多数在<algorithm>中定义，STL提供查找、排序等。

find(v.begin(),v.end(),3); //左闭右开区间查找

binary_search 二分查找

sort

……

等等