set和map
- 1.关联式容器
- 2. 键值对
- 3. set
- 3.1 介绍
- 3.2 简单使用
- 4.multiset
- 5.map
- 5.1 介绍
- 5.2 简单使用
- 6. multimap
1.关联式容器
关联式容器是一种STL容器，用于存储键-值对。它们提供了一种通过键来快速查找值的机制。STL总共实现了两种不同结构的管理式容器：树型结构（map、set、multimap、multiset）与哈希结构。在关联式容器中，里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高.
2. 键值对
概念：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
STL中键值对结构的定义：
template<class T1,class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair():first(T1()),second(T2())
{}
pair(const T1& a,const T2& b):first(a),second(b)
{}
};
3. set
3.1 介绍
- set的底层是二叉搜索树（红黑树）。
- set中的数据是有序且去重的。
- set中的数据是被const修饰的，所以不能修改，但是可以插入和删除。
- set默认的排序是按照从小到大的。如果想要按照自己的想法排序，需要自己写一个仿函数。
- 和map不同的是，set底层的键值对不是<key,value>而是<value,value>。
- set容器查找效率很高，时间复杂度为O(log2 N)
3.2 简单使用
- begin() 返回set容器的第一个元素
- end() 返回set容器的最后一个元素
- clear() 删除set容器中的所有的元素
- empty() 判断set容器是否为空
- insert() 插入一个元素
- size() set容器内元素个数
- clear() 清空容器
int main()
{
//去重加排序
set<int> s;
s.insert(10);
s.insert(10);
s.insert(1);
s.insert(20);
s.insert(20);
s.insert(8);
s.insert(5);
cout << s.size() << endl;
set<int>::iterator it = s.begin();
while (it != s.end())
cout << *it++ << " ";
cout << endl;
s.clear();
cout << s.size();
return 0;
}
- count()
用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了
void test2()
{
set<int> s;
s.insert(10);
s.insert(10);
s.insert(1);
s.insert(20);
s.insert(20);
s.insert(8);
s.insert(5);
cout << "10的个数：" << s.count(10) << endl;
cout << "5的个数：" << s.count(5) << endl;
cout << "100的个数：" << s.count(100) << endl;
if (s.count(10))
{
//do...
}
}
erase(iterator) 删除迭代器iterator指向的值
erase(first,second) 删除迭代器first和second之间的值
erase(key_value) 删除键值key_value的值
注:前两个必须保证迭代器有效，不然程序会崩溃，最后一个，不管值存不存在都可以
void test3()
{
set<int> s;
set<int>::const_iterator iter;
set<int>::iterator first;
set<int>::iterator second;
for (int i = 1; i <= 10; ++i)
{
s.insert(i);
}
//第一种删除
s.erase(s.begin());
//第二种删除
first = s.begin();
second = s.begin();
second++;
second++;
s.erase(first, second);
//第三种删除
s.erase(8);
cout << "删除后 set 中元素是 ：";
for (iter = s.begin(); iter != s.end(); ++iter)
{
cout << *iter << " ";
}
cout << endl;
}
lower_bound(key_value) 返回第一个大于等于key_value的迭代器
upper_bound(key_value) 返回最后一个大于key_value的迭代器
这两个函数也可以用于于删除一个区间的数据。
void test4()
{
set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(4);
auto start = s.lower_bound(3); // >=val
cout << *start << endl;
auto finish = s.upper_bound(5); // >val
cout << *finish << endl;
while (start != finish)
{
cout << *start << " ";
++start;
}
cout << endl;
}
4.multiset
该容器允许键值重复，其他的使用和set差不多。这样count()的作用就显现出来了。还有一个不同的是find()返回的是中序遍历的第一个。
5.map
5.1 介绍
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。
- 在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair: typedef pair<const key, T> value_type;
- 在内部，map中的元素总是按照键值key进行比较排序（默认升序）的。
- 和set一样key不允许修改，但是key所关联的value可以修改。
- map支持下标访问符（set不支持），即在[]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))
5.2 简单使用
map的使用和set的使用基本是差不多，但是map的[]运算符使用起来还是很方便的，下面就简单介绍几种。
- 插入数据的几种方法：
//1.直接insert pair
map<string,int> m;
m.insert(pair<string,int>("apple",1));
//2. 直接insert value_type 其实本质和第一种方式一样
map<string,int> m;
m.insert(map<string,int>::value_type("apple",1));
//3. 使用[]运算符，这种是最简便的方法
map<string,int> m;
m["apple"] = 1;
- 修改数据
//如果数据原本不存在，就相当于插入操作
map<string,int> m;
m["apple"]++;
- 查找数据
map<string,int> m;
if(m["apple"])
cout << m[apple] << endl;
6. multimap
和map不同的是，multimap允许有重复的key值，但这同时也导致了multimap没有[]这个运算符，因为会导致二义性。
