【STL详解 —— map和set的使用】

🕗 发布于 2024-07-21 15:47 c++ 网络 开发语言

关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、
forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

那什么是关联式容器？它与序列式容器有什么区别？

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

一般的序列式容器有：

容器名	特性
vector	动态数组，能够高效地进行随机访问。扩展数组大小时可能需要重新分配内存。
deque	双端队列，支持在两端快速插入和删除元素。
list	双向链表，适合频繁的插入和删除操作，但是不支持随机访问

一般的序列是容器有：

容器名	特性
set	存储唯一的元素，自动排序，使用红黑树实现。
map	存储键值对，键是唯一的，自动排序，使用红黑树实现。
multiset	允许存储重复元素，自动排序，使用红黑树实现。
multimap	存储键值对，键和值都可以重复，自动排序，使用红黑树实现。

此为，C++11还引入了无序关联式容器

容器名	特性
unordered_set	存储唯一的元素，不保证顺序，使用哈希表实现。
unordered_multiset	允许存储重复元素，不保证顺序，使用哈希表实现。
unordered_map	存储键值对，键是唯一的，不保证顺序，使用哈希表实现。
unordered_multimap	存储键值对，键和值都可以重复，不保证顺序，使用哈希表实现。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

比如：在中英字典中，每一个单词有其对应的翻译，其是一一对应的，此时key即为单词，value为单词对应的翻译。

在SGI-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)
    {}
};

这里的pair是一个模板结构，需要两个类型参数，T1和T2，通过typedef来定义两个别名，并通过T1，T2来定义成员变量first second 。带参的构造函数使在创建pair对象的时候直接赋值。

set

set的介绍

set是按照一定次序存储元素的容器。
默认情况下，std::set 使用 std::less 作为比较函数，这意味着它会使用小于运算符（<）来比较元素。用户可以提供自己的比较函数对象，以自定义排序方式。
set在底层是用二叉搜索树(红黑树)实现的。
与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
set在底层是用平衡搜索树（红黑树）实现的，所以在set当中查找某个元素的时间复杂度为 $log_{} n$

set的使用

set的模板参数列表

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>

> class set;

Key：描述：表示 set 中存储的元素类型。示例：如果你想存储整数，可以使用
set <int>；如果你想存储字符串，可以使用set <string>

Compare（默认为 std::less）：
描述：一个函数对象，用于元素的排序准则。默认情况下，使用 std::less<Key> 进行排序，即按升序排序

Allocator（默认为 std::allocator<Key>）:
描述：定义了分配器，用于管理 set 中元素的内存分配。默认情况下，使用标准的 std::allocator<Key>。

set的构造

构造1：

explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

空容器构造函数 也是默认构造函数，构造一个空容器，没有任何元素。

构造2：

template <class InputIterator>
  set (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());

范围构造函数：构造一个容器，包含从[first，last)范围内的元素，每个元素都是从该范围中的对应元素构造的。

构造3

set (const set& x);

拷贝构造函数：构造一个容器，包含x中每个元素的拷贝。

容器内部保留了 alloc 和 comp 的副本，这些副本用于在其生命周期内分配存储和排序元素。拷贝构造函数（3）创建一个容器，并保留和使用 x 的分配器和比较对象的副本。元素的存储空间是使用这个内部分配器分配的。

set的迭代器

函数说明	功能介绍
iterator begin()	返回set中起始位置元素的选代器
iterator end()	返回set中最后一个元素后面的送代器
const_iterator cbegin() const	返回set中起始位置元素的const迭代器
const_iterator cend() const	返回set中最后一个元素后面的const送代器
reverse_iterator rbegin()	返回set第一个元素的反向迭代器，即end
reverse_iterator rend()	返回set最后一个元素下一个位置的反向选代器，即rbegin
const_reverse_iterator crbegin() const	crbegin() const返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const	返回set最后一个元素下一个位置的反向const迭代器，即crbegin

#include <iostream>
#include <set>
int main()
{
int myints[] = { 75,23,65,42,13 };
std::set<int> myset(myints, myints + 5);

std::cout << "myset contains:";
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
std::cout << ' ' << *it;

std::cout << '\n';

return 0;
}

set的容量

empty()

bool empty() const;

检测set中的元素是否为空，空返回true，否则false.

// set::empty
#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;

  myset.insert(20);
  myset.insert(30);
  myset.insert(10);

  std::cout << "myset contains:";
  while (!myset.empty())
  {
     std::cout << ' ' << *myset.begin();
     myset.erase(myset.begin());
  }
  std::cout << '\n';

  return 0;
}


//myset contains: 10 20 30

size()

返回set中有效元素的个数

// set::size
#include <iostream>
#include <set>

int main ()
{
  std::set<int> myints;
  std::cout << "0. size: " << myints.size() << '\n';

  for (int i=0; i<10; ++i) myints.insert(i);
  std::cout << "1. size: " << myints.size() << '\n';

  myints.insert (100);
  std::cout << "2. size: " << myints.size() << '\n';

  myints.erase(5);
  std::cout << "3. size: " << myints.size() << '\n';

  return 0;
}

//0. size: 0
//1. size: 10
//2. size: 11
//3. size: 10

set的修改操作

1.insert

pair<iterator,bool> insert const value_type& x)

在set中插入元素x，实际插入的是<x，x>构成的键值对，如果插入成功，返回
<该元素在set中的位置，true>。如果插入失败，说明x在set中已经存在，返回 <x在set中的位置，false>

2.erase

1. void erase (iterator position)
2. size_type erase ( constkey_type& x)
3. void erase ( iterator first,iterator last )

1. 删除set中position位置上的元素
2. 删除set中值为x的元素，返回删除的元素的个数
3. 删除set中[first，last)区间中的元素

// erasing from set
#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;

  // insert some values:
  for (int i=1; i<10; i++) myset.insert(i*10);  
  // 10 20 30 40 50 60 70 80 90

  it = myset.begin();
  ++it;                        // "it" points now to 20

  myset.erase (it);

  myset.erase (40);

  it = myset.find (60);
  myset.erase (it, myset.end());

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
  std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

//myset contains: 10 30 50

3.swap()

void swap (set<Key,Compare,Allocator>&st);

交换set中的元素

4.clear()

void clear ()

将set中的元素清空

5.find()

iterator find (constkey_type& x) const

返回set中值为x的元素的位置

// set::find
#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;

  // set some initial values:
  for (int i=1; i<=5; i++) myset.insert(i*10);    
  // set: 10 20 30 40 50

  it=myset.find(20);
  myset.erase (it);
  myset.erase (myset.find(40));

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

//myset contains: 10 30 50

6.count()

size_type count ( constkey_type& x) const*

返回set中值为x的元素的个数


#include <set>
void TestSet()
{
// 用数组array中的元素构造set
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
set<int> s(array, array + sizeof(array) / sizeof(array[0]));
cout << s.size() << endl;
// 正向打印set中的元素，从打印结果中可以看出：set可去重
for (auto& e : s)
cout << e << " ";
cout << endl;
// 使用迭代器逆向打印set中的元素
for (auto it = s.rbegin(); it != s.rend(); ++it)
cout << *it << " ";
cout << endl;
// set中值为3的元素出现了几次
cout << s.count(3) << endl;
}

map

map的介绍

map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair typedef pair<const key, T> value_type;
map中通过键值访问单个元素的速度通常比unordered_map容器慢.
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

map的使用

map的模板参数列表

在这里插入图片描述

key: 键值对中key的类型
T：键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

map的构造

explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

空容器构造函数（默认构造函数） 构造一个空的map对象，没有元素。

template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());

范围构造函数
构造一个容器，包含从范围 [first, last) 中的所有元素，每个元素由该范围中对应的元素构造

map (const map& x);

拷贝构造函数
构造一个容器，其中包含 x 中每个元素的副本。

map的迭代器

函数声明	功能介绍
begin()和end()	begin：首元素的位置，end最后一个元素的下一个位置
cbegin(和cend()	与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin()和rend()	反向选代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反
crbegin(和crend()	与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改

map的容量与元素访问

1.empty（）

bool empty () const

检测map中的元素是否为空，是返回true，否则返回false

// map::empty
#include <iostream>
#include <map>

int main ()
{
  std::map<char,int> mymap;

  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;

  while (!mymap.empty())
  {
    std::cout << mymap.begin()->first << " => " << mymap.begin()->second << '\n';
    mymap.erase(mymap.begin());
  }

  return 0;
}

//a => 10
//b => 20
//c => 30

2.size()

size_type size() const

返回map中有效元素的个数

// map::size
#include <iostream>
#include <map>

int main ()
{
  std::map<char,int> mymap;
  mymap['a']=101;
  mymap['b']=202;
  mymap['c']=302;

  std::cout << "mymap.size() is " << mymap.size() << '\n';

  return 0;
}

//mymap.size() is 3

3.operator []

mapped _type& operator[] (constkey_type& k)

返回去key对应的value

map中元素的修改

函数声明	功能简介
pair<iterator,bool> insert (const value_type& x)	在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功
void erase (iterator position )	删除position位置上的元素
size_type erase ( const key_type& x)	删除键值为x的元素
void erase ( iterator first,iterator last )	删除[first,last)区间中的元素
void swap (map<Key,T,Compare,Allocator>&mp)	交换两个map中的元素
void clear ()	将map中的元素清空
iterator find ( const key_type& x）	在map中插入key为x的元素，找到返回该元素的位置的迭代器，否则返回end
const_iterator find ( const key_type& x) const	在map中插入key为x的元素，找到返回该元素的位置的const选代器，否则返回cend
size_type count ( const key_type& x) const	返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

multiset

在这里插入图片描述
总结来说，set 适用于需要唯一元素的情况，而 multiset 则适用于需要存储多个相同元素的情况。

multimap

在这里插入图片描述
总结来说，map 适用于需要唯一键值对的情况，而 multimap 则适用于需要存储多个相同键的情况。

原文地址：https://blog.csdn.net/jokr_/article/details/140501121

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Linux源码安装的Redis如何配置systemd管理并设置开机启动
下一篇：降雨量预测 | Matlab基于ARIMA-RBF降雨量预测

算数基本定理@质因数分解原理
把自然数写成素数的乘积，结论就是著名的算术基本定理。此定理建立了自然数与素数之间的一个重要的关系式。算数基本定理是整除理论性质和结论的精华,是整个初等数论的基础证明一些方程是否有整数解能够从公式的角度
阅读更多2024-11-15
用 Python 从零开始创建神经网络（六）：优化（Optimization）介绍
在随机初始化的模型中，或者即使是采用更复杂方法初始化的模型中，我们的目标是随着时间的推移培训或教育一个模型。为了训练一个模型，我们调整权重和偏差以提高模型的准确性和置信度。为此，我们需要计算模型的错误
阅读更多2024-11-15
海思3403对RTSP进行目标检测
用ss928 实现rtsp流的目标检测
阅读更多2024-11-15
亮数据——助力全球数据抓取的高效代理平台
特别是在需要跨境数据采集的场景中，亮数据的全球代理池能够让用户根据目标网站的地域需求，选择不同地区的IP地址，以此提升数据抓取的稳定性和成功率。亮数据不仅提供了丰富的IP资源，还内置了智能管理系统，可
阅读更多2024-11-15
【卡尔曼滤波】递归算法Recursive的应用 C语言、Python实现（Kalman Filter）
【卡尔曼滤波】递归算法Recursive的应用 C语言、Python实现（Kalman Filter）
阅读更多2024-11-15
记一次工作中订单幂等处理方案
当然可以考虑在数据库新增一张表，这张表上有第三方订单号的字段，并为此字段建立唯一索引，每次下单前预先往这张表插入数据，如果此第三方订单号已存在，那么插入数据必然报错。第一次是通过分布式锁检测，这是在
阅读更多2024-11-15
大数据湖项目建设方案（100页WORD）
随着信息技术的飞速发展，数据量呈现出爆炸性增长的趋势。企业、政府机构及科研单位在运营过程中积累了大量的数据资源，这些数据中蕴含着巨大的价值，但如何高效地存储、处理和分析这些数据，成为了一个亟待解决的问
阅读更多2024-11-15
深度学习笔记14-卷积神经网络2
卷积神经网络，是包含卷积运算且具有深度结构的前馈神经网络。在卷积神经网络中，包含卷积层、池化层和全连接层三种重要的结构。相比前馈神经网络，卷积层和池化层是新增的网络结构，在提取特征时，卷积神经网络使用
阅读更多2024-11-15
[Mysql基础] 表的操作
1.1 语法说明：field表示列名datatype表示列的类型字符集，如果没有指定字符集，则以所在数据库的字符集为准collate校验规则，如果没有指定校验规则，则以所在数据库的校验规则为准。
阅读更多2024-11-15
Mysql-DDL语句
Mysql DDL语句的使用方法和配置命令，可以更加快速熟悉的掌握Mysql基本操作命令
阅读更多2024-11-15