C++_chapter8_STL概述，关联/无序容器，分配器，迭代器

Mr_WangAndy

965人浏览 · 2025-11-04 15:05:31

Mr_WangAndy · 2025-11-04 15:05:31 发布

继续写关联容器和无序容器，分配器，迭代器，算法等。

文章目录

8.3 关联容器和无序容器

8.3.1 无序关联容器（哈希表）

无序关联容器底层用哈希表实现，增删查都是O(1) ；
在无序容器中，set只存放key, 无序是指：插入时不指定元素的插入位置，且不能重复。

unordered_set :  只存放key, 无序，且不能重复。
unordered_multiset： 存放key, 无序，key可以重复
unordered_map： 存放<key,value>，不能重复
unordered_multimap 存放<key,value> 可以重复

8.3.1.1. unordered_set的使用

1 insert emplace 插入元素

	std::unordered_set<int> uset1;
	uset1.insert(1);
	uset1.insert(2);
	uset1.emplace(3); // 原地构造元素
	uset1.insert(3);  // 重复元素不会被插入
	//for (const auto& elem : uset1)
	//{
	//	std::cout << elem << " ";
	//}
	//cout << endl;
	// 输出 1  2

2 find 查找元素，如果未找到则返回end()

	std::unordered_set<int> uset2 = { 1, 2, 3 };
	auto it = uset2.find(2);
	if (it != uset2.end()) 
	{
		std::cout << "Found: " << *it << std::endl;
	}
	else 
	{
		std::cout << "Not found" << std::endl;
	}

3 删除元素 erase

	std::unordered_set<int> uset3 = { 1, 2, 3 };
	uset3.erase(2); // 删除2

	for (const auto& elem : uset3)
	{
		std::cout << elem << " ";
	}
	cout << endl; // 输出 1 3

4 元素数量 count()

元素的数量 size() empty() count():返回具有指定键的元素数量结果只能是0或者1

	std::unordered_set<int> uset4 = { 1, 2, 3 };
	cout << uset4.size() << endl;  // 3 
	cout << uset4.empty() << endl; // 0
	cout << uset4.count(2) << endl; // 1

5 清空 clear

	std::unordered_set<int> uset5 = { 1, 2, 3 };
	cout << uset5.size() << endl;  // 3
	uset5.clear();
	cout << uset5.size() << endl;  // 0

6 遍历 begin() 和 end()

	std::unordered_set<int> uset6 = { 1, 2, 3 };
	cout << "6 遍历 begin() 和 end() " << endl;
	for (auto it = uset6.begin(); it != uset6.end(); ++it)
	{
		std::cout << *it << " ";
	}
	cout << endl; // 输出 1 2 3

7 返回桶的数量 backet_count()

	std::unordered_set<int> uset7 = { 1, 2, 3 };
	cout << "7 遍历 begin() 和 end() " << endl;
	cout << uset7.bucket_count() << endl; // 8
	for (size_t i = 0; i < uset7.bucket_count(); ++i) {
		cout << "桶 " << i << " 中的元素数量: " << uset7.bucket_size(i) << endl;
	}
	/*
		桶 0 中的元素数量: 0
		桶 1 中的元素数量: 0
		桶 2 中的元素数量: 0
		桶 3 中的元素数量: 0
		桶 4 中的元素数量: 1
		桶 5 中的元素数量: 0
		桶 6 中的元素数量: 1
		桶 7 中的元素数量: 1
	*/

8.3.1.2. unordered_multiset

1 插入元素 insert 和 emplace

	unordered_multiset<int> umset1;
	umset1.insert(1);
	umset1.insert(2);
	umset1.insert(3);
	umset1.insert(3); // 重复元素可以插入

	for (const auto& elem : umset1)
	{
		cout << elem << " ";
	}
	cout << endl;
	// 结果： 1 2 3 3

2 删除元素 erase clear()

erase(const key_type & key ) 删除 key 的元素
clear() 清空所有元素

	unordered_multiset<int> umset2 = { 1, 2, 3, 3 };
	umset2.erase(2);
	for (const auto& elem : umset2)
	{
		cout << elem << " ";
	} // 输出： 1 3 3 
	cout << endl;

3 查找元素 find() count()

find(const key_type& key): 查找等于 key 的元素，返回指向该元素的迭代器。
count(const key_type& key): 返回等于 key 的元素的数量。

	unordered_multiset<int> umset3 = { 1, 2, 3, 3 ,4};
	auto it = umset3.find(3);
	if (it != umset3.end()) 
	{
		cout << "Found: " << *it << endl;
	}
	else 
	{
		cout << "Not found" << endl;
	}
	// 元素数量
	cout << "Count of 3: " << umset3.count(3) << endl;  // 2

4 访问元素 *it begin() end()

*it 访问元素
begin() : 返回指向容器中第一个元素的迭代器。
end() : 返回指向容器中最后一个元素之后的迭代器。

	unordered_multiset<int> umset4 = { 1, 2, 2, 3 };

	// 遍历元素
	for (auto it = umset4.begin(); it != umset4.end(); ++it) 
	{
		cout << *it << " ";
	}

5 size() 和 empty()

size() : 返回容器中元素的数量。
empty() : 如果容器为空，则返回 true；否则返回 false。

	unordered_multiset<int> umset5 = { 1, 2, 2, 3 };
	// 容器大小
	cout << "Size: " << umset5.size() << endl;
	cout << "Is empty: " << (umset5.empty() ? "Yes" : "No") << endl;

	// 6 桶接口 
	unordered_multiset<int> umset6 = { 1, 2, 2, 3 };
	// 桶的数量
	cout << "Bucket count: " << umset6.bucket_count() << endl;
	// 每个桶中的元素数量
	for (size_t i = 0; i < umset6.bucket_count(); ++i) 
	{
		cout << "Bucket " << i << " size: " << umset6.bucket_size(i) << endl;
	}
	/*
	Bucket count: 8
	Bucket 0 size: 0
	Bucket 1 size: 0
	Bucket 2 size: 0
	Bucket 3 size: 0
	Bucket 4 size: 1
	Bucket 5 size: 0
	Bucket 6 size: 1
	Bucket 7 size: 2
	*/

8.3.1.3. unordered_map

unordered_map可以存放键值对。但是存放无序的，不能重复的键值对[key, value]。使用该容器插入时候，必须插入一对。

1获取元素的方法 operator[] 和 at()

	// 1.1, operator[] 方法 如果key不存在，会自动创建一个key
	unordered_map<char, int> umap;
	umap['A'] = 1; // 插入或者更新 A 的值；如果A不存在，就插入，如果存在就更新
	umap['B'] = 2;
	int value = umap['A']; //  访问A的值

	// 1.2 at 访问，通过键访问元素，如果不存在，会抛出异常 out_of_range
	unordered_map<char, int > umap2;
	umap2['A'] = 2;
	int value2 = umap2.at('A');
	//value2 = umap2.at('B'); // 会抛出异常 out_of_range

2 插入元素的方法 insert 和 emplace

insert() 插入

	unordered_map<char, int> umap3;
	umap3.insert({ 'A',2 });
	umap3.insert({ 'B',3 });
	umap3.insert(std::make_pair(  'C',4 ));
	int value3 = umap3.at('A');
	std::cout << value3 << endl;  // 输出 2 
	value3 = umap3.at('C');
	//std::cout << value3 << endl;

emplace 插入

	unordered_map<char, int> umap4;
	umap4.emplace('A', 1);
	//std::cout << umap4.at('A') << endl; // 输出 1

3 查找元素

	unordered_map<char, int> umap5;
	umap5['A'] = 1;
	umap5['B'] = 2;
	auto it = umap5.find('A');
	if (it != umap5.end())
	{
		std::cout << "找到了" << endl;
	}
	else
	{
		std::cout << "未找到" << endl;
	}
	// 结果 ： 找到了

4 删除元素

	unordered_map<char, int> umap6;
	umap6['A'] = 1;
	umap6['B'] = 2;
	umap.erase('A'); // 删除A

5 容器大小

size() 返回容器的数量；empty() 返回容器是否为空；

	unordered_map<char, int> umap7;
	umap7['A'] = 1;
	umap7['B'] = 2;
	std::cout << umap7.size() << endl; // 2
	std::cout << umap7.empty() << endl; // 0

	// count : 返回具有指定键的元素的数量 结果只能是0或者1
	std::cout << umap7.count('A') << endl; // 1
	std::cout << umap7.count('C') << endl; // 0

6 清空 clear()

	unordered_map<char, int> umap8;
	umap8['A'] = 1;
	umap8['B'] = 2;
	cout << umap8.size() << endl; // 2
	umap8.clear();
	cout << umap8.size() << endl; // 0

8.3.1.4. unordered_multimap

unordered_ multimap 不支持 [] 运算符重载。
键值对可以重复，与ordered_map 一样。

	unordered_multimap<int, string> map1;
	map1.insert({ 100,"Andy" });
	map1.insert(make_pair(101, "Anna"));
	map1.insert(make_pair(101, "Anna"));
	map1.insert(make_pair(101, "Anna"));

8.3.1.5. 无序关联容器的应用

1 在海量数据中，统计哪些数字重复了，并且统计数字重复的次数

分析：看到统计次数，可以确定使用unordered_multimap, key 存储原有的值，value存放key出现的次数。

int main()
{
	int arr[100];
	for (int i = 0; i < 100; i++)
	{
		arr[i] = rand() % 100;
	}

	unordered_map<int, int> map1;
	for (int k : arr)
	{
		//auto it = map1.find(k);
		//if (it == map1.end())  // 如果没有k值，则插入
		//{
		//	map1.insert({ k,1 });
		//}
		//else  // 如果存在，次数+1
		//{
		//	it->second++;
		//}

		map1[k]++;   // 如果k不存在，map1[k]++  {k,0}-> {k,1} 
	}				 // 如果存在，map1[k]++  {k,i}-> {k,i+1} 

	for (const pair<int, int> &v : map1)
	{
		if (v.second > 1)
		{
			cout << v.first << "," << v.second << endl;
		}
	}

	system("pause");
	return 1;
}

2. 去重复，把海量数据中重复的去掉

直接去重复时，不需要查看重复次数，直接使用unordered_set. 因为插入时，自动去重的功能。

int main()
{
	// 
	int arr[10];
	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 10;
	}

	unordered_set<int> set1;
	for (int k : arr)
	{
		set1.insert(k);
	}
	auto it = set1.begin();
	for (; it != set1.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	system("pause");
	return 1;
}

8.3.2 有序关联容器（红黑树）

有序容器与无序容器的使用类似，只不过底层是红黑树实现的。

set
multiset
map
multimap
插入，删除，查找时间复杂度是O(logn）

8.3.2.1 set用法

set 存放基础数据类型

int main()
{
	set<int> set1;
	for (int i = 0; i < 10; i++)
	{
		set1.insert(rand() % 10);
	}

	for (int v : set1)
	{
		cout << v << " ";
	}
	cout << endl;

	system("pause");
	return 1;
}

set存放类
需要提供operator<的实现。

class Student
{
public:
	Student(int id = 0, string name = " ")
		:_id(id)
		, _name(name)
	{
		
	}

	// 重载 < 
	bool operator<(const Student &stu) const
	{
		return _id > stu._id;
	}

private:
	int _id;
	string _name;
	friend ostream & operator<<(ostream &out, const Student &stu);
};

ostream & operator<<(ostream &out, const Student &stu)
{
	out << "id:" << stu._id << " name:" << stu._name << endl;
	return out;
}

int main()
{
	set<Student> set1;
	set1.insert(Student(2, "Andy"));
	set1.insert(Student(1, "Anna"));
	
	auto it = set1.begin();
	for (auto it = set1.begin(); it != set1.end(); ++it)
	{
		cout << *it << endl;
	}

	system("pause");
	return 1;
}

8.3.2.2 map用法

class Student
{
public:
	Student(int id = 0, string name = " ")
		:_id(id)
		, _name(name)
	{
		
	}

	// 重载 < 
	bool operator<(const Student &stu) const
	{
		return _id > stu._id;
	}

private:
	int _id;
	string _name;
	friend ostream & operator<<(ostream &out, const Student &stu);
};

ostream & operator<<(ostream &out, const Student &stu)
{
	out << "id:" << stu._id << " name:" << stu._name << endl;
	return out;
}


int main()
{
	set<Student> map1;
	map1.insert(Student(2, "Andy"));
	map1.insert(Student(1, "Anna"));
	
	auto it = map1.begin();
	for (auto it = map1.begin(); it != map1.end(); ++it)
	{
		cout << *it << endl;
	}

	system("pause");
	return 1;
}

8.4分配器简介、使用与工作原理说

分配器就是扮演内存池的角色。
C++中的分配器直接使用了malloc，并没有使用内存池。

	void test()
	{
		allocator<int> aloc1;
		int* p = aloc1.allocate(3); // 保存 3个int，12字节
		aloc1.deallocate(p, 3);
	}

8.5迭代的概念和分类

8.5.1迭代器基本概念

迭代器类似于指针，指向容器中的某一个位置。指针可以用p来读取指向的内容，同理迭代器可以用iter来读取指向的内容。

8.5.2选代器的分类

迭代器的分类原因：迭代器主要根据容器的底层数据结构来划分的。
功能：迭代器是STL中连接容器与算法的抽象接口，提供了统一的数据访问方式，实现了算法与容器的解耦合。
迭代器特点：共三条
(1) 迭代器对于容器来说，可以根据类似指针的操作(如*it,++it)访问元素的内容；
(2) 算法通用性：对于同一个算法，比如sort()，传入迭代器完成对容器的操作，可以支持vector和deque的排序。
(3) 迭代器区间：左闭右开，[begin,end),end指向末尾下一个元素，即空的无效的位置。迭代器分五类。

输入型迭代器：struct input_iterator_tag

功能：只能单方向向前移动一次，支持读取元素，但不支持修改。
支持操作：*it, ++it, ==, != 等。
典型应用：用于单遍扫描算法，如 std::find，扫描一遍vector或list，查看是否存在某个元素
支持容器：无容器专门只支持输入迭代器，但某些算法返回的临时迭代器可能属于此类（如 istream_iterator）。

void test2()
 {
     // 从字符串流中读取数据
     std::istringstream iss("10 20 30 40 50");
     // 创建输入迭代器，会自动跳过 空格 回车等，读取到下一个空格后停止，然后将这个读取内容转为
     // int
     std::istream_iterator<int> start(iss);
     std::istream_iterator<int> end;  // 默认构造表示结束
     // 使用std::find在流中查找值30
     auto result = std::find(start, end, 30);
     if (result != end) 
     {
         std::cout << "找到值30!" << std::endl;
         // 注意：此时流已经被消耗到值30之后的位置
         if (result != end) 
         {
             std::cout << "下一个值是: " << *(++result) << std::endl; // 会输出40
         }
     }
     else 
     {
         std::cout << "未找到值30" << std::endl;
     }
 }

输出型迭代器：struct output_iterator_tag

功能：只能单方向向前移动，支持写入元素，但不支持读取元素。
支持操作：++（前置和后置）、*（解引用赋值）。
典型应用：用于单遍输出算法，如 std::copy 的输出目标。
支持容器：无容器专门只支持输出迭代器，但某些算法返回的临时迭代器可能属于此类（如 ostream_iterator）。

    void test3()
    {
        std::vector<int> numbers = { 1,2,3,4,5,6 };
        std::ofstream outfile("event_number.txt");
        // 创建输出迭代器 outfile，写入到文件，每个元素用逗号分隔
        std::ostream_iterator<int> file_iter(outfile, ", ");
        // 使用std::copy_if将偶数筛选出来并写入文件
        std::copy_if(numbers.begin(), numbers.end(), file_iter,
            [](int n) { return n % 2 == 0; });
        // 文件内容: 2, 4, 6
        outfile.close();
    }

前向迭代器：struct forward_iterator_tag

功能：支持单方向向前移动，支持多次读取同一位置的元素，也支持修改元素（如果容器允许）。
支持操作：所有输入迭代器的操作 + 多次解引用。
典型应用：用于多遍扫描算法，如 std::replace。
支持容器：std::forward_list、std::unordered_set、std::unordered_map 及其对应的 multiset 和 multimap。

双向迭代器：struct bidirectional_iterator_tag

功能：支持双向移动（向前和向后），支持多次读取和修改元素。
支持操作：所有前向迭代器的操作 + --（前置和后置）。
典型应用：用于需要双向遍历的算法，如 std::reverse。
支持容器：std::list、std::set、std::map 及其对应的 multiset 和 multimap。

随机访问迭代器：struct random_access_iterator_tag

功能：支持双向移动和随机访问（跳跃式访问），支持高效的元素定位。
支持操作：所有双向迭代器的操作 +=、-=、+、-、[]（下标访问）、<、>、<=、>=。
典型应用：用于需要随机访问的算法，如 std::sort。
支持容器：std::vector、std::deque、std::array、普通数组。

8.5.3 各容器的迭代器类型

容器类型	支持的迭代器类型
std::vector因为底层是连续的内存，所以是随机访问迭代器	随机访问迭代器
std::deque 分段连续的内存结构，底层是内存块和索引表结构，	随机访问迭代器
std::array	随机访问迭代器
std::list底层是双向链表结构，每个节点保存了向前或向后的节点，所以可以双向访问。时间复杂度：O(n)	双向迭代器
std::set / std::multiset std::map / std::multimap树形结构：底层是红黑树，对于树中的节点指向了父节点和子节点，但是迭代器按照顺序访问。	双向迭代器
std::unordered_set / std::unordered_multiset std::unordered_map / std::unordered_multimap哈希表结构，使用链式哈希表，每次遍历都是一个哈希函数映射后的值，只能向前遍历。	前向迭代器
普通数组	随机访问迭代器
std::forward_list	前向迭代器

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

亚马逊云科技技术品牌专区

所有评论(0)

查看更多评论

Mr_WangAndy

@weixin_43916755

已为社区贡献9条内容

C++_chapter8_STL概述，关联/无序容器，分配器，迭代器

Mr_WangAndy

文章目录

8.3 关联容器和无序容器

8.3.1 无序关联容器（哈希表）

8.3.1.1. unordered_set的使用

1 insert emplace 插入元素

2 find 查找元素，如果未找到则返回end()

3 删除元素 erase

4 元素数量 count()

5 清空 clear

6 遍历 begin() 和 end()

7 返回桶的数量 backet_count()

8.3.1.2. unordered_multiset

1 插入元素 insert 和 emplace

2 删除元素 erase clear()

3 查找元素 find() count()

4 访问元素 *it begin() end()

5 size() 和 empty()

8.3.1.3. unordered_map

1获取元素的方法 operator[] 和 at()

2 插入元素的方法 insert 和 emplace

3 查找元素

4 删除元素

5 容器大小

6 清空 clear()

8.3.1.4. unordered_multimap

8.3.1.5. 无序关联容器的应用

1 在海量数据中，统计哪些数字重复了，并且统计数字重复的次数

2. 去重复，把海量数据中重复的去掉

8.3.2 有序关联容器（红黑树）

8.3.2.1 set用法

8.3.2.2 map用法

8.4分配器简介、使用与工作原理说

8.5迭代的概念和分类

8.5.1迭代器基本概念

8.5.2选代器的分类

输入型迭代器：struct input_iterator_tag

输出型迭代器：struct output_iterator_tag

前向迭代器：struct forward_iterator_tag

双向迭代器：struct bidirectional_iterator_tag

随机访问迭代器：struct random_access_iterator_tag

8.5.3 各容器的迭代器类型

所有评论(0)

温馨提示：您尚未绑定手机号

Mr_WangAndy