STL在ACM中的应用

STL 提供三种类型的组件：容器、迭代器和算法，它们都支持泛型程序设计标准。在ACM中充分利用STL可以大大的简化程序，提高解题效率。

1、容器主要有两类：顺序容器和关联容器。顺序容器（vector/list/deque/string）等是一系列元素的有序集合。关联容器（set/multiset/map/multimap）包含查找元素的键值。

2、迭代器的作用是遍历容器。

3、STL算法库包含四类算法：排序算法，不可变算法，变序算法和数值算法。

 

常用的容器：

1、vector

Vector的内存管理是这样的，在分配小于等于128个字节的内存的时候，采用内存池的方式，否则也是直接每次都调用C的malloc函数。

vector<int> v;

v.push_back(data);

       for(vector<int>::iterator it = v.begin();it!=v.end();it++)    {     cout<<*it<<" ";    }

accumulate(v.begin(),v.end(),0); //从begin加到end，再加0

也可以用定义数组的方式：

vector<int> v(3);

v[0]=3;

v[1]=4;

v[2]=8;

cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl;

 

 

vector v 定义之后，下面可以用v[i]来访问

 

vector的插入：vec.insert(vec.begin()+i,20);

 

vector的删除：vec.erase(v.begin+i); //删除第i+1个元素

vec.erase(v.begin,v.begin()+3);//删除第一到第四个元素

vec.clear(); //全部清除

 

vector的反转：#include<algorithm> reverse(v.begin(),v.end());

其实数组也可以用这个函数来反转

 

vec.size()  

vec.empty()-->bool

用sort来排序，引入algorithm头文件

sort(v.begin(),v.end()); //默认的是升序排列

也可以自定义比较函数

bool Comp(const int &a, const int &b)

{

if(a!=b) return a>b; //这是为了在相信

else return a>b;

}

然后调用：sort(v.begin(),v.end(),Comp);

2、string

string str = "lingyibin";

 

 

string::iterator it=str.begin();

然后再for，和vector一样。

 

str.replace(3,1,"g"); //3是从0开始算的

 

str.compare("ling"); //str大，则返回1，等则0，小则-1

 

str用printf输出:printf(str.c_str());

 

str.find('d');   //返回找到的位置，找不到时返回-1

str.find("yi");

当然string也可以通过str[i]这种格式来访问，得到的结果是一个char

把char[]数组赋值给string的可以，但反过来就不行了。

3、set

set集合是一个实现了红黑树的平衡二叉检索树。

里面的元素不会重复，而且是有序。

如：

    set<int> s;

    s.insert(34);

    s.insert(3);

    s.insert(27);

    s.insert(31);

    s.insert(3);

    for(set<int>::iterator it = s.begin(); it != s.end(); it ++)

    {

        cout<<*it<<endl;

    }

结果是：

3

27

31

34

反向遍历set:

set<int>::reverse_iterator rit;

for(rit = s.rbegin();rit!=s.rend();rit++) cout<<*rit<<endl;

it = s.find(21);

if(it!=s.end()) //找到

cout<<"找到了"<<endl;

else cout<<"没找到"<<endl;

//set的自定义比较函数

struct myCmp

{

bool operator()(const int &a,const int &b)

{

return a>b;

}

};

set<int,myCmp> mySet;

//如果set里面是一个结构体的话，直接把比较函数写到结构体里面

struct Info

{

string name;

double score;

bool operator < (const Info &a) const

{

return a.score < score;

}

}

4、map 和set一样，也是红黑树结构，不允许重复，用法和set差不多

map<int,string> m;

for(it = m.begin(); it != m.end(); it++)

{

cout<<(*it).first<<" : "<<(*it).second<<endl;

}

map的查找：

map<int,char>::iterator it;

it = m.find(28);

if(it!=m.end()) ……//说明找到了

5、双向队列：deque（头进尾出）

d.push_back(2);//从后端推入

d.push_front(3);//从后端推入，并覆盖已有元素

d.insert(d.begin()+2,89);//中间插入，会覆盖原来的元素

d.pop_back();//从尾部删除

d.pop_front();//从头部删除

6、list

list<int> l;

#include<algorithm>

list<int>::iterator it;

it = find(l.begin(),l.end(),5);

l.sort();//链表的排序

7、bitset

#include<bitset>

bitset<10> b;

b[1]=1;

b[6]=1;

b[9]=1;

b.set();//置位-->1111111111

b.reset();//置0

8、stack

stack的几个常用方法

s.push(33);

s.top();

s.pop();

s.size();

s.empty();//0或1

9、queue

queue的几个常用方法

q.push(33);

q.pop();

q.front;

q.back();

q.empty();

q.size();

10、priority_queue

priority_queue//大的先出队

重载<来改变出队顺序

struct Info

{

string name;

double score;

bool operator < (const Info &a) const

{

return a.score < score;

}

}

priority_queue其它操作和stack一样

……其它的就不一一列出了，有兴趣可以自己google吧！^_^