C++Primer笔记——第十一章：关联容器

作者: 吃远 | 来源:发表于2019-01-03 14:17 被阅读0次

一、本章学习总结

关联容器和顺序容器有根本的不同：关联容器中的元素是按关键字保存和访问的，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。
分类：按照三个属性：set或map; 顺序保存元素还是无序; 关键字是否可以重复; 可以分成8个类别。如unordered_multi_set是一个允许重复关键字，元素无序保存的集合。
关联容器不支持位置相关操作，如push_back, push_front, 或访问第k个元素c[k]。
set相比vector，用来保存不重复单词的好处：使用vecotr需要每次在输入单词时调用find检查单词是否已在vector中；且vector是无序线性表，find查找只能采用顺序查找的方式，其耗时与vec.size()成线性关系。set使用红黑树实现，其花费时间与vec.size()成对数关系。当单词量很大时set优势巨大。
关联容器迭代器的解引用为该容器对应value_type的引用。其第一个成员对应关键字，类型必定是const的。第二个成员为关键字对应的值。与vector和string不同，map的下标运算符返回的类型(mapped_type)与解引用map迭代器得到的类型(value_type)不同。

二、各小节知识点回顾

11.1 定义关联容器

关联容器的定义感觉用的比较多的有三种套路：①直接列表初始化，即大括号初始化。②构建pair类型，然后逐一insert到map中。③实际使用时先定义空map，随后根据需要使用下标访问添加元素。

使用举例：一个初始化map的例子：

 typedef pair<string, unsigned> mypair;
 map<string, unsigned> m1 = {{"word1", 1},{"word2",2},{"word3",3}};
 map<string, unsigned> m2;
 m2.insert(make_pair("map2_word1",1));  //使用make_pair可以让编译器根据v1和v2的类型推断出pair的类型
 m2.insert(make_pair("map2_word2",2));
 m2.insert(mypair("map2_word3", 43));

 cout<<"map 1: "<<endl;
 print(m1);
 cout<<"map 2: "<<endl;
 print(m2);

运行结果

$ ../../compile.sh map_defination.cpp && ./map_defination
only one arg passed.
map 1:
word1==>1
word2==>2
word3==>3
map 2:
map2_word1==>1
map2_word2==>2
map2_word3==>43

· 涉及知识点

I. pair：类似容器，pair是一个用来生成特定类型的模板。一个特别之处在于pair的数据成员first和``是public的,可以直接访问。pair的使用是非常灵活的。比如下面例子，一个需要返回pair的函数：

process(vector<string> &v)
{
    if (!v.empty())
        return {v.back(), v.back().size()};
        //return make_pair(v.back(), v.back().size());
    else
        return pair<string, int>();  //隐式构造返回值        
}

11.2 使用关联容器

① 初步认识map和set
map即关联数组，与普通数组的区别在于下标不必是整数。set则仅仅是关键字的简单集合。当想知道一个值是否存在时，set最适用。

顺便回顾下顺序容器：若元素很小（如int）且大致数量事先可知，在程序运行中不会剧烈变化，大部分情况只需要在末尾添加或删除，且需要频繁访问任意位置的元素，则vector可带来最高效率；若需要频繁在头部和胃部添加删除元素，则deque最好；若元素较大（如大的类对象），数量预先不知道，或是程序运行过程中频繁变化，对元素的访问更多的是顺序访问全部或者很多元素，则list很合适。

使用举例：单词计数程序
功能：记录给定输入单词中各个单词出现次数。注意去除标点符号和一些无意义的词如the, a等; 忽略大小写。

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <cctype>
#include <fstream>

using namespace std;
typedef vector<string> vs;

bool notpunc(const char ch)
{
    return (ispunct(ch) ? false : true); //header: cctype
}

string& transform(string &s)
{
    for (auto &c : s)
    {
        if (c>'A' && c<'Z')
            c = c - ('A' - 'a');
    }
    return s;
}

int main()
{
    ifstream in("words_list");
    string word;
    map<string, size_t> word_count;
    set<string> excluded = {"this","The","the","a","A","And","and","is"};
    while(in>>word)
    {
        // partition 不支持(w.begin(), w.end(), !ispunct) 
        auto loc = stable_partition(word.begin(), word.end(), notpunc);
        word.erase(loc, word.end());
        //set.find 返回一个迭代器，如果给定关键字在set中，迭代器指向该关键字。否则返回尾后迭代器
        if (excluded.find(word) == excluded.end())  
            word_count[transform(word)] += 1;
    }
    for (const auto &x : word_count)
    {
        cout<<"\""<<x.first<<"\""<<" occurs "<< x.second<<" times"<<endl;
    }
}

运行结果：

$ ../../compile.sh word_count.cpp && ./word_count
only one arg passed.
"1122" occurs 1 times
"Another" occurs 1 times
"above" occurs 1 times
"added" occurs 1 times
"appended" occurs 1 times
"are" occurs 1 times
"can" occurs 1 times
"chapter" occurs 1 times
"exercise" occurs 1 times
"long" occurs 1 times
"many" occurs 1 times
"more" occurs 1 times
"new" occurs 1 times
"not" occurs 1 times
"receive" occurs 1 times
"sentence" occurs 2 times

· 涉及知识点：

I. map的一个重要特点是：在使用下标运算符"[]"访问元素时，如果关键字不存在，则map会为该关键字创建一个元素并插入到map中，关联值将进行值初始化。同时map.size()将会+1. 比如map<string, shared_ptr<set>> 类型，如果下标访问的关键字不存在，则map将创建一个空的共享指针，此时就应该留意不能直接操作空指针。

II. 与之相关的方法是通过map.at(k)函数访问关键字为k的元素，同时进行参数检查。如果k不再map中，抛出out_of_range异常。

III. 一个有趣的现象：word_count这个关联容器在输出时，元素已经按照关键字的字典顺序排列好了。这就是所谓的有序容器。即map等有序容器在构建时对关键字类型是有潜在要求的：即关键字类型必须定义元素比较的方法。简而言之就是该关键字类型需要定义一个"<"运算符，或者一个实现"<"功能的操作（即严格弱序）。

使用举例：练习严格弱序：创建一个包含Sales_data类型元素的set。

#include<iostream>
#include<vector>
#include <string>
#include<set>
#include <map>

using namespace std;

class Sales_data
{
public:
    friend void print(const Sales_data&);
    Sales_data(const string &s, unsigned u, float price): bookNo(s), units(u), price(price), revenue(price * u) {}
    const string& isbn() const {return bookNo;}
private:
    string bookNo;
    unsigned units;
    float price;
    float revenue;
};

void print(const Sales_data& item)
{
    cout<<"书目: "<<item.bookNo<<"售价: "<<item.price<<"销量: "<<item.units<<"收入: "<<item.revenue<<endl;
}

bool compareIsbn(const Sales_data &i1, const Sales_data &i2)
{
    //return i1.bookNo < i2.bookNo; 注意compareIsbn函数不是友元，不能访问私有成员
    return i1.isbn() < i2.isbn();
}

int main()
{
    Sales_data i1("book-1-a", 20, 11.5);
    Sales_data i2("book-2-b", 30, 20.2);
    Sales_data i3("book-3", 40, 92.5);
    //set接收两个类型：关键字类型Sales_data，以及**比较操作类型**（即函数指针类型）；
    //同时在定义此容器类型对象(bookstore)时，需要提供想要使用的操作的指针。
    set<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);  //这里是不是就不能直接初始化bookstroe了？
    bookstore.insert(i1);
    bookstore.insert(i2);
    bookstore.insert(i3);
    cout<<"书目信息个数: "<<bookstore.size()<<endl;
    for (const auto &x : bookstore)
        print(x);
}

运行结果：

$ ../../compile.sh keyType_strict_weak_ordering.cpp && ./keyType_strict_weak_ordering
only one arg passed.
书目信息个数: 3
书目: book-1-a售价: 11.5销量: 20收入: 230
书目: book-2-b售价: 20.2销量: 30收入: 606
书目: book-3售价: 92.5销量: 40收入: 3700

注意：decltype获得一个函数指针类型时，必须加上一个*。当我们使用一个函数名时，在需要的情况下它会自动转换成一个指针。

11.3 关联容器操作

①关联容器额外的类型别名

key_type和value_type对于set来说都对应关键字类型；对于map来说前者对应关键字类型，后者对应一个pair<const key_type, mapped_type>，其中mapped_type为map所特有，代表其值的类型。

②关联容器迭代器
①中值得注意的一点是key_type前面的const。之所以这么说，是因为当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。对于map而言，其value_type为一个pair。该pair的first成员保存const的关键字，second保存成员值；对set而言由于只有关键字，故set的迭代器是const的。即set的迭代器的解引用是只读的。

使用举例：

auto map_it = word_count.cbegin();
while(map_it != word_count.cend())
{
    cout<<map_it->first<<" occurs "<<map_it->second<<" times"<<endl;
    ++map_it;
}

此外，迭代器的另一个使用场景是容器成员函数返回值时。比如insert函数。map.insert函数的用法见p384页。对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，其first成员是一个迭代器，指向具有给定关键字的元素（若给定关键字不存在，则该迭代器指向新插入的元素位置），second成员是一个bool，指出元素是插入成功还是已经存在于容器中。

使用举例：还是之前的单词计数程序，不过这里用insert实现：

while(cin>>word)
    ++word_count.insert({word, 0}).first->second;
    //若word已存在于map中，insert返回一个指向该word位置的迭代器;
    //若不存在则返回指向新插入的word对应位置的迭代器。然后对迭代器的second成员即mapped value进行增一。

③关联容器与算法
关联容器通常不使用泛型算法。比如要搜索容器时，可以用关联容器自定义的find成员函数代替泛型算法的find函数。

对于set而言，不能通过其迭代器对容器元素进行修改（添加）。即使是通过back_inserter或者inserter等试图使用插入迭代器也不行。

④multimap 和 multiset 中的元素查找

注意，这两个容器定义在各自的同名头文件中。
元素查找。直接看一个例子：打印muiltimap中某个关键字对应的所有值：

// authors 为一个 multimap<string, unsigned>类型的对象。
// 方法一：使用lower_bound和upper_bound返回一个迭代器范围
for (auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item); beg != end; ++beg)
    cout<<beg->second<<endl;

// 方法二： 直接使用equal_range
for (auto pos = authors.equal_range(search_item); pos.first != pos.second; ++pos.first)
    cout<<pos.first->second<<endl;

注意：这段代码中几个函数的返回值需要区分一下。lower_bound和upper_bound通常一起使用，来返回一个迭代器范围。当查找的元素不存在时，这两个函数返回相同的迭代器，不需要关心该迭代器具体指向哪里（可能是随便指的...）。重要的是两个迭代器指向同一个位置。equal_range返回一个迭代器pair，若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置。若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。

三、章节练习——一个单词转换的map

3.1 功能定义：

给定一个单词转换文件以及一个待转化的文本，要求输出单词转换之后的文本。映射表如下：

brb be right back
k okay?
y why
r are
u you
pic picture
thk thanks!
l8r later

3.2 分析：

考虑到需要建立的单词映射表，该程序肯定要使用map容器。此外。注意到给定的映射表存在一个简写映射多个单词的情况。要考虑如何将第一个单词（简写）读取至map的key，剩下的多个单词读取到map的value中。

刚开始尝试这么写（错误写法一）：

map<string, string> rule;
string brif, comp;
while(in>>brif>>comp)
{
    rule.insert(make_pair(brif, comp));
}
return rule;

但是这样写有两个问题：①显然映射文件的每行代表一条映射，这样读取输入流就丢弃了行信息；
②in>>brif>>comp将string 两两配对。如果映射关系每行都只有两个单词的话可行。但是无法完成如"brb --> be right back" 这样的映射。

后来又这么写（错误写法二）：

string line, word;
vector<string> line_vec;
while(getline(in_map, line))
{
    //处理每一行
    stringstream stream(line);
    while(stream>>word)
        line_vec.push_back(word);
    mps.insert(make_pair(line_vec[0], accumulate(line_vec.begin()+1, line_vec.end(), string(" "))));
}

这样写是希望将每行读入一个vector中，然后把vector第一个元素作为key，后面所有元素拼接起来作为value...可惜accumulate的第三个参数不是dilemma，而是初始元素...所以这样拼接之后元素都连在一起。

正确写法：对于每一行，先使用in>>word读取一个，然后再使用getline读取后面的输入流：while(in>>brif && getline(in, comp)。完整程序如下：

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <sstream>
#include <fstream>
#include <iterator>
using namespace std;

void print_map(const map<string, string> m)
{
    for (const auto &d : m)
    {
        cout<<d.first<<" -> "<<d.second<<endl;
    }
}

map<string, string> buildMap(ifstream &in)
{
    map<string, string> rule;
    string brif, comp;
    while(in>>brif && getline(in, comp))
    {
        rule.insert(make_pair(brif, comp.substr(1)));
    }
    return rule;
    /**
    while(in>>brif>>comp)
    {
        rule.insert(make_pair(brif, comp));
    }
    return rule;
    **/
}

string transform(const string &s, const map<string, string> &m)
{
    auto rst = m.at(s);
    return rst;
}

int main()
{
    ifstream file_rule("map_rule.txt");
    ifstream text("text.txt");
    if (!file_rule)
    {
        cout<<"fail to open file map_rule.txt"<<endl;
        exit(0);
    }
    if (!text)
    {
        cout<<"fail to open file text.txt"<<endl;
        exit(0);
    }
    auto rule = buildMap(file_rule);
    cout<<"[INFO] build up transform mapping rule:"<<endl;
    //cout<<"size:"<<rule.size()<<endl;
    print_map(rule);

    cout<<"[INFO] transformed text: "<<endl;
    string line, word;
    while(getline(text, line))
    {
        istringstream stream(line);
        while(stream>>word)
        {
            if (rule.find(word)!=rule.end())
            {
                cout<<transform(word, rule)<<" ";
            }
            else
                cout<<word<<" ";
        }
        cout<<endl;
    }
}

在查代码的时候发现一段有趣的程序，使用Istringstream可以方便的对string进行split，也记录在下面：
参考：stackoverflow

#include <iostream>
#include <sstream>

std::string input = "abc,def,ghi";
std::istringstream ss(input);
std::string token;

while(std::getline(ss, token, ',')) {
    std::cout << token << '\n';
}

C++Primer笔记——第十一章：关联容器

一、本章学习总结

二、各小节知识点回顾

11.1 定义关联容器

· 涉及知识点

11.2 使用关联容器

· 涉及知识点：

11.3 关联容器操作

三、章节练习——一个单词转换的map

3.1 功能定义：

3.2 分析：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读