C++ 关联容器

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、使用
• 二、关联容器概述
• • pair类型
• 关联容器 *** 作
• • 增
  • 删
  • map下标
  • 访问元素
  • 单词转换 map
• 无序容器
• 总结

---

前言

关联容器map和set

最简单的散列表：数组，arr[key] = value

按关键字有序保存元素		底层实现	查询效率	增删效率
map	关联数组：保存关键字-值对	红黑数	O(log n)	O(log n)
set	关键字即值，即只保存关键字的容器	红黑数	O(log n)	O(log n)
multimap	关键字可重复出现的map	红黑数	O(log n)	O(log n)
multiset	关键字可重复出现的set	红黑数	O(log n)	O(log n)
按关键字无序保存元素
unordered_map	用哈希函数组织的map	哈希表	O(1)	O(1)
unordered_set	用哈希函数组织的set	哈希表	O(1)	O(1)
unordered_multimap	哈希组织的map：关键字可以重复出现
unordered_multiset	哈希组织的set：关键字可重复出现

---

一、使用

一个值是否存在用set

//单词计数
//       key type,value type
std::map<string, size_t>  word_count;
string word;
while (cin >> word) ++word_count[word]; //若word不在关键字中，自动创建关键字，其值为0
for (const auto &w : word_count)
	cout << w.first << " occurs " << w.second
	     << ( (w.second>1)?" times ":" time " ) << endl;

//使用set
map<string, size_t> word_count;
set<setstring> exclude = {"The", "But"};
string word;
while (cin >> word)
// 若word在exclude中find返回指向该元素的迭代器，否则返回尾后迭代器
	if (exclude.find(word) == exclude.end())
		++ word_count[word];

看一个例子：

bool my_tolower(string &wd){
    for (auto it = wd.begin(); it != wd.end(); ++it)
        *it = std::tolower(*it); 
    return true;
}
int main(){
    vector<string> lst1 ={"AVC", "sIdf"},lst2;
    std::copy_if(lst1.begin(), lst1.end(), 
    //泛型算法向谓词传递的是 解引用的迭代器，即引用类型，指向lst1的元素
    //变为小写后，根据谓词返回结果决定是否将该元素 拷贝 到迭代器所指的位置
            std::inserter(lst2, lst2.begin()), my_tolower/*通过该谓词将单词变为小写*/ );
    for (auto c:lst1) cout << c << " "; cout << endl;   //avc sidf
    for (auto c:lst2) cout << c << " "; cout << endl;   //avc sidf
    for (auto it = lst2.begin(); it != lst2.end(); ++it){
        *it = "aa";
    }
    for (auto c:lst1) cout << c << " "; cout << endl;  //avc sidf
    for (auto c:lst2) cout << c << " "; cout << endl;  //aa aa
return 0;}

二、关联容器概述

关联容器的迭代器都是双向的

map<string, size_t> wd_count; //空容器
//列表初始化
set<string> exlude = {"a", "asdf"};
map<string, string> authors = {{key:value}, {key2:value2}};

vector<int> ivec = {1,1,2,2};
set<int> iset(ivec.cbegin(), ivec.end());
multiset<int> miset(ivec.cbegin(), ivec.cend());

要求：
有序容器要求其key必须定义比较的方法，默认用 <

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs){
	return lhs.isbn() < rhs.isbn();
}
std::multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
std::multiset<Sales_data, bool(*)(const Sales_data &,const Sales_data &)> 
			  bookstore(compareIsbn);

pair类型

标准库类型pair定义在头文件 utility 中

pair<T1, T2> p;
pair<T1, T2> p(v1, v2);
pair<T1, T2> p={v1, v2};
std::make_pair(v1, v2);  /返回一个用v1， v2初始化的pair，pair的类型从v1和v2的类型推断出来
p.first
p.second
p1 relop p2    关系运算符(<、 <=、 >、 >=)

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

关联容器 *** 作

key_type	此容器类型的关键字类型
mapped_type	每个关键字关联的类型；只适用于map
value_type	对于set，与key_type相同 对于map，为pair

一个map的value_type是一个pair， 可以改变pair的值，但是不能改变关键字成员的值
set的迭代器是 const 的

auto map_it = wd_count.cbegin();
while (map_it != wd_count.cend()){
	map_it -> first;
	map_it -> second;
	++ map_it;
}

关联容器的关键子是 const 的意味着

增

vector<int> ivec = {2,4,6,8,2,4,6,8};
set<int> set2;
set2.insert(ivec.cbegin(), ivec.ceng());
set2.insert({1,3,5,7,9});

wd_count.insert({word, 1});
.insert(make_pair(word, 1));
.insert(pair<string, size_t>(word, 1) );
.insert(map<string, size_t>::value_type(word, 1));

map<string, size_t> word_count;
string word;
while (cin >> word){
	auto res = word_count.insert({word, 1});
	if (!res.second)
		++  res.first -> second ;
}

multimap<string, string> authors;
authors.insert( {"A", "lele"} );
authors.insert( {"A", "haha"} );

删

c.erase(k);    //从c中删除每个关键字为k的元素。返回
c.erase(p);	   //删除迭代器p指定的元素，p必须指向一个真实的元素不能等于c.end()。
			   //返回一个指向p之后元素的迭代器，若p指向c中的尾元素，则返回c.end()
c.erase(b, e); //删除[b,e)范围内的元素

map下标

set 不支持下标

map<string, size_t> word_count;
word_count["Anna"] = 1;

c[key];    //返回左值，若k不在c中，则插入k并初始化值
c.at(key); //访问关键字为k的元素，带参数检查；多k不在c中，抛出out_of_range异常

• 在word_count中搜索关键字为Anna的元素，未找到
• 将新关键字-值插入到word_count中，关键字是一个const string，保存Anna，值进行初始化
• 提取出新插入的元素，并将值1赋予它

访问元素

set<int> iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1);    //返回一个迭代器，指向key == 1 的元素
iset.find(11);   //返回 .end()
iset.count(1);   //return 1
iset.count(11);  /return 0

string search_item("Alasdf");
auto entries = authors.count(search_item);
auto iter = authors.find(search_item);
while(entries--){
	cout << iter->second << endl;
	++iter;
}

for (auto beg = author.lower_bound(search_item), end = authors.upper_bound(search_item);
	beg != end; ++ beg){
	cout << beg -> second << endl;
}

for(auto pos = author.equal_range(search_item); pos.first != pos.second; ++pos.first){
	cout << pos.first->second << endl;
}

单词转换 map

map<string, string> buildMap(ifstream &map_file){
    string line;
    map<string, string> trans_map;
    while (getline(map_file, line)){
        istringstream wds(line);
        string key, value;
        wds >> key >> value;
        trans_map[key] = value;
    }
    return trans_map;
}
string& transform(string &wd, map<string, string> &trans_map){
    auto res = trans_map.find(wd);
    if (res != trans_map.end())
        return  res -> second;
    else
        return wd;
}
void word_transform(ifstream &map_file, ifstream &input){
    auto trans_map = buildMap(map_file);
    string line;
    while (getline(input, line)){
        istringstream words(line);
        bool first_wd = true;
        string wd;
        while (words >> wd){
            if (first_wd)
                first_wd = false;
            else
                cout << " ";
            cout << transform(wd, trans_map) ;
        }
        cout << endl;
    }
}
int main(){
    ifstream map_file("./mapped.txt"), input("./origin.txt");
    word_transform(map_file, input);
return 0;}

无序容器

桶

无序容器对关键字类型的要求
必须是hashable

size_t hasher(const Sales_data &sd){
	return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data *rhs){
	return lhs.isbn() == rhs.isbn();
}
using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
//参数是桶大小、哈希函数指针和相等性判断运算符指针
SD_multiset bookstore(42, hasher, eqOp);

如果类中已经定义了 == 运算符，则可以只重载哈希函数：

//使用FooHash生成哈希值；Foo必须有 == 运算符
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);

---

总结

• 关联容器是一个map或是一个set。map保存 key-value对；set只保存关键字
• 关键字唯一或不唯一
• 关键字有序或无序

有序容器使用比较函数来比较关键字，从而将元素按顺序存储。默认采用关键字类型的 < 运算符。
无序容器使用关键字类型 == 运算符和一个hash类型的对象类组织元素。