C++之STL---set及map的基本使用

用户11991900

发布于 2026-01-15 12:04:58

720

一.序列式容器和关联式容器

定义

序列式容器：
- 是一种按照元素插入顺序存储数据的容器。元素存储在连续或逻辑上连续的空间中，通过索引或迭代器可以顺序访问每个元素。
- 常见的序列式容器包括数组、向量（vector）、列表（list）、双端队列（deque）等。
- 元素按照插入顺序依次存储。例如，在 vector 中，元素存储在连续的内存空间中；在 list 中，元素通过指针或引用连接在一起。
- 存储结构相对简单，主要关注元素的顺序和连续性。
关联式容器：
- 是一种基于键值对存储数据的容器。每个元素由键（Key）和值（Value）组成，键是唯一的，通过键可以快速定位到对应的值。
- 常见的关联式容器包括哈希表（unordered_map）、平衡二叉树（map）、集合（set）等。
- 元素存储方式取决于具体的实现。例如：
  - map 和 set 通常基于平衡二叉树（如红黑树）实现，元素按照键的顺序存储。
  - unordered_map 和 unordered_set 基于哈希表实现，元素存储在哈希桶中，通过哈希函数快速定位。
- 存储结构更复杂，但能通过键快速访问元素。

二.set

2.1set基本介绍

set的声明如下，T就是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.2set的构造和迭代器

// empty (1) ⽆参默认构造 

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

// range (2) 迭代器区间构造 

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

// copy (3) 拷⻉构造 

set (const set& x);

// initializer list (5) initializer 列表构造 

set (initializer_list<value_type> il,
 const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());

一、`set` 的构造函数

set 的构造函数有多种重载形式，用于创建不同类型的 set 容器。以下是常见的构造方式：

1. 默认构造

std::set<int> mySet;

创建一个空的 set，默认使用小于操作符（<）对元素进行排序。

2. 指定比较函数

std::set<int, std::greater<int>> mySet; // 使用大于操作符排序

可以通过自定义比较函数来改变元素的排序方式。例如，使用 std::greater 可以让元素按降序排列。

3. 从另一个容器初始化

std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::set<int> mySet(vec.begin(), vec.end());

使用一个范围（如另一个容器的迭代器范围）来初始化 set。重复的元素会被自动去除。

4. 使用初始化列表

std::set<int> mySet = {3, 1, 4, 1, 5, 9};

使用花括号 {} 包裹的初始化列表来创建 set。同样，重复的元素会被自动去除。

5. 拷贝构造和移动构造

std::set<int> original = {1, 2, 3};
std::set<int> copy(original); // 拷贝构造
std::set<int> moved(std::move(original)); // 移动构造

拷贝构造会创建一个与原 set 完全相同的副本。
移动构造会将原 set 的内容移动到新 set 中，原 set 会变成空。

二、`set` 的迭代器

set 的迭代器用于遍历容器中的元素。由于 set 是基于平衡二叉树实现的，迭代器会按照元素的排序顺序访问元素。

// 迭代器是⼀个双向迭代器 
iterator -> a bidirectional iterator to const value_type

// 正向迭代器 
iterator begin();
iterator end();

// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

1. 获取迭代器

begin() 和 end()：分别返回指向第一个元素和最后一个元素之后位置的迭代器。

auto it = mySet.begin(); // 指向第一个元素
auto it_end = mySet.end(); // 指向最后一个元素之后的位置

2. 遍历 `set`

std::set<int> mySet = {1, 2, 3, 4, 5};

// 使用迭代器遍历
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

// 使用范围 for 循环
for (const auto& elem : mySet) {
    std::cout << elem << " ";
}
std::cout << std::endl;

迭代器支持递增操作（++），可以依次访问每个元素。
范围 for 循环是 C++11 引入的简化，语法可以直接遍历容器中的元素。

3. 插入和删除元素

插入元素时，set 会自动保持元素的排序顺序。

mySet.insert(6); // 插入元素 6

删除元素时，可以使用迭代器指定要删除的元素。

auto it = mySet.find(3); // 查找元素 3
if (it != mySet.end()) {
    mySet.erase(it); // 删除元素 3
}

4. 查找元素

使用 find() 方法查找元素，返回指向找到的元素的迭代器，如果未找到则返回 end()。

auto it = mySet.find(4);
if (it != mySet.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Not found!" << std::endl;
}

5.`set` 的迭代器特性

set 的迭代器是双向迭代器，支持双向遍历（即可以递增也可以递减）。

auto it = mySet.begin();
++it; // 移动到下一个元素
--it; // 移动到上一个元素

由于 set 的元素是唯一的，迭代器不会指向重复的元素。

2.3set的增删查

在 C++ 中，std::set 是一种关联式容器，用于存储唯一的元素，并且这些元素会自动按照某种顺序排列（默认是升序）。set 提供了高效的插入、删除和查找操作。以下是关于 set 的增删查操作的详细说明：

一、插入操作

1 . 使用 `insert()` 方法

insert() 是 set 中用于插入元素的主要方法。它会将元素插入到容器中，并确保元素的唯一性。

std::set<int> mySet;

// 插入单个元素
mySet.insert(10);
mySet.insert(20);
mySet.insert(30);

// 插入重复元素（不会插入）
mySet.insert(10); // 10 已经存在，插入失败

如果元素已经存在于 set 中，insert() 方法不会插入该元素，并且不会改变容器的内容。
insert() 方法返回一个 pair，其中 first 是指向插入元素（或已存在元素）的迭代器，second 是一个布尔值，表示插入是否成功。

auto result = mySet.insert(40);
if (result.second) {
    std::cout << "Element inserted successfully!" << std::endl;
} else {
    std::cout << "Element already exists!" << std::endl;
}

2. 插入范围

set 还支持从另一个容器（或范围）插入多个元素。

std::vector<int> vec = {50, 60, 70};
mySet.insert(vec.begin(), vec.end()); // 插入整个范围

二、删除操作

1. 使用 `erase()` 方法

erase() 方法用于删除 set 中的元素。可以通过以下几种方式调用 erase()：

通过值删除：

mySet.erase(20); // 删除值为 20 的元素

通过迭代器删除：

auto it = mySet.find(30); // 查找值为 30 的元素
if (it != mySet.end()) {
    mySet.erase(it); // 删除迭代器指向的元素
}

通过范围删除：

auto start = mySet.lower_bound(40); // 找到第一个大于等于 04 的元素
auto end = mySet.upper_bound(60);   // 找到第一个大于 60 的元素
mySet.erase(start, end);            // 删除 [start, end) 范围内的元素

三、查找操作

1. 使用 `find()` 方法

find() 方法用于查找 set 中是否存在某个元素。如果找到，返回指向该元素的迭代器；否则返回 end()。

auto it = mySet.find(50);
if (it != mySet.end()) {
    std::cout << "Element found: " << *it << std::endl;
} else {
    std::cout << "Element not found!" << std::endl;
}

2. 使用 `count()` 方法

count() 方法用于统计某个元素在 set 中出现的次数。由于 set 中的元素是唯一的，count() 的返回值只能是 0 或 1。

if (mySet.count(60) > 0) {
    std::cout << "Element exists!" << std::endl;
} else {
    std::cout << "Element does not exist!" << std::endl;
}

3. 使用 `lower_bound()` 和 `upper_bound()` 方法

lower_bound() 返回指向第一个大于或等于给定值的元素的迭代器。
upper_bound() 返回指向第一个大于给定值的元素的迭代器。

auto lower = mySet.lower_bound(40); // 指向第一个 >= 40 的元素
auto upper = mySet.upper_bound(60); // 指向第一个 > 60 的元素

std::cout << "Elements in range [40, 60):" << std::endl;
for (auto it = lower; it != upper; ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

2.4multiset和set的差异

C++中`multiset`和`set`的差异

std::multiset和std::set都是C++标准库中的关联容器，它们都基于红黑树（自平衡二叉搜索树）实现，具有自动排序的特性。然而，它们之间存在一个关键区别：是否允许重复元素。

核心差异

特性	std::set	std::multiset
元素唯一性	不允许重复元素	允许重复元素
插入操作	若元素已存在，则插入失败	总是插入成功，即使元素已存在
count()方法	返回0或1	返回实际出现次数
erase()方法	删除单个元素	默认删除所有匹配元素（可通过迭代器删除单个实例）
适用场景	需要唯一性的集合（如去重）	需要统计元素频率或保留重复值的集合

三.map

3.1map类的介绍

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实现，增删查改效率O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的。

template < class Key, // map::key_type

		 class T, // map::mapped_type

		 class Compare = less<Key>, // map::key_compare

		 class Alloc = allocator<pair<const Key,T> > 
//map::allocator_type

		 > class map;

3.2pair类型介绍

std::pair 是 C++ 标准库中的一个简单模板类，用于将两个不同类型的值组合成一个单一单元。它是一种轻量级的数据结构，广泛应用于各种场景，特别是在需要返回多个值或存储键值对时。

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.3map的构造

map的⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) ⽆参默认构造 

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

// range (2) 迭代器区间构造 

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

// copy (3) 拷⻉构造 

map (const map& x);

// initializer list (5) initializer 列表构造 

map (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();

`std::map` 的构造函数

std::map 提供了多种构造方式，以满足不同的需求。以下是常见的构造方法：

1. 默认构造

std::map<int, std::string> myMap;

创建一个空的 std::map，键的类型为 int，值的类型为 std::string。
默认情况下，键会按照升序排列。

2. 指定比较函数

std::map<int, std::string, std::greater<int>> myMap;

可以通过自定义比较函数来改变键的排序方式。例如，使用 std::greater<int> 可以让键按降序排列。

3. 从另一个容器初始化

std::vector<std::pair<int, std::string>> vec = {{1, "one"}, {2, "two"}, {3, "three"}};
std::map<int, std::string> myMap(vec.begin(), vec.end());

使用一个范围（如另一个容器的迭代器范围）来初始化 std::map。容器中的元素必须是 std::pair 类型，其中 first 是键，second 是值。

4. 使用初始化列表

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

使用花括号 {} 包裹的初始化列表来创建 std::map。每个元素是一个 std::pair，其中 first 是键，second 是值。

5. 拷贝构造和移动构造

std::map<int, std::string> original = {{1, "one"}, {2, "two"}};
std::map<int, std::string> copy(original); // 拷贝构造
std::map<int,:: stdstring> moved(std::move(original)); // 移动构造

拷贝构造：创建一个与原 std::map 完全相同的副本。
移动构造：将原 std::map 的内容移动到新 std::map 中，原 std::map 会变成空。

3.4map的增删查

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;

一、插入操作

1. 使用 `operator[]` 插入

operator[] 是一种简单且常用的插入方式。它会根据键值自动插入或更新元素。

std::map<int, std::string> myMap;

myMap[1] = "one";   // 插入键为 1，值为 "one" 的元素
myMap[2] = "two";   // 插入键为 2，值为 "two" 的元素
myMap[3] = "three"; // 插入键为 3，值为 "three" 的元素

如果键已存在，则会更新对应的值。
如果键不存在，则会插入一个新的键值对。

2. 使用 `insert()` 方法插入

insert() 是另一种插入方法，它提供了更多的灵活性，例如插入多个键值对或避免重复插入。

std::map<int, std::string> myMap;

// 插入单个键值对
myMap.insert(std::make_pair(1, "one"));
myMap.insert(std::make_pair(2, "two"));

// 插入初始化列表
myMap.insert({{3, "three"}, {4, "four"}});

// 插入范围
std::vector<std::pair<int, std::string>> vec = {{5, "five"}, {6, "six"}};
myMap.insert(vec.begin(), vec.end());

insert() 方法返回一个 pair，其中 first 是指向插入元素的迭代器，second 是一个布尔值，表示是否成功插入（如果键已存在，则返回 false）。

// insert插⼊⼀个pair<key, T>对象 

// 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false 

// 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象first是新插⼊key所在结点的迭代器，second是true 

// 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器 

// 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现

二、删除操作

1. 使用 `erase()` 方法删除

erase() 方法用于删除 std::map 中的元素，可以通过键、迭代器或范围来删除。

通过键删除：

myMap.erase(2); // 删除键为 2 的元素

通过迭代器删除：

auto it = myMap.find(3); // 查找键为 3 的元素
if (it != myMap.end()) {
    myMap.erase(it); // 删除迭代器指向的元素
}

通过范围删除：

auto start = myMap.lower_bound(3); // 找到第一个键 >= 3 的元素
auto end = myMap.upper_bound(5);   // 找到第一个键 > 5 的元素
myMap.erase(start, end);           // 删除 [start, end) 范围内的元素

三、查找操作

1. 使用 `find()` 方法查找

find() 方法用于查找 std::map 中是否存在某个键。如果找到，返回指向该键值对的迭代器；否则返回 end()。

auto it = myMap.find(3);
if (it != myMap.end()) {
    std::cout << "Key 3 found with value: " << it->second << std::endl;
} else {
    std::cout << "Key 3 not found!" << std::endl;
}

2. 使用 `count()` 方法

count() 方法用于统计某个键在 std::map 中出现的次数。由于 std::map 中的键是唯一的，count() 的返回值只能是 0 或 1。

if (myMap.count(4) > 0) {
    std::cout << "Key 4 exists!" << std::endl;
} else {
    std::cout << "Key 4 does not exist!" << std::endl;
}

3. 使用 `lower_bound()` 和 `upper_bound()` 方法

lower_bound() 返回指向第一个键大于或等于给定值的元素的迭代器。
upper_bound() 返回指向第一个键大于给定值的元素的迭代器。

auto lower = myMap.lower_bound(3); // 指向第一个键 >= 3 的元素
auto upper = myMap.upper_bound(5); // 指向第一个键 > 5 的元素

std::cout << "Elements in range [3, 5):" << std::endl;
for (auto it = lower; it != upper; ++it) {
    std::cout << it->first << " -> " << it->second << std::endl;
}

3.5map的数据修改

前⾯我提到map⽀持修改mapped_type数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构。map第⼀个⽀持修改的⽅式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有⼀个⾮常重要的修改接口operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接⼝需要注意从内部实现⻆度，map这⾥把我们传统说的value值，给的是T类型，typedef为mapped_type。⽽value_type是红⿊树结点中存储的pair键值对值。⽇常使⽤我们还是习惯将这⾥的T映射值叫做value。

一、`operator[]` 的工作原理

operator[] 是 std::map 提供的一个成员函数，用于通过键访问对应的值。它的行为如下：

如果键 已存在，operator[] 返回对键对应值的引用，可以直接通过这个引用修改值。
如果键 不存在，operator[] 会自动插入一个键值对，其中键是给定的键，值是值类型的默认构造值（例如，对于 std::string，默认值是空字符串；对于 int，默认值是 0），然后返回对这个新值的引用。

二、使用 `operator[]` 修改值

1. 修改已存在的键对应的值

假设 std::map 中已经存在某个键，可以通过 operator[] 直接修改它的值。

2. 插入新的键值对

如果键不存在，operator[] 会自动插入一个新的键值对，并返回对新值的引用。这可以用来初始化新键的值。

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type值 
iterator find (const key_type& k);

operator[]
// 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另⼀个是insert返回值pair<iterator,bool> 

pair<iterator,bool> insert (const value_type& val);
mapped_type& operator[] (const key_type& k);

// operator的内部实现 
mapped_type& operator[] (const key_type& k)
{
 pair<iterator, bool> ret = insert({ k, mapped_type() });
 iterator it = ret.first;
 return it->second;
}
// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能 
 // 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能

3.6multimap和map的差异

std::multimap和std::map都是C++标准库中的关联容器，它们都基于红黑树（自平衡二叉搜索树）实现，具有自动排序的特性。然而，它们之间存在一个关键区别：是否允许键重复。

核心差异

特性	std::map	std::multimap
键的唯一性	不允许重复键	允许重复键
插入操作	若键已存在，则插入失败	总是插入成功，即使键已存在
[]运算符	支持通过键直接访问值	不支持（因为一个键可能对应多个值）
count()方法	返回0或1	返回键的实际出现次数
find()方法	返回匹配键的单个元素的迭代器	返回匹配键的第一个元素的迭代器
equal_range()方法	通常不需要（因为键唯一）	返回包含所有匹配键的元素范围
适用场景	需要唯一键的映射关系	需要一对多映射关系或保留重复键的映射

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-06-26，如有侵权请联系 cloudcommunity@tencent.com 删除

map

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！