IT评测·应用市场-qidao123.com技术社区

标题: map和set [打印本页]

作者: 小秦哥 时间: 4 天前
标题: map和set

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企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)