首先要知道set的底层是由红黑树（平衡二叉搜索树）实现的。
Tset存放元素类型，底层是<value, value>的键值对。Compare仿函数，因为实现搜索树需要比较。
void test_set()
{
// 默认构造
set<int> s1;
// 迭代器区间构造
int a[] = { 1, 2, 3, 4 };
set<int> s2(a, a + 4);
// 拷贝构造（深拷贝）
set<int> s3(s2);
for (int e : s2) cout << e << " ";
cout << endl;
for (int e : s3) cout << e << " ";
cout << endl;
}
可以看到set有反向迭代器。
void test1()
{
set<int> s;// 排序+去重
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(3);
s.insert(4);
// 正向迭代器
set<int>::iterator it1 = s.begin();
while (it1 != s.end())
{
cout << *it1++ << " ";
}
cout << endl;
// 反向迭代器
set<int>::reverse_iterator it2 = s.rbegin();
while (it2 != s.rend())
{
cout << *it2++ << " ";
}
cout << endl;
}
因为set的仿函数默认参数是less<T>，所以排的是升序，如果我们想排降序就可以传递greater<T>。
void test1()
{
set<int, greater<int>> s;// 排序+去重
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(3);
s.insert(4);
// 正向迭代器
set<int>::iterator it1 = s.begin();
while (it1 != s.end())
{
cout << *it1++ << " ";
}
cout << endl;
// 反向迭代器
set<int>::reverse_iterator it2 = s.rbegin();
while (it2 != s.rend())
{
cout << *it2++ << " ";
}
cout << endl;
}
1.2.3.1 insert && find && erase
void test2()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
set<int>::iterator it = s.find(3);
s.erase(it);
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
}
1.2.3.2 count
传进去一个元素数值，返回该元素的个数。
void test2()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
cout << s.count(2) << endl;
cout << s.count(6) << endl;
}
因为set的元素是唯一的，所以在set这里count可以用find来代替，但是在后面的multiset可以插入重复的元素，count就可以统计该元素的个数。
multiset和set的区别是它可以插入重复的元素。其他的接口跟set一致。头文件也跟set相同。
void test3()
{
multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(2);
ms.insert(3);
ms.insert(4);
for (auto& e : ms)
{
cout << e << " ";
}
cout << endl;
cout << "count(1): " << ms.count(1) << endl;
}
另外使用find查找时，如果有多个值相同，find返回的值是中序的第一个。
key键值对中key的类型T键值对中value的类型
注意：
1️⃣ map中的元素总是按照键值key进行比较排序的。
2️⃣ map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
构造和迭代器跟上面的set类似，就不过多阐述。
2.2.1.1 insert
void test4()
{
map<string, int> m;
m.insert(pair<string, int>("a", 1));// 匿名对象
m.insert(make_pair("b", 2));// 简化写法
m.insert(make_pair("c", 2));
m.insert(make_pair("d", 2));
map<string, int>::iterator it = m.begin();
while (it != m.end())
{
cout << (*it).first << "->" << (*it).second << endl;
it++;
}
}
make_pair:函数模板，不需要像pair一样显示声明类型，而是通过传参自动推导。
2.2.1.2 统计次数
1️⃣ 使用find，利用迭代器
int main()
{
string arr[] = { "北京", "武汉", "广州", "上海", "北京", "北京", "广州",
"上海", "上海" };
map<string, int> cnt;
for (auto& e : arr)
{
map<string, int>::iterator fd = cnt.find(e);
if (fd == cnt.end())
{
cnt.insert(make_pair(e, 1));
}
else
{
fd->second++;
}
}
for (auto& e : cnt)
{
cout << e.first << "->" << e.second << endl;
}
return 0;
}
2️⃣ 使用[]
int main()
{
string arr[] = { "北京", "武汉", "广州", "上海", "北京", "北京", "广州",
"上海", "上海" };
map<string, int> cnt;
for (auto& e : arr)
{
cnt[e]++;
}
for (auto& e : cnt)
{
cout << e.first << "->" << e.second << endl;
}
return 0;
}
[] 可以用来插入、修改、查找
[] -> (*((this->insert(make_pair(k,mapped_type()))).first)).second
// 等价于
V& operator[](const K& k)
{
pair<iterator, bool> ret = insert(make_pair(k, V()));
return ret.first->second;
}
这里就可以看出使用[]的时候要注意：如果没有它会直接插入。
所以我们想插入就可以：
int main()
{
map<string, int> m;
// 插入
m["广西"];
m["广东"] = 1;
for (auto& e : m)
{
cout << e.first << "->" << e.second << endl;
}
return 0;
}
当我们想要修改的时候不能用insert，因为只要key相同就会插入失败。
int main()
{
map<string, int> m;
// 插入
m["广西"];
m["广东"] = 1;
m.insert(make_pair("广东", 2));// 插入失败
for (auto& e : m)
{
cout << e.first << "->" << e.second << endl;
}
return 0;
}
先要修改可以：
m["广东"] = 2;
key不在就是插入，key在就是查找。
int main()
{
multimap<string, int> mm;
mm.insert(make_pair("北京", 1));
mm.insert(make_pair("北京", 2));
mm.insert(make_pair("北京", 1));
mm.insert(make_pair("上海", 1));
for (auto& e : mm)
{
cout << e.first << "->" << e.second << endl;
}
return 0;
}multimap容器与map容器的底层实现以及成员函数的接口都是基本一致,而multimap的key可以重复。注意multimap没有[]。
使用multimap统计次数：
int main()
{
multimap<string, int> mm;
string arr[] = { "北京", "武汉", "广州", "上海", "北京", "北京", "广州",
"上海", "上海" };
for (auto& e : arr)
{
map<string, int>::iterator fd = mm.find(e);
if (fd == mm.end())
{
mm.insert(make_pair(e, 1));
}
else
{
fd->second++;
}
}
for (auto& e : mm)
{
cout << e.first << "->" << e.second << endl;
}
return 0;
}
