C++-树形关联式容器set的使用

1. 关联式容器

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高.

2. set的介绍

1. set是按照一定次序存储元素的容器 2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。 3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。 4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对 子集进行直接迭代。 5. set在底层是用二叉搜索树(红黑树)实现的。

注意：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放

value，但在底层实际存放的是由<value, value>构成的键值对。

2. set中插入元素时，只需要插入value即可，不需要构造键值对。

3. set中的元素不可以重复(因此可以使用set进行去重)。

4. 使用set的迭代器遍历set中的元素，可以得到有序序列

5. set中的元素默认按照小于来比较

6. set中查找某个元素，时间复杂度为：log_2 n

7. set中的元素不允许修改

8. set中的底层使用二叉搜索树(红黑树)来实现

3.set的使用

3.1 set的模板参数列表 

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。

Compare：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

3.2 insert

set的insert就是直接插入即可，特点就是排序加去重，如果插入一个存在的value，则不会成功。

3.3 迭代器

迭代器也是一样的套路，相当于在二叉搜索树中走了一个中序遍历，反向迭代器和范围for也是一样的玩法。

3.4 find 

find可以查找一个value，并且返回这个位置的迭代器。

3.5 erase

这里的erase不会返回下一个节点的下标，所以需要一个一个删除，或者是给一段区间去删除，可以和find配合起来使用，如果想要删除3-5这个闭区间的value，那么就可以使用find返回迭代器。

如果直接使用erase去删除，如果这个value不存在则不做处理。

3.6 count

count这个接口就是用来查找这个value存在多少个，所以可以用来判断有没有这个value。 

3.7 lower_bound和upper_bound

如果我们想删除3-5这段闭区间之间的值，使用find就不可行了。因为3和5不一定在，就不一定找得到，还有一个问题就是迭代器的区间一般是左闭右开，所以find不可行，这个时候就要使用lower_bound和upper_bound了。如果3存在则返回3，如果3不存在则返回4，也就是>=value的值。那么upper_bound有5则返回的是6，符合左闭右开的要求，没有5返回的也是6，也就是>value的·值。

void test_set2()
{
	// 排序+去重
	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;
	//s.erase(start, finish);

	while (start != finish)
	{
		cout << *start << " ";
		++start;
	}
	cout << endl;

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

 4.multiset

如果set是排序加去重的话，那么multiset就是纯排序，允许键值冗余。

那么erase的第二个模板就能很好的用起来了，返回有几个value。

 那么find一个value的话，返回的是哪一个呢？返回的是中序遍历的第一个。