没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全STL关联容器概述1

STL关联容器概述1

ribbon

需积分: 0 0 下载量 132 浏览量 2022-08-08 22:42:10 上传评论收藏 323KB DOCX 举报

温馨提示

试读

57页

STL关联容器概述1

资源详情

资源评论

资源推荐

STL 关联容器概述

2011 年 07 月 09 日 16:00:11 yfk 阅读数 6647

本声明。

本文链接：https://blog.csdn.net/yfkiss/article/details/6594859

1. 概念

STL 容器大的方向分为两类，序列式容器和关联式容器，这两者通过数据在容器内的排

列来区分，关联容器是通过键(key)存储和读取元素的，而顺序容器则通过元素在容器

中的位置顺序存储和访问元素。

标准的 STL 序列容器包括：vector、list、deque、heap（算法呈现）、stack(适配

器)、queue（适配器）、priority_queue(适配器)。标准的 STL 关联式容器包括：set、

multiset、map、multimap。SGI STL 还提供了一些非标准的关联式容器，eg：

hash_table、hash_set。

2. 底层实现

先了解几个概念：

二叉搜索树是一种特殊的二叉树，其具有如下性质：

1) 若左子树不空，则左子树所有结点的值均小于它的根结点的值

2）若右子树不空，则右子树所有节点的值均大于它的根节点的值

3）左右子树也分别为二叉搜索树

二叉搜索树支持各种动态集合操作，包括：插入、查找、删除，其操作的时间复杂度与

树的高度成正比，在遇到二叉树极端不平衡的情况下，其形状就与链表是一样的，二叉

树插入、查找、删除的时间复杂度都退化为 O（n）。

平衡二叉搜索树是一种特殊的二叉搜索树，其没有一个节点深度过大，不同的平衡条件，

造就不同的效率表现。常见的平衡二叉搜索树有：AVL-tree 和 RB-tree。

关联容器一般以平衡二叉搜索树作为内部数据结构，RB-tree 的应用尤其广泛。

RB-tree 是许多平衡二叉查找树的一种，一颗有 n 个内结点的红黑树的高度至多为

2lg(n+1)，它能保证在最坏情况下，基本的动态集合操作时间为 O(lgn)。

3. set / multiset

3.1 概念

set 不区分键值和实值，其键值就是实值。顾名思义，可以把 set 当做集合使用，由于 set

的底层是平衡二叉搜索树，因此其在插入、查询和删除时都是 O(lgn)的时间复杂度。set

和 multiset 唯一的不同是，set 不允许任何两个元素有相同的值，而 multiset 允许键

值重复。

3.2 迭代器

set 的迭代器本质上是 const_iterator，这是因为 RB-tree 的结构依赖

于数据的组织，如果允许通过 iterator 改变 set 元素值，会严重破坏

RB-tree 结构。此外，当对 set 进行插入和删除时，除了影响指向操作

元素本身的迭代器之外，不影响指向其它元素的迭代器。

3.3 Set API

(constructor) Construct set (public member function)

(destructor) Set destructor (public member function)

operator= Copy container content (public member function)

Iterators:

begin Return iterator to beginning (public member function)

end Return iterator to end (public member function)

rbegin Return reverse iterator to reverse beginning (public

member function)

rend Return reverse iterator to reverse end (public member

function)

Capacity:

empty Test whether container is empty (public member

function)

size Return container size (public member function)

max_size Return maximum size (public member function)

Modifiers:

insert Insert element (public member function)

erase Erase elements (public member function)

swap Swap content (public member function)

clear Clear content (public member function)

Observers:

key_comp Return comparison object (public member function)

value_comp Return comparison object (public member function)

Operations:

find Get iterator to element (public member function)

count Count elements with a specific key (public member

function )

lower_bound Return iterator to lower bound (public member

function)

upper_bound Return iterator to upper bound (public member

function)

equal_range Get range of equal elements (public member

function)

Allocator:

get_allocator Get allocator (public member function)

3.4 set 实例：

1. #include <iostream>

2. #include <set>

3. using namespace std;

5. int _tmain(int argc, _TCHAR* argv[])

6. {

7. set<int> myset;

8. set<int>::iterator it, itlow, uplow;

9. int i;

10.

11. //

插入数据

12. cout << "insert elements " << endl;

13. for (i=0; i<10; i++)

14. myset.insert(i*2);

15.

16. int num = 4;

17.

18. //

查询、删除数据

19. cout << "find and delete element" << 4 << endl;

20. it=myset.find(num);

21. if(it != myset.end())

22. {

23. myset.erase(it);

24. }

25.

26. num = 7;

27.

28. //

元素边界

29. itlow = myset.lower_bound(num);

30. uplow = myset.upper_bound(num);

31. cout << num << " lower bound is " << *itlow << endl;

32. cout << num << " upper bound is " << *uplow << endl;

33. pair<set<int>::iterator,set<int>::iterator> ret =

myset.equal_range(7);

34. cout << num << " lower bound is " << *ret.first << endl;

35. cout << num << " upper bound is " << *ret.second << endl;

36.

37. // check

数据是否在容器中

38. if (myset.count(num)>0)

39. cout << num << " is an element of myset.\n";

40. else

41. cout << num << " is not an element of myset.\n";

42.

43. //

输出容器大小

44. cout << "set size: " << (int) myset.size() << endl;

45.

剩余56页未读，继续阅读

内容反馈

王佛伟

粉丝: 13
资源: 320

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

STL关联容器概述1

评论0

最新资源

STL关联容器概述1

评论0

STL关联容器入门

eytzinger：具有Eytzinger（BFS）布局的C ++缓存友好型STL关联容器

安博牛耳教育_STL关联容器string算法.ppt

SGI STL 关联式容器源码

STL_2 关联容器 String 算法.pdf

STL的容器deque的使用

C++ STL vector 容器介绍

STL -容器,string容器

STL容器.emmx

STL容器使用代码

STL容器和算法函数表

STL容器的一些使用简介

C++标准库STL的容器vector

c++/STL容器设计相关

STL常用容器详细解析

STL_vector容器介绍

STL常用容器1

STL 容器对比

cpp-MyTinySTL用C11实现的小型STL容器库算法库

STL顺序容器：list的使用

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

安全认证cisp教材全套

OpenVAS GVM 中文翻译补丁

2024最新：Hvv中常见的面试问题

最新资源