管理元素集合的STL容器大致分为两类。一类是有顺序的集合,称为序列式容器;另一类是经过排序的集合,称为关联式容器。

序列式容器会将新添加的元素置于特定为位置,这个位置由插入的时间和地点决定,与元素本身的值无关。前面介绍过的vector和list就是很有代表性的序列式容器。

相对地,关联式容器会依据特定的排序标准来决定要添加的元素的位置。STL为用户提供了set、map、multiset、multimap容器。

关联式容器会在管理数据的过程中,自动给元素排序。虽然序列式容器也能进行排序,但是关联式容器的优势在于,开源随时采用二分搜索法,搜索元素的效率极高。

map是以键与值的组合为元素的集合。每个元素拥有一个键和一个值,集合以键作为排序标准。这里的map和python中的dict类似,各元素的键唯一,不存在重复。map可以看作是一种能使用任意类型元素作为下标的关联式容器。

map的用法:

函数名功能复杂度
size()返回map中的元素数O(1)
clear()清空mapO(1)
begin()返回指向map开头的迭代器O(1)
end()返回指向map末尾的迭代器O(1)
insert((key, value))向map中插入元素(key, value)O(logn)
erase(key)删除键值为key的元素O(logn)
find(key)搜索与key一致的元素,并且返回指向该元素的迭代器。
若没有与key键值一致的元素,则返回end()
O(logn)

map与set一样,也是通过平衡二叉树来实现的。因此元素的插入、删除、搜索的复杂度都是O(logn)

下面的一串代码演示了map的几种基本用法

#include<iostream>
#include<map>
#include<string>
using namespace std;

void print(map<string, int> T)
{
    map<string, int>::iterator it;
    cout<<T.size()<<endl;
    for(it = T.begin(); it!=T.end();it++)
    {
        pair<string, int> item = *it;
        cout<<item.first<<" --> "<<item.second<<endl;

    }
}

int main()
{
    map<string, int>T;
    T["red"] = 32;
    T["blue"] = 688;
    T["yellow"] = 122;

    T["blue"] += 312;

    print(T);

    T.insert(make_pair("zebra", 101010));
    T.insert(make_pair("white", 0));
    T.erase("yellow");

    print(T);

    pair<string, int> target = *T.find("red");
    cout<<target.first<<" --> "<<target.second<<endl;

}

在上面这串代码里面,pair是STL提供的结构体模板,其第一个元素可以用first访问,第二个元素可以用second访问。

map<string, int> T 是一个声明,用于生成关联数组,该关联数组管理以string为键的int元素。

map容器可以像数组一样,用”[ ]”来进行访问,并进行读写操作。当然也可以用迭代器来顺次访问每一对键和值。

利用map,我们可以更方便地实现

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_C

这个题目。当初我们是用散列法来完成这个题目的,现在我们用map来做的话,只需要这样做:

#include<iostream>
#include<map>
#include<string>
using namespace std;


int main()
{
    int n;
    cin>>n;
    map<string, bool> m;
    string cmd,ipt;
    for(int i=0;i<n;i++)
    {
        cin>>cmd;
        if(cmd[0]=='i')
        {
            cin>>ipt;
            m[ipt] = true;
        }
        else
        {
            cin>>ipt;
            if(m[ipt])
                cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }
    }
}

这里就是把key设成字符串,然后值设为一个bool变量。由于bool默认是false的,所以,就可以很方便地实现一个字典的查找功能。

你也可能喜欢

发表评论