C++ Primer读书笔记–第十章

关联容器通过key-value存储和读取元素。

map:key-value
set:只包含key

map和set的都保证key是唯一的,不允许为同一个key添加第二个元素,如果要多个key,可以使用mutimap或者mutiset。

10.1  pair类型

pair主要是为map中的“key-value”这种元素而设计的元素类型,定义于<utility>中。

pair<T1,T2> p1;  空的key-value
pair<T1,T2> pi(first,second); 初始化key value
make_pair(v1,v2);  直接根据key value造pair元素
最后面这个非常常用

可以直接访问pair对象的两个成员:first和second

10.2  关联容器

关联容器不能通过指定容器大小来指定,不能使用assign直接指定,不能使用resize。
关联容器一定按照key的次序排序。

10.3  map类型

map是key-value对的集合,可以理解为关联数组。

定义

map<string,int> work_count;
map<k,v> m;
map<k,v> m(m2);
map<k,v> m(b,e);

排序比较

默认情况下,map按照key类型的 '<' 号进行严格弱排序,也可以指定比较函数。

map<const char*, int, ltstr> months;

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

map内置类型

map<K,V>::key_type      做索引key的类型
map<K,V>::mapped_type   做值value的类型
map<K,V>::value_type    pair类型

最后这个经常容易搞错。
map的iterator,就是一个指向pair<K,V>的“指针”

给map添加元素

有3种办法给map添加元素
假设map<string,int> m;
(1)map["test"] = 1;
这个会导致一个问题,如果"test"这个key不存在,那么将test-1被插入map中!
(2)map.insert()
最基本的版本是insert(e) , e是一个value_type类型即pair类型
其中,生成pair的方法可以有2种
insert(map<string,int>::value_type("test",1));
insert(make_pair("test",1));

insert函数返回一个pair,first是map的迭代器类型指向被插入的位置,second是bool类型的,表示是否插入了map(如果key已经存在则为false)

查找map中的元素

有三种办法:下标,find,count

(1)下标
map<string,int> m;
int cnt = m["key1"]
副作用是,如果key1不存在于m将插入key1-0

(2)find
map<string,int>::iterator itr =  m.find("key1");
if(itr==m.end())
{
   //Not found
}
else
{
   int cnt = itr->second;
}

(3)count 返回key出现的次数
int cnt =  m.count("key1");

删除map中的元素

m.erase(k)  删除key为k的元素
m.erase(p)  同上,不过p是迭代器指向k
m.erase(b,e)  按照迭代器范围删除

map对象遍历

使用begin和end运算,生成map的迭代器范围。

map<string,int>::iterator itr = map.begin();

while(itr!=map.end())
{
  //itr->first is key itr->second is value
}

10.4  set类型

set是纯key的集合,如果要检查某个元素是否在一个集合中,类似这种逻辑操作,set很合适。

set的使用基本与map相同。

但是,有如下主要不同点
(1)set只能通过find和count进行获取元素,不能通过下标操作。
(2)map的itrator就是set<T>中的T本身的指针

10.5 multimap和multiset

multiset和multimap允许一个键对应多个实例(key到value上的多对多映射)。

multiset和multimap同样不支持下标[]运算。

元素添加和删除

每次调用insert总会添加一个元素,而不像map(map中insert的时候,如果已经有key则不插入)
autors.insert(make_pair("I",1));

而erase函数将删除该key的所有key-value

查找元素

最重要的规则:multimap中,同样的key所关联的元素一定会相邻存放

multimap和multiset中查找之所以会麻烦,主要是解决一个key如果返回多个key-value的问题。一般有两种方案,强烈推荐第二个

(1)利用iterator和count查找
multimap<string,string>::iterator itr = authors.find(name);
sz_type cnt = authors.count(name);
//根据count设置边界条件
for(sz_type i=0;i<cnt;i++)
{
  cout<<itr->second<<endl;
  itr++;
}

(2)利用lower_bound(key)和upper_bound(key)

这两个函数返回key为键的上届和下届,遍历这个上届到下届之间的迭代器,就完成了find过程。
multimap<string,string>::iterator begin = authors.lower_bound(key),
                                  end = authors.upper_bound(key);

while(beg!=end)
{
   count<<beg->second<<endl;
   beg++;
}

另外,也可以使用equal_range返回pair<上届,下届>,和这个方法是类似。

Leave a Reply

Your email address will not be published.