第五节 常用C++容器vector，set和map

  上一节我们介绍了一些简单的数据结构，大家只要理解概念就可以了，为下面的概念和模型打下基础。这一节，我们讲一讲C++中一些常用的容器。就像之前的list，stack一样，能给我们写程序带来很大的帮助。

vector

  动态数组（vector）是比较常用的容器之一，它的用法和数组类似，但是大小不确定。在我们对它的值进行更改的时候，它的大小也会变化。它的声明方法和数组类似：

1
vector<int> v;

  push_back()可以在结尾添加元素：

1
2
3
v.push_back(1);
v.push_back(2);
v.push_back(3);

  vector可以和数组一样通过下标来访问。下标也是从0开始的：

1
print("%d %d %d\n",v[0],v[1],v[2]);

  v.begin()和v.end()返回的是两个指针，分别指向vector的第一个元素和最后一个元素。

  和我们之前讲过的list一样，vector也可以使用迭代器：

1
2
3
4
vector<int> v;
    vector<int>::iterator it;
    for(it=v.begin();it!=v.end();it++)
        printf("%d ",*it);

  我们来做一道练习题吧，hdu2561，思路很简单，我们用vector来存放数据，sort()排序之后输出。在输出完一组数据之后，我们应该使用clear()来清空容器。AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int c,n,t;
    vector<int> v;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d",&t);
            v.push_back(t);
        }
        sort(v.begin(),v.end());
        printf("%d\n",v[1]);
        v.clear();
    }
    return 0;
}

  除此之外，还有一些常用的函数：

front() back() 返回首尾元素的引用。
empty() 是否为空
size() 元素的个数
pop_back() 删除容器中最后一个元素
clear() 删除所有元素
erase(iterator it) 删除迭代器指向的的元素

set

  set被称为集合类，存放的元素会按照大小自动排序，但是不能有重复的元素。如果想要存放重复的元素，应该使用multiset。

  声明、初始化和迭代器等：

1
2
3
4
5
6
7
8
set<int> set01;
    set<int>::iterator it;
    set01.insert(3);
    set01.insert(1);
    set01.insert(1);
    for(it01=set.begin();it!=set.end();it++)
        printf("%d ",*it);
    return 0;

  正如它的名字，在处理集合之类的问题的时候我们可以使用。可以看这道题：hdu1412。同一个set存储连个数据，不仅实现了相同元素的排除还排好了序。在输出一组结果之后，应该使用clear()来清空容器。下面是AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <set>
using namespace std;

int main()
{
    int i,n,m,t;
    set<int> st;
    set<int>::iterator it;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<n+m;i++)
        {
            scanf("%d",&t);
            st.insert(t);
        }
        for(it=st.begin();it!=st.end();)
        {
            printf("%d",*it);
            printf("%c",(++it)==st.end()?'\n':' ');
        }
        st.clear();
    }
    return 0;
}

empty() 是否为空
size() 元素的个数
erase(iterator it) 删除迭代器指向的的元素

map

  map称为映射，元素成对出现。<Key,Value>，前面的称为关键字，后面是关键字对应的值。映射中的元素会按照key的大小自动排序。map是单映射，key和value是一对一的关系。如果想要实现多映射就要使用multimap。

  声明、初始化

1
2
3
4
5
6
7
map<int,string> map01;
    pair<int,string>p1(1,"这是1");
    pair<int,string>p2(2,"这是2");
    pair<int,string>p3(3,"这是3");
    map01.insert(p1);
    map01.insert(p2);
    map01.insert(p3);

  除此之外，我们还可以使用赋值的方法来进行初始化，但是仅限于单映射。

1
2
3
map01[5]=25;
map01[3]=9;
map01[4]=16;

  begin()和end()返回的是两个指针，分别指向map的第一个元素和最后一个元素。如果需要访问映射中的元素，需要使用迭代器：

1
2
3
4
5
6
7
map<int,int> map01;
    map<int,int>::iterator it01;
    map01[5]=25;
    map01[3]=9;
    map01[3]=10;
    for(it01=map01.begin();it01!=map01.end();it01++)
        printf("Key:%d Value:%d\n",(*it01).first(*it01).second);

  下面做一道练习题：(hdu2550)[http://acm.hdu.edu.cn/showproblem.php?pid=2550]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <map>
using namespace std;

int main()
{
    map<int,int> mp;
    map<int,int>::iterator it;
    int t,n,key,value,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d%d",&key,&value);
            mp[key]=value;
        }
        for(it=mp.begin();it!=mp.end();it++)
        {
            for(i=0;i<(*it).second;i++)
            {
                printf(">+");
                for(j=0;j<(*it).first-2;j++)
                    printf("-");
                printf("+>\n");
            }
            printf("\n");
        }
        mp.clear();
    }
    return 0;
}