PS,1880后程序员

看不完的牙,写不完的程序,跑不完的步。
随笔 - 97, 文章 - 34, 评论 - 10, 引用 - 0
数据加载中……

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

 

关联容器 Associative Containers

 

关联容器包括:

l  map

l  set

l  multimap

l  multiset

 

10.1 初步知识:pair类型

创建和初始化pairs

Examples:

pair<string, string> anon;       // holds two strings

pair<string, int> word_count;    // holds a string and an int

pair<string, vector<int> > line; // holds string and vector<int>

使用typedef简化定义:

typedef pair<string, string> Author;

Author proust("Marcel", "Proust");

Author joyce("James", "Joyce");

pair操作

可以直接访问pair的数据成员。这些数据成员都是public。(the pair class gives us direct access to its data members: Its members are public.

string firstBook;

// access and test the data members of the pair

if (author.first == "James" && author.second == "Joyce")

    firstBook = "Stephen Hero";

 

10.2 关联容器

关联容器共享了很多顺序容器的操作。但是关联容器还定义了自己特有的操作。

关联容器的元素是按key进行排序的。当我们迭代访问一个关联容器时,保证是按照key的顺序来访问,而不是按照元素在容器中的顺序来访问的。When we iterate across an associative container, we are guaranteed that the elements are accessed in key order, irrespective of the order in which the elements were placed in the container.

 

10.3 map

定义map

map<k, v> m;

创建一个名字是m的空的map

map<k, v> m(m2);

创建一个名字是mmapmm2的拷贝。mm2必须具有相同的keyvalue类型。

map<k, v> m(b, e);

创建一个名字是mmap,它是迭代器be指定的元素的拷贝。元素的类型必须可以转换成<const k, v>

 

key类型的约束条件

key不仅仅有类型,而且还包括对比方法。缺省条件下,使用>操作符比较key。这就是说,作为key的类型必须定义<操作。

map定义的类型

map定义的类型包括:

map<K, V>::key_type

用于索引mapkey的类型

map<K, V>::mapped_type

map中与key关联的 值的类型

map<K, V>::value_type

pair

它的第一个元素的类型必须是constmap<K, V>::key_type;第二个元素的类型必须是map<K, V>::mapped_type

value_type是一个pair,只能修改pair的值,而不能修改key

map迭代器解引用生成pair

当我们解引用一个map迭代器,得到的是一个容器值的引用, 这个值的类型是value_type类型。

Example:

// get an iterator to an element in word_count

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

 

// *map_it is a reference to a pair<const string, int> object

cout << map_it->first;                  // prints the key for this element

cout << " " << map_it->second;          // prints the value of the element

map_it->first = "new key";              // error: key is const

++map_it->second;     // ok: we can change value through an iterator

 

map添加元素

2种方法:

l  使用insert

l  先用下标操作符索引元素,然后对此元素进行赋值。

通过下标索引map

map中下标就是key。如果使用的下标值不存在,就会在map里追加一个元素,它的key就是这个下标值。

map <string, int> word_count; // empty map

// insert default initialzed element with key Anna; then assign 1 to its value

word_count["Anna"] = 1;

map下标操作的返回值类型是mapped_value

使用map::insert

一个简单的例子可以看出insert和下标操作的区别:

int main() {

            map <string, int> word_count ;

            word_count["first"] =1;

            word_count["first"] =9;

            cout << word_count["first"] << endl;

            word_count.clear();

            word_count.insert( map<string, int>::value_type("first", 1) );

            word_count.insert( map<string, int>::value_type("first", 9) );

            cout << word_count["first"] << endl;

  return 0;

}

输出:

9

1

insert返回的是一个pairfirst是指向元素的map迭代器,secondbool值,表示元素是否插入成功。如果key存在时,直接返回map中的元素迭代器;如果key不存在,创建一个新的pair,然后插入map,返回这个新元素对应的迭代器。

map查找

下标操作提供了最简单的访问获得键值的方法:

map<string,int> word_count;

int occurs = word_count["foobar"];

int occurs = word_count["foobar"];但是这样的取值方法其实还有可能隐含着一个插入操作。如果word_count不包含"foobar",则先插入以"foobar"作为key的元素。值则是按默认值处理,等于0,这样occurs就被赋值为0.

另一类方法:

m.count(k)

返回km中出现的次数

m.find(k)

如果k存在,返回指向该元素的迭代器。如果不存在,返回off-the-end迭代器。

先用这类方法进行判断,然后再用下班取值,就可以避免如果key不存在,直接取值导致向map插入元素带来的副作用。

Example(使用count检查某个key是否存在):

int occurs = 0;

if (word_count.count("foobar"))

    occurs = word_count["foobar"];

Example(读取元素而不插入元素):

int occurs = 0;

map<string,int>::iterator it = word_count.find("foobar");

if (it != word_count.end())

    occurs = it->second;

删除map元素

有三类删除元素的操作:

m.erase(k)

删除key值是k的元素。返回值的类型是size_type,表示删除元素的个数。

m.erase(p)

删除由迭代器p指向的元素。p!=m.end()。返回值是void

m.erase(b,e)

删除由迭代器b,e指定访问内的所有元素。返回值是void

 

10.4 set

其实就是只有keymap

 

10.5 multimap multiset 类型

multimap追加元素,还是按照pair来追加的。

// adds first element with key Barth

authors.insert(make_pair(

  string("Barth, John"),

  string("Sot-Weed Factor")));

 

// ok: adds second element with key Barth

authors.insert(make_pair(

  string("Barth, John"),

  string("Lost in the Funhouse")));

 

multimapfind操作

find的返回值是迭代器:

// author we'll look for

string search_item("Alain de Botton");

 

// how many entries are there for this author

typedef multimap<string, string>::size_type sz_type;

sz_type entries = authors.count(search_item);

 

// get iterator to the first entry for this author

multimap<string,string>::iterator iter =

                         authors.find(search_item);

 

// loop through the number of entries there are for this author

for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter) cout <<

       iter->second << endl; // print each title

对比mapfind操作:

//int occurs = 0;

map<string,int>::iterator it = word_count.find("foobar");

if (it != word_count.end())

    occurs = it->second;

 

另一种面向迭代器的解决方案

这种方案包含了3种操作,这3种操作返回值都是指针。它们提供了另一种访问集合元素的方法,虽然这些方法对于mapset也适用,但是更多情况还是用在multimapmultiset

m.lower_bound(k)

返回指向key值不小于k的第一个元素的迭代器。

m.upper_bound(k)

返回指向key值大于k的第一个元素的迭代器

m.equal_range(k)

返回一个迭代器的pair

first相当于m.lower_bound(k)

second相当于m. upper_bound(k)

例如,key数据如下:

1

2

3

3

5

6

6

7

7

7

8

If key=3, lower_bound=第一个3; upper_bound=5

if key=4; lower_bound=第一个5; upper_bound=5。这表明此key不存在(判断条件lower_bound= upper_bound),同时也表示出这个key在容器中的插入位置。

 

使用容器:文本查询程序

这部分其实最好先自己写写看。

需求:

读入指定文件,然后统计指定单词出现的次数,按规定的格式来显示。

规定格式包括:

l  出现的总的次数

l  行号 内容

按照这个要求我先写了一个,然后再回去读大师的说法,比对不足。

 

 

 

 

 

posted on 2009-06-04 11:22 amenglai 阅读(726) 评论(0)  编辑  收藏 所属分类: C++ Primer 之 读书笔记


只有注册用户登录后才能发表评论。


网站导航: