- map 简介
- unordered_map 无序map
- map 的插入
- multimap 多重map
- map 输出
- find
- equal_range
- set 容器
map底层由排序二叉树，也就是红黑树实现
我们来看一段示例代码，通过map统计string中各字符串出现的次数
int main()
{
string stra[] = { "map","deque","queue","vector","list","map","vector","map" };
std::map<string, int> simap; //iterator 双向迭代器
for (auto& x : stra)
{
simap[x] += 1;
//在这里与我们常识不同的是，这里方括号中写入的是字符串而不是整型
}
std::map<string, int>::iterator it = simap.begin();
for (; it != simap.end(); ++it) // it+=2 error!!!
{
cout << it->first << "==>" << it->second << endl;
}
return 0;
}
我们的key 与 value 在map中存放是以一个对的形式存放的
template<class _Key,class _Val>
class map
{
typedef pair<const _Key,_Val> value_type;
using value_type = pair<const _Key,_Val>;//c11
}
value_type由pair进行重命名，由对进行命名
我们通过输出结果可以看出来，输出顺序是由自小到大进行排列的，那么如何让其由大到小进行排列呢
int main()
{
string stra[] = { "map","deque","queue","vector","list","map","vector","map" };
std::map<string, int,std::greater<string>> simap; //iterator 双向迭代器
std::map<string, int, std::greater<string>>::value_type;
for (auto& x : stra)
{
simap[x] += 1;
}
std::map<string, int, std::greater<string>>::iterator it = simap.begin();
for (; it != simap.end(); ++it) // it+=2 error!!!
{
cout << it->first << "==>" << it->second << endl;
}
return 0;
}
这样就可以根据字典的由高到低进行打印，其中顺序的排列相关到二叉树的旋转
map迭代器的类型也是由键值对构成，在迭代中我们的节点有两个预购成，一个是 first 代表字符串一个是 second 代表整型值
unordered_map 无序map无序map的底层由哈希表进行实现
int main()
{
string stra[] = { "map","deque","queue","vector","list","map","vector","map" };
std::map<string, int> simap;
std::unordered_map<string, int> unmap;
for (auto& x : stra)
{
simap[x] += 1;
unmap[x] += 1;
}
std::map<string, int>::iterator it = simap.begin(); //re_tree
for (; it != simap.end(); ++it) // it+=2 error!!!
{
cout << it->first << "==>" << it->second << endl;
}
cout << endl;
std::unordered_map<string, int>::iterator uit = unmap.begin(); //hash(key)
for (; uit != unmap.end(); ++uit)
{
cout << uit->first << "==>" << uit->second << endl;
}
return 0;
}
map 与 unordered_map 的选择在于是否希望关键码有序
我们在这里写了通过年龄去查找名字的map，并且年龄不可以重复
int main()
{
std::map<int, string> age_namemap;
int age;
string name;
while (cin >> age >> name, age >= 16 || name != "end")
{
age_namemap[age] = name;
age_namemap.insert(std::map<int, string>::value_type(age, name));;
//age_namemap.insert(age,name); error!!!
}
for (auto& x : age_namemap)
{
cout << x.first << "==>" << x.second << endl;
}
}
我们可以通过，age_namemap[age] = name;进行插入
同时也可以age_namemap.insert(std::map这样插入
但是不可以直接age_namemap.insert(age,name);
这是因为需要传入的是一个对，所以必须按照pair对的方式进行插入
所以age_namemap.insert(pair这样的插入方式也是可以的
若允许年龄可以重复该怎么做
int main()
{
std::multimap<int, string> anmap; //关键码可以重复
std::map<int, string> namap; //关键码不可以重复
namap[23] = "zyq";
namap[24] = "cbq";
namap[23] = "hello";
for (auto& x : namap)
{
cout << x.first << "==>" << x.second << endl;
}
return 0;
}
首先我们看这一段代码，对map的关键码进行重复输入，那么新的name就会将旧的name进行覆盖
operator[]根据关键码进行访问数据，实际返回的是引用的方式，若键不存在则插入键值对，若存在则会进行返回
namap.insert(map<int, string>::value_type(23, "zyq"));
namap.insert(map<int, string>::value_type(24, "cbq"));
namap.insert(map<int, string>::value_type(23, "hello"));
当我们通过insert，进行插入的时候并不会进行覆盖
insert 所返回的是一个键值对std::pair
//返回的pair类型为，map迭代器，bool
//auto it = namap.insert(map::value_type(23, "zyq"));
std::pair<map<int,string>::iterator,bool> it = namap.insert(map<int, string>::value_type(23, "zyq"));
it = namap.insert(map<int, string>::value_type(24, "cbq"));
it = namap.insert(map<int, string>::value_type(23, "hello"));
第一步：first返回迭代器指向键值对，second返回true
第二步：first返回迭代器键值对，second返回true
第三步：first返回第一步的迭代器，second返回false
这一步在插入的过程中，首先使用关键码进行比较，发现关键码已经存在，那么“hello”无法插入，并且返回该关键码存放的数据，并且将布尔值赋为false
多重map
int main()
{
std::multimap<int, string> anmap; //关键码可以重复
std::map<int, string> namap; //关键码不可以重复
//namap[23] = "zyq";
//namap[24] = "cbq";
//namap[23] = "hello";
auto it = anmap.insert(map<int, string>::value_type(23, "zyq"));
it = anmap.insert(map<int, string>::value_type(24, "cbq"));
it = anmap.insert(map<int, string>::value_type(23, "hello"));
for (auto& x : anmap)
{
cout << x.first << "==>" << x.second << endl;
}
return 0;
}
int main()
{
std::map<string, int> simap;
simap["zyq"] = 20;
simap["cbq"] = 21;
simap["scz"] = 22;
string name;
while (cin >> name, name != "end")
{
cout << simap[name] << endl;
}
}
在这里对未知的关键码输出0
若使用at()对关键码对应的值进行输出
int main()
{
std::map<string, int> simap;
simap["zyq"] = 20;
simap["cbq"] = 21;
simap["scz"] = 22;
string name;
while (cin >> name, name != "end")
{
//cout << simap[name] << endl;
cout << simap.at(name) << endl;
}
}
at()方式会抛出异常，这就是与下标方式的不同
在 map 进行查找关键码，找到则返回该关键码的迭代器，未找到则返回 simap.end()
int main()
{
std::map<string, int> simap;
simap["zyq"] = 20;
simap["cbq"] = 21;
simap["scz"] = 22;
std::map<string, int>::iterator it = simap.find("zyq");
if (it != simap.end())
{
cout << it->first << " " << it->second << endl;
}
else
{
cout << "no key" << endl;
}
return 0;
}
std::map<string, int>::iterator it = simap.find("gg");
该迭代器对map从头到尾进行查找，直到迭代器等于 simap.end()
返回匹配特定键的元素范围
返回容器中所有拥有给定关键的元素范围，范围以两个迭代器定义，一个指向首个不小于key的元素，另一个指向首个大于key的元素，首个迭代器可以换用lower_bound()获得，而第二个迭代器可换用upper_bound()获得
std::pair<iterator,iterator> equal_range(const Key& key);
这里返回的是键值对，其中由两个迭代器组成
int main()
{
std::map<int, char> icmap;
for (int i = 0;i < 26; ++i)
{
icmap[i] = 'a' + i;
}
for (auto& x : icmap)
{
cout << x.first << "==>" << x.second;
}
cout << endl;
std::pair<map<int, char>::iterator, map<int, char>::iterator> it;
it = icmap.equal_range(15);
cout << it.first->first << "==>" << it.first->second << endl;
cout << it.second->first << "==>" << it.second->second << endl;
return 0;
}
equal_range 返回一个对，这个对中由两个迭代器组成，第一个迭代器对应 first，第二个迭代器对应 second，并且这个first，second也是键值对
first 指向了 15==>p，而 second 指向了下一个对 16==>q
int main()
{
std::map<int, char> icmap;
int k = 0;
for (int i = 0;i < 26; ++i)
{
icmap[k] = 'a' + i;
k += 5; //在这里进行改动！！！
}
for (auto& x : icmap)
{
cout << x.first << "==>" << x.second;
}
cout << endl;
std::pair<map<int, char>::iterator, map<int, char>::iterator> it;
it = icmap.equal_range(15);
cout << it.first->first << "==>" << it.first->second << endl;
cout << it.second->first << "==>" << it.second->second << endl;
return 0;
}
第一个迭代器指向关键码为15的节点，第二个迭代器指向其后继节点
it = icmap.equal_range(16);
当我们去寻找16，无法找到16的情况，第一第二个迭代器都为第一个高于16的值
- set中的元素都是排好序的
- set集合中没有重复的元素
int main()
{
std::set<int> iset;
int x;
while (cin >> x, x != -1)
{
if (iset.count(x)) // count x存在返回1 不存在返回0
{
cout << "已经有了：" << x << endl;
}
else
{
iset.insert(x);
}
}
return 0;
}
set 可以记录那些值重复，但是不能记录重复了多少次
若希望记录某值出现次数，则使用map更合适
int main()
{
map<int, int> iimap;
for (int i = 0; i < 10000; ++i)
{
int x = rand() % 10000;
iimap[x] += 1;
}
return 0;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）