C++进阶:详细讲解容器set与map(pair、multiset、multimap)

是Nero哦 2024-09-11 10:05:09 阅读 86

C++进阶:详细讲解容器set与map(pair、multiset、multimap)

上次介绍了搜索二叉树:C++进阶:二叉搜索树介绍、模拟实现(递归迭代两版本)及其应用

为了介绍后面的AVLTree和红黑树,我们要进行一些铺垫,就是set与map的介绍啦


文章目录

1.关联式容器与序列式容器2.C++中的键值对——`pair`2.1pair定义2.2pair的对象创建与访问2.3make_pair() 函数和使用`{}` -简化创建过程

3. set容器3.1Constructs构造函数3.2Iterator 迭代器3.3 插入、删除、查找、count3.3.1 insert()插入3.3.2 erase() 删除3.3.3 find()查找3.3.4 count()函数

4.容器 multiset5.map 容器5.1map 模板参数说明5.2 对象的创建5.3 迭代器,insert,find ,`[]`重载5.3.1 迭代器5.3.2 insert() 函数5.3.3 find() 函数5.3.4 `[]`

6.容器 multimap


1.关联式容器与序列式容器

关联式容器和序列式容器是 C++ 中两种不同的容器类型

关联式容器:

关联式容器主要包括 <code>std::set, std::map, std::multiset, std::multimap 等。这些容器是基于键值对(<key, value>结构)的概念,通过键==(key)来唯一标识元素==。关联式容器内部使用二叉搜索树(通常是红黑树)或类似的数据结构,以保持元素的有序性。插入、删除、查找等操作的平均时间复杂度是 O(log n)。

序列式容器:

序列式容器包括 std::vector, std::list, std::deque, std::array 等。这些容器是基于线性结构的,元素在容器中的位置是由插入的顺序决定的。插入、删除、查找等操作的平均时间复杂度因容器类型而异,但在最差情况下,可能达到 O(n)。


2.C++中的键值对——pair

在C++中,键值对是一种数据结构,通常用于表示关联关系

键值对由两部分组成:键(Key)和值(Value)。这种结构允许通过键来检索和关联对应的值,key代表键值,value表示与key对应的信息

2.1pair定义

std::pair 是C++标准库中提供的一个简单的键值对实现。它包含在 <utility> 头文件中。一个 std::pair 有两个公有成员:firstsecond,分别表示键和值==(first<= =>key ; second<= =>value)==

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)

{}

};

2.2pair的对象创建与访问

文档中的构造函数的介绍:

sm1

默认构造函数:

<code>pair();默认构造函数创建一个空的 std::pair 对象,不包含任何值。

拷贝构造函数:

template<class U, class V> pair (const pair<U,V>& pr);拷贝构造函数用于从另一个 std::pair 对象 pr 中复制键值对来构造一个新的 std::pair 对象。

初始化构造函数:

pair (const first_type& a, const second_type& b);初始化构造函数接受两个参数 ab,分别用于初始化 std::pair 对象的 firstsecond 成员变量。

void test_pair()

{

pair<int, char> p1;//空参

pair<int, char> p2(2, '2');

pair<int, char> p3(p2);//拷贝构造

cout << p1.first << " " << p1.second << endl;;

cout << p2.first << " " << p2.second << endl;

cout << p3.first << " " << p3.second << endl;

}

int main()

{

test_pair();

return 0;

}

sm2

2.3make_pair() 函数和使用<code>{} -简化创建过程

sm3

<code>void test_pair2()

{

auto p4 = make_pair(2, 'c');//使用make_pair

pair<int, char> p5 = { 3,'d' };//c++11后,使用{ }

cout << p4.first << " " << p4.second << endl;

cout << p5.first << " " << p5.second << endl;

}

int main()

{

test_pair2();

return 0;

}

我们能使用{}(初始化列表),是因为:构造函数匹配。如果使用花括号进行初始化,编译器会尝试匹配合适的构造函数。对于 pair,存在接受两个参数的构造函数,因此可以通过初始化列表直接构造键值对

sm4


3. set容器

sm5

set是按照一定次序存储元素的容器

在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。

在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代。

set在底层是用二叉搜索树(红黑树)实现

3.1Constructs构造函数

sm6

<code>void test_set1()

{

set<int> s1;

vector<int> v = { 1,2,3,4,5 };

set<int> s2(v.begin(), v.end());//利用迭代区间

set<int> s3 = s2;//拷贝构造

for (auto e : s1)

{

cout << e << " ";

}

cout << endl;

for (auto e : s2)

{

cout << e << " ";

}

cout << endl;

for (auto e : s3)

{

cout << e << " ";

}

cout << endl;

}

int main()

{

test_set1();

return 0;

}

3.2Iterator 迭代器

函数声明 功能
iterator begin(); 返回指向set开头的迭代器
iterator end(); 返回指向set最后一个元素后面的迭代器
const_iterator cbegin() const; 返回指向set开头的const迭代器
const_iterator cend() const; 返回指向set最后一个元素后面的const迭代器
reverse_iterator rbegin(); 返回指向set最后一个元素的反向迭代器
reverse_iterator rend(); 返回指向set第一个元素前面的反向迭代器
const_reverse_iterator crbegin() const; 返回指向set最后一个元素的反向const迭代器
const_reverse_iterator crend() const; 返回指向set第一个元素前面的反向const迭代器

3.3 插入、删除、查找、count

3.3.1 insert()插入

声明:pair<iterator, bool> insert(const value_type& val);

插入元素到 set 中。如果插入成功,返回一个迭代器指向插入的位置和 true。如果元素已经存在,返回一个迭代器指向已存在的元素和 false

返回一个 pair 对象,包含插入的迭代器和插入是否成功的标志。

3.3.2 erase() 删除

sm7

函数声明 功能介绍 返回值
<code>iterator erase(iterator position); 删除指定位置的元素,并返回指向被删除元素之后元素的迭代器。 指向被删除元素之后元素的迭代器。
size_type erase(const key_type& k); 删除 set 中所有等于指定键值的元素。返回删除的元素个数。 删除的元素个数。
iterator erase(iterator first, iterator last); 删除区间 [first, last) 中的所有元素,并返回最后一个被删除元素之后的迭代器。 指向被删除元素之后元素的迭代器。

3.3.3 find()查找

sm8

<code>find 函数用于在 set 中查找指定键值的元素,并返回指向该元素的迭代器。如果元素不存在,则返回 end()

3.3.4 count()函数

声明:size_type count (const key_type& k) const;

count 函数用于统计 set 中与指定键值相等的元素个数。由于 set 中元素的键值是唯一的,因此该函数的返回值要么是 0(元素不存在),要么是 1(元素存在)

void test_set2()

{

// 排序+去重

set<int> s;

s.insert(5);

s.insert(1);

s.insert(6);

s.insert(3);

s.insert(5);

s.insert(1);

for (auto e : s)

{

cout << e << " ";

}

cout << endl;

set<int>::iterator pos = s.find(5);//找到5就删除

if (pos != s.end())

{

cout << "找到了" << endl;

s.erase(pos);

}

for (auto e : s)

{

cout << e << " ";

}

cout << endl;

if (s.count(1))

{

cout << "1在" << endl;

}

else

{

cout << "1不在" << endl;

}

}

int main()

{

test_set2();

return 0;

}

sm9


4.容器 multiset

sm10

multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。

在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的),但可以从容器中插入或删除。

在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。

multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭代器遍历时会得到一个有序序列。

multiset底层结构为二叉搜索树(红黑树)

注意:

multiset中再底层中存储的是<value, value>的键值对

mtltiset的插入接口中只需要插入即可

与set的区别是,multiset中的元素可以重复,set是中value是唯一的

使用迭代器对multiset中的元素进行遍历,可以得到有序的序列

multiset中的元素不能修改

在multiset中找某个元素,时间复杂度为

O

(

l

o

g

2

N

)

O(log_2 N)

O(log2​N)

multiset的作用:可以对元素进行排序

<code>multiset 是 C++ 标准库中的关联式容器之一,属于有序容器。与 set 不同的是,multiset 允许键值重复,即可以包含相同键值的多个元素

允许重复键值: multiset 允许容器中存在相同的键值,因此可以包含多个相同键值的元素。

有序性: 与 set 类似,multiset 也维护元素的有序性,根据键值进行排序。

当需要允许键值重复,并且希望保持元素有序时,可以选择使用 multiset


5.map 容器

sm11

map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素

在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:

在内部,map中的元素总是按照键值key进行比较排序的。

map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。

map支持下标访问符,即在<code>[]中放入key,就可以找到与key对应的value。

map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。

5.1map 模板参数说明

key: 键值对中key的类型

T: 键值对中value的类型

Compare: 比较器的类型,map中的元素按照key来比较的,缺省情况下按照小于来比较,一般情况下(内置类型元素)该参数不需要传递,如果无法比较时(自定义类型),需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc:通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器

5.2 对象的创建

sm12

<code>void testmap1()

{

map<string, string> m1;//空的

map<string, string> m2(m1);//拷贝构造

}

5.3 迭代器,insert,find ,[]重载

5.3.1 迭代器

下面是关于 multiset 中成员函数 begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), 和 crend() 的函数声明和功能介绍:

函数声明 功能介绍
iterator begin(); 返回 multiset 中首元素的位置的迭代器。
iterator end(); 返回 multiset 中最后一个元素后面的位置的迭代器。
const_iterator cbegin() const; 返回 multiset 中首元素的位置的 const 迭代器,不能修改所指向的元素。
const_iterator cend() const; 返回 multiset 中最后一个元素后面的位置的 const 迭代器,不能修改所指向的元素。
reverse_iterator rbegin(); 返回指向 multiset 中第一个元素的反向迭代器,即 end()
reverse_iterator rend(); 返回指向 multiset 中最后一个元素下一个位置的反向迭代器,即 rbegin()
const_reverse_iterator crbegin() const; 返回指向 multiset 中第一个元素的反向 const 迭代器,不能修改所指向的元素。
const_reverse_iterator crend() const; 返回指向 multiset 中最后一个元素下一个位置的反向 const 迭代器,不能修改所指向的元素。

5.3.2 insert() 函数

sm13

<code>void testmap2()

{

map<string, string> m1;//空的

m1.insert(pair<string, string>("sort", "排序"));//匿名对象

m1.insert(make_pair("apple", "苹果"));//使用make_pair函数

m1.insert({ "apple", "苹果" });// C++11 多参数隐式类型转换(构造函数支持)

}

5.3.3 find() 函数

sm14

在 <code>map 中,find 函数用于查找指定键的元素,并返回指向该元素的迭代器。如果找到了指定的键,则返回指向该键值对的迭代器;如果未找到,则返回指向 map 末尾的迭代器。

函数声明 功能介绍
iterator find(const key_type& k); 查找键值为 k 的元素,并返回一个指向该元素的迭代器。如果 k 存在于 map 中,则返回指向该元素的迭代器;如果不存在,则返回指向 map 末尾的迭代器。
const_iterator find(const key_type& k) const; 在常量 map 中查找键值为 k 的元素,并返回一个指向该元素的迭代器。如果 k 存在于 map 中,则返回指向该元素的迭代器;如果不存在,则返回指向 map 末尾的迭代器。

5.3.4 []

sm15

读取元素:当使用 <code>[] 运算符时

如果指定的键存在于 map 中,则返回与该键关联的值如果不存在,则会插入一个新的键值对,键为指定的键,值为默认构造的对应值类型的默认值,并返回该默认值的引用

插入元素:当使用 [] 运算符向 map 中插入元素时

如果指定的键不存在,则会创建一个新的键值对,键为指定的键,值为指定的值,并返回该值的引用如果键已经存在,则直接返回对应的值的引用

void testmap3()

{

map<string, string> m1;//空的

m1.insert(pair<string, string>("sort", "排序"));//匿名对象

m1.insert(make_pair("apple", "苹果"));//使用make_pair函数

m1.insert({ "left", "左边" });// C++11 多参数隐式类型转换(构造函数支持)

for (auto& kv : m1)

{

cout << kv.first << ":" << kv.second << " ";

}

cout << endl;

m1["right"];//这是插入一个right(key)

m1["apple"] = "青苹果";//这里是进行修改

for (auto& kv : m1)

{

cout << kv.first << ":" << kv.second << " ";

}

cout << endl;

}

int main()

{

testmap3();

return 0;

}

sm16


6.容器 multimap

sm17

multiset是按照特定顺序存储元素的容器,其中元素是可以重复的

在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的),但可以从容器中插入或删除。

在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。

multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭代器遍历时会得到一个有序序列。

multiset底层结构为二叉搜索树(红黑树)

注意

multiset中再底层中存储的是<value, value>的键值对

mtltiset的插入接口中只需要插入即可

与set的区别是,multiset中的元素可以重复,set是中value是唯一的

使用迭代器对multiset中的元素进行遍历,可以得到有序的序列

multiset中的元素不能修改

在multiset中找某个元素,时间复杂度为

O

(

l

o

g

2

N

)

O(log_2 N)

O(log2​N)

multiset的作用:可以对元素进行排序


这次就到这里啦!!!感谢大家支持!!!



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。