一、C++结构体

#include 
    
     using namespace std;struct Point{    int x;    int y;    Point(int x=0,int y=0):x(x),y(y){}};Point operator +(const Point &A,const Point &B){    return Point(A.x+B.x,A.y+B.y);}ostream& operator <<(ostream &out,const Point A){    out<<'('<
     
      <<','<
      
       <<')'<
      
     
    

注意

1. 在C++中定义struct类型，可以直接用，可以不再用typedef取别名
2. 对结构体编写重构函数参考实例如上
3. 结构体可以有成员函数，而且有它独有的初始化方式，
4. C++中的函数参数可以拥有默认值
5. C++结构体可以有多个构造函数
6. 以上，同样在class中适用

二、模板

#include 
    
     using namespace std;struct Point{    int x;    int y;    Point(int x=0,int y=0):x(x),y(y){}};Point operator +(const Point &A,const Point &B){    return Point(A.x+B.x,A.y+B.y);}ostream& operator <<(ostream &out,const Point A){    out<<'('<
     
      <<','<
      
       <<')'<
       
        T sum(T *p,T *q){    T result=0;//initiate 0*****    while(p!=q){        result=result+*p;        p++;    }    return result;}int main(){    Point points[4]={Point(0,0),Point(1,1),Point(2,2),Point(3,3)};    cout<
        
         <
        
       
      
     
    

三、STL

3.1 排序与检索

例题1

现有N个大理石，每个大理石上写了一个非负整数、首先把各数从小到大排序；然后回答Q个问题。每个问题问是否有一个大理石写着某个整数x，如果是，还要回答哪个大理石上写着x。排序后的大理石从左到右编号为1~N。

(在样例中，为了节约篇幅，所有大理石的数合并到一行，所有问题也合并到一行。)

样例输入：

4 1

2 3 5 1

5

5 2

1 3 3 3 1

2 3

样例输出：

CASE# 1：

5 found at 4

CASE# 2：

2 not found

3 found at 3

#define LOCAL#include
    
     #include
     
      using namespace std;const int MAX=100;int main(){    #ifdef LOCAL    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);    #endif // LOCAL    int n,q;    int object;    int time=0;    int array[MAX];    while(scanf("%d%d",&n,&q)==2 && n){        printf("CASE# %d:\n",++time);        //input n numbers        int i=n;        while(i--)scanf("%d",&array[i]);        sort(array,array+n);//use sort c++ gives        while(q--){            scanf("%d",&object);            //find            int p=lower_bound(array,array+n,object)-array;//to find the index of the object in array            if(array[p] == object) printf("%d found at %d\n",object,p+1);            else printf("%d not found\n",object);        }    }    return 0;}
     
    

以上注意：

1. 重定向操作，在本地可以这么做，放到oj上要改变写法，所以用ifdef的预定义方式。
2. sort是一个模板函数，可以接收任何有<运算的类型
3. 可以对普通数组array进行排序，也可以对vector进行排序，vector的排序方式为sort(v.begin(),v.end());
4. lower_bound()函数接受三个参数，一二两个是数组的起始位置，第三个是待查找的元素，表示在数组中寻找第一次大于或者等于待查元素的位置。
5. scanf()的返回值：正确输入的变量个数，注意正确包括类型正确，个数正确。

3.2 vector

3.3 set

例题

输入一个文本，找出所有不同的单词，按字典序从小到大进行输出，单词不区分大小写。

样例输入：

Adventures in Disneyland

Two blondes were going to Disneyland when they came to a fork in the

road. the sign read:"Disneyland Left."

So they went home.

样例输出：

a

adventures

blondes

came

disneyland

fork

going

home

in

left

read

road

sign

so

the

they

to

two

went

were

when

#define LOCAL#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;set
        
          dict;int main(){    #ifdef LOCAL    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);    #endif    string line,x;    while(cin>>line){        //1.to lower case        for(int i=0;i
         
          >x) dict.insert(x); } for(set
          
           ::iterator it=dict.begin();it!=dict.end();++it){ cout<<*it<<'\n'; } return 0;}
          
         
        
       
      
     
    

代码中用到了一些自带的函数如isapha()、tolower()等，具体使用参见

注意：

1. 要对输入样例进行处理，非字母要变成空格，大写字母变成小写字母。
2. 在将string进行插入到set的时候就已经按照字典序插入的了，因为string类型的<定义，就是定义为字典序的。

四、总结

vector、set和map的速度都很快，其中vector的速度接近数组，而set和map的速度也远远超过“用一个vector保存所有，然后逐个查找”的速度，set和map每次插入，查找和删除时间和元素个数的对数呈线性关系。但有些对时间要求很高的题目中，STL可能成为性能瓶颈。