4-4第一次完善了pair类型T 多样的初始化 迭代器的内部

序列式容器与关联式容器

序列式容器：像vector、list、deqeue等逻辑结构为线性的容器  两个位置间的数据进行交换时依旧是序列式容器。

关联式容器：像map、set和unordered_map、unordered_set系列。关联式容器的逻辑结构通常不是线性的，元素间交换一下 逻辑结构就被破坏了。

set类

template<class T, 
         class Compare = less<T>, 
         class Alloc = allocator<T>
         > 
class set
{
    …………
};

set类的介绍

T是set底层的关键字类型。

无重复数据，less<T>代表小于比较与存储->中序遍历为升序序列。

set默认要求T支持小于比较，如果不支持或者想按照自己的需求定义比较可以自己实现仿函数来传递给第二个模板参数。

set底层存储数据的内存是从空间配置器中申请的，如果需要可以自己实现内存池，传递给第三个参数。(一般情况下我们都不需要传后两个模板参数)

set底层是使用红黑树实现的，增删查的效率是O(logN),迭代器遍历走的是搜索树的中序，所以是有序的。

set的初始化

可使用"初始化列表"进行初始化:

int main()
{
    //构造    
    std::set<int> s0;

	//列表初始化
	std::set<int> s1({ 2,123,23,14,3 });
	std::set<int> s2 = { 2,123,23,14,3 };
	std::set<int> s4{ 1 };

	//拷贝构造
	std::set<int> s5 = s1;
	std::set<int> s6(s2);

	return 0;
}

当T是pair类型时：

比较插入：先比较first若相等则比较second

迭代器

双向迭代器 遍历默认(中序遍历)按照升序顺序，因为底层是搜索二叉树。但是set的iterator 与 const_iterator均不支持修改数据 。 因为修改数据导致结构混乱

lower_bound与upper_bound

iterator lower_bound(const value_type& val);    //返回最初大于等于val位置的迭代器。

iterator upper_bound(const value_type& val);   //返回最初大于val位置的迭代器。

multiset类

与set类共属于同一个头文件<set>。

其区别在于multiset支持多个重复值，一些函数实现围绕此差异展开。

find查找中序的第一个指定数据、erase删除所有值相同的数据、count返回计数结果。

map类

不同于set的单数据val  map具有两个数据分别是key与val。

template<class K, 
         class T, 
         class comp = less(K), 
         class Alloc = allocator<pair<K,T>>
class map
{
    ……
}

参数

key:

key通常作为唯一标识，避免重复。例如：用户的ID作为key，用户的信息作为value。
快速查找：key作为标识符直接访问对应的内部信息。
排序与去重：在有序map中key自动排序，插入相同的key会覆盖原有value！！

value：

value允许更新而key通常不可变。

set的建构逻辑默认按照key来进行升序的排序。

map的底层是使用红黑树来实现的，增删查改的效率是O(logN)。

迭代器

迭代器it类型std::pair<const K, T>。访问通过first与second访问。

单向(++)迭代器按照红黑树的中序前进。

pair

pair下有两个参数对理解、使用map十分重要。

map内有key，val两个值在于pair的存储功能当插入。

map<string, int> m;
m["first"]++;

map的[]

区别于一般容器的[ ]，map的[ ]拥有查找、插入、修改三大功能。

例如对于：m.[key_name] = "key_e_name";   
找到了：返回对应位置value的引用。
找不到：新增"key_name"的元素，并返回其引用。

官方文档解释如下：

insert的原理

经常使用的map对象插入方法：

erase所有情况分析

• set/map：erase(key)返回删除的元素数量（0或1）。
• multiset/multimap：erase(key)返回删除的元素总数（可能大于1）。

注意：
1.非bool类型的返回值，返回的是数目。
2.迭代器失效。