1.序列式容器和关联式容器
在认识map和set之前，关于容器，有两个重要的分类
序列式容器：按照元素插入的顺序保存数据，关注元素的顺序和位置，由于逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，元素是按他们在容器中的存储位 置来顺序保存和访问的，如string、vector、list、deque、array、forward_list等
关联式容器：通过关键字来存储和访问元素，关注的是元素之间的关系，逻辑结构通常是⾮线性结构， 两个位置有紧密的关联关系，如果交换顺序，它的存储结构就被破坏了，如map/set系列和unordered_map/unordered_set系列
2.1 set的声明
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
> class set;
- set默认要求T支持小于比较，如果想按本身的需求可以自行实现仿函数传给第⼆个模版参数
- set底层存储数据的内存是从空间设置器申请的
- ⼀般环境下，使用时不需要传后两个模版参数
- set底层是⽤红⿊树(特殊的二叉搜刮树)实现，增删查效率是O(logN),迭代器走中序遍历，可以保证数据有序
红黑树：
2.2 set的构造和迭代器
//⽆参默认构造
explicit set(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
//迭代器区间构造
template <class InputIterator>
set(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type & = allocator_type());
//拷⻉构造
set(const set& x);
//列表构造
set(initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 迭代器是⼀个双向迭代器
iterator->a bidirectional iterator to const value_type
//正向迭代器
iterator begin();
iterator end();
//反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
set支持正向迭代器和反向迭代器，遍历默认按升序(set默认小于比较) ，支持迭代器就支持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，由于修改数据会破坏底层的数据结构
2.3 set的增删查（不支持改）
增：
pair insert (const value_type& val); // 单个数据插⼊，如果已经存在则插⼊失败
set<int> se; //单个数据插⼊使用示例
se.insert(5);
se.insert(4);
void insert (initializer_list il); // 列表插⼊，已经在容器中存在的值不会插⼊
set<int> se; //列表插⼊使用示例
se.insert({1,2,5});
template<class InputIterator>
void insert (InputIterator first, InputIterator last); //迭代区间插入
vector<int> arr;
arr.push_back(2);
arr.push_back(4);
arr.push_back(1);
set<int> se;
se.insert(arr.begin(), arr.end()); //迭代区间插入使用示例
查：
iterator find (const value_type& val); //查找 val ，返回 val 地点的迭代器，没有找到返回 end()
set<int> se;
se.insert(5);
se.insert(2);
se.insert(1);
auto it = se.find(2); //查找val使用示例
size_type count (const value_type& val) const; //查找 val ，返回 Val 的个数
//对于set而言，数据会去重，返回值是0或1
set<int> se;
se.insert(5);
se.insert(2);
se.insert(1);
size_t n = se.count(2)；
//对于multiset，支持数据冗余，返回值 >=0
multiset<int> mse;
mse.insert(5);
mse.insert(2);
mse.insert(2);
mse.insert(2);
mse.insert(1);
size_t n = mse.count(2);
iterator lower_bound (const value_type& val) const; //返回小于即是 val 位置的迭代器
set<int> se;
se.insert(2);
se.insert(4);
se.insert(6);
se.insert(5);
auto it = se.lower_bound(3);
iterator upper_bound (const value_type& val) const; //返回⼤于 val 位置的迭代器
set<int> se;
se.insert(2);
se.insert(4);
se.insert(6);
se.insert(5);
auto it = se.upper_bound(4);
删：
size_type erase (const value_type& val); //删除 val ，返回删除乐成的个数
对于set来说，不存在数据冗余，只能删除1个或0个，所以erase返回1或0
对于multiset而言，可能存在多个相同数据，所以erase返回值 >=0
set<int> se; //set
se.insert(2);
se.insert(2);
se.insert(4);
se.insert(1);
size_t ret = se.erase(2); //ret = 1
multiset<int> mse; //multiset
mse.insert(2);
mse.insert(2);
mse.insert(2);
mse.insert(4);
size_t ret = mse.erase(2); //ret = 3
iterator erase (const_iterator position); //删除⼀个迭代器位置的值，返回下一个位置的迭代器
当删除set中仅有的一个值之后，返回的迭代器会失效，不可访问
set<int> se;
se.insert(2);
se.insert(4);
se.insert(1);
se.insert(3);
auto it = se.begin();
auto it1 = se.erase(it);
iterator erase (const_iterator first, const_iterator last); //删除⼀段迭代器区间的值
set<int> se;
se.insert(2);
se.insert(4);
se.insert(1);
se.insert(3);
se.erase(se.begin(), se.end()); //删除se中的所有数据
3.1 map
map的声明如下
template < class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key, T> >
> class map;
Key就是map底层关键字的范例，T是map底层value的范例，set默认要求Key支持小于比较，如果不⽀持大概需要的话可以⾃⾏实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间设置器申请的
- map底层是⽤红⿊树实现
- 增删查改效率是 O(logN)
- 迭代器遍历是⾛的中序，所以是按key有序顺序遍历的
3.2 pair范例
map底层的红⿊树节点中的数据，使⽤pair存储键值对数据
typedef pair<const Key, T> value_type;
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)
{}
template<class U, class V>
pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
{}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{
return (pair<T1, T2>(x, y));
}
3.2 map的构造和迭代器
map⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，由于底层是⼆叉搜刮树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜刮树的结构
//无参默认构造
explicit map(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
//迭代器区间构造
template <class InputIterator>
map(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type & = allocator_type());
//拷贝构造
map (const map& x);
//列表构造
map(initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
3.3 map的增删查
map增接⼝，插⼊的pair键值对数据，跟set所有不同，但是查和删的接⼝只⽤关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value
Member types
key_type->The first template parameter(Key)
mapped_type->The second template parameter(T)
value_type->pair<const key_type, mapped_type>
// 单个数据插⼊，如果key已经存在则插⼊失败, key存在相称value不相称也会插⼊失败
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找k，返回k地点的迭代器，没有找到返回end()
iterator find(const key_type& k);
// 查找k，返回k的个数
size_type count(const key_type& k) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除k，k存在返回0，存在返回1
size_type erase(const key_type & k);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等k位置的迭代器
iterator lower_bound(const key_type& k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound(const key_type& k) const;
3.4 map数据的修改
map⽀持修改mapped_type数据，也就是second的值，不⽀持修改key数据，修改关键字数据，破坏了底层搜刮树的结构
map第⼀个⽀持修改的⽅式时通过迭代器，迭代器遍历时大概find返回key地点的iterator修改，map另有⼀个⾮常重要的修改接⼝operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接⼝
需要留意从内部实现⻆度，map这⾥把我们传统说的value值，给的是T范例，typedef为 mapped_type。⽽value_type是红⿊树结点中存储的pair键值对值。
1.查找k，返回k地点的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type值
iterator find(const key_type& k);
2.insert插⼊⼀个pair<key, T>对象
如果key已经在map中，插⼊失败，则返回⼀个pair<iterator, bool>对象，返回pair对象first是key地点结点的迭代器，second是false
如果key不在在map中，插⼊乐成，则返回⼀个pair<iterator, bool>对象，返回pair对象first是新插⼊key地点结点的迭代器，second是true
pair<iterator, bool> insert(const value_type& val);
因此，⽆论insert插⼊乐成还是失败，返回 pair 对象的 first 都会指向 key 地点的迭代器，insert 可以⽤来实现 operator[]
mapped_type& operator[] (const key_type& k);
3.5 multimap和map的差异
multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，由于⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
