【C++ 笔记五】STL 标准模板库 —— 容器基础进阶网站首页 其他

【C++ 笔记五】STL 标准模板库 —— 容器基础进阶

Loup&卡普 2024-10-17 12:01:05

简介【C++ 笔记五】STL 标准模板库 —— 容器基础进阶

【C++ 笔记五】STL 标准模板库 —— 容器基础进阶

文接上文【C++ 笔记四】STL 标准模板库 —— 容器基础

文章目录

【C++ 笔记五】STL 标准模板库 —— 容器基础进阶

I - 简单回顾

STL 六大组件之间的关系：

容器存储数据，存储需要使用内存，容器使用分配器去分配和释放内存，算法通过迭代器访问容器中的数据，仿函数用于算法的特别处理，适配器帮助仿函数/迭代器完成一些更细节的设置等。

1.1 - 序列式容器（顺序容器）

Sequence containers

顺序容器根据其内存结构可以大致分为三种

数组，连续内存空间
链表，非连续内存空间
映射表管理的分段连续空间

在这里插入图片描述
array / vector 连续内存空间，支持随机访问。

注: Random Access，个人感觉最初的翻译不恰当，应翻译为 任意访问，random 本身也有任意的意思。随机有被动的意思，任意有更多主动的含义。

list / forward-list 支持双/单向顺序访问。

forward-list 相较 list 少一倍的指针，只支持单向的顺序访问，其的迭代器也不支持 - - 递减运算符和reverse_iterator, 与手写最好单向链表相当的性能，所以也不支持 size() 操作。

stack 和 queue 底层是 deque 映射表管理多端连续内存，为容器适配器不提供迭代器访问。

选用容器时，通常最佳选用 vector，除非中间插入删除操作非常多时使用 list, forward-list，通常相同元素数量情况下，后两者内存额外开销较大。

1.2 - 关联式容器 (关联容器)

Associative containers

在大部分书籍中，不定序容器（unordered container）也归类于关联式容器。关联式容器底层实现主要包含两种数据结构：

红黑树
哈希表

在这里插入图片描述
查找速度：哈希表 > 红黑树

哈希表 bucket_size 与元素数量相同时，会两倍扩容，使用新的哈希计算方式，元素会被重新打散，分布到新的 bucket 后。哈希查找 O(1)，产生哈希冲突，即哈希值相同时只能循序查找。

1.3 - 访问方法/对外接口

插入

push_back(elem);
emplace_back(elem);
push_front(elem);
emplace_front(elem);

访问

// 若不存在，行为未定义
container[n]; 
// 若不存在，抛出异常 out_of_range
container.at(n);

行为未定义，表示可能获取到一个意外的数据，或者程序异常退出等。

删除

pop_back();
pop_front();

// 注意删除时刷新迭代器
erase(iter);
erase(iterA, iterB);

// 清空
clear();

删除示例：

std::vector<int> vec = { 1, 2, 4, 5, 6, 9 };

// lambda 表达式 [捕获](入参) -> 返回值类型 { 函数体 };
auto delete_element = [&vec](int a) -> bool 
{
	bool deleted(false);
	for (auto iter = vec.begin();
	iter != vec.end(); ++iter)
	{
		if (a == (*iter))
		{
			// 删除时刷新迭代器
			iter = vec.erase(iter);
			deleted = true;
		}
	}
	return deleted;
};

delete_element(5);

1.4 - 迭代器

迭代器为一种泛化的指针，容器内的可访问范围为一种左闭合区间 (left-inclusive interval) ，左闭右开 [begin, end) 。

在这里插入图片描述
反向迭代器的递增/递减 (++/--) 操作与正向迭代器方向相反。

II - 容器概述与注意事项

2.1 - 时间复杂度

顺序容器

顺序容器的查找时间复杂度为 O(n)，即在存在 n 个元素时，大 O 表示时间渐进复杂度上界，也就是最差的情况下需要查找 n 次。

关联容器

红黑树为一种特殊的平衡二叉搜索树 (balanced binary search tree)，查找复杂度为 O( $log_{}n$ )。

二叉树：一棵树型数据结构，每个节点至多有两个子节点。

平衡二叉树：即对于树中任何一个节点，它的左子树和右子树的高度之差 (平衡因子) 的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
这样平衡二叉树就可以避免其中一棵子树过深，造成搜索时间过长。

二叉搜索树：即对于树中任何一个节点，它左子节点的值，小于该节点的值。且该节点的值小于其右子节点的值。

红黑树如下图所示：
在这里插入图片描述
红黑树的最左节点为其最小值，最右节点为其最大值。

O( $log_{}n$ ) 推导过程:

因为每次查找从根节点开始，每次查找下降一个高度，元素即节点为 n 的情况下，高度约为 $log_{2}n+1$ ，也就是约需要查找 $log_{2}n+1$ 次。算法复杂度只保留最高阶即 $log_{2}n$ ，根据定义,

对于 O(g(n)) = f(n) ，存在正整数 $n_{0}$ 和 c，在 $n_{0}$ 时， $0 \leq f (n) \leq c g (n)$ 始终成立。

$log_{2}n$ ，假定 a 为 0 到正无穷，不为 0 且不为 1 的常数，根据换底公式

$log_{2}n = frac {log_{a}n} {log_{a}2} = frac {1} {log_{a}2} * log_{a}n$

${log_{a}2}$ 可视为常数，可见底数为 2 或任何对于 log 有意义的底数都作用不大，所以 2 省掉即为
$log_{}n$

2.2 - 注意事项

2.2.1 - 前递增/递减操作更高效

前递增/递减的运算结果为左值，后递增/递减的运算结果为右值。因此可进行连续的前递增/减操作，连续的后递增/减操作会产生编译错误。

int i = 0;

++++i; // ok
i++;   // ok
i++++; // compilation error, need l-value

----i; // ok
i--;   // ok
i----; // compilation error, need l-value

编译错误为需要一个左值。左值与右值，简而言之，对于一个赋值运算，等号左边的值为左值，等号右边的值为右值。

左值与右值的主要不同为，右值不可修改不可取地址。使用左值一般意义是使用其内存即地址值，右值一般使用其字面值即数据值，举例

int a(2), b(3);
a = 4; // 1
a = b; // 2

1 处 4 为右值，使用其数据值，a 在此处为左值，使用其存储空间即地址值
2 处 b 虽为与 a 相同的变量，但这里为右值，使用其数据值

容器迭代器实现前后递增操作符重载的方式是，后递增递减增加一个 int 参数以区分，但此参数无意义，仅用于区分。

list 的前递增与后递增代码示例：

// 前 ++，node 指针指向其下一个节点，且此处返回引用，即自身。如 cout << 可实现级联式输出操作，原理一致。
self& operator++()
{ node = (link_type) ((*node).next); return *this; }

// 后 ++ ，使用 int 参数区分，但本身此 int 无实际意义。
self operator++(int)
{ self tmp = *this; ++*this; return tmp; }
// 调用前 ++ ，并返回一个临时变量。

list 的后递增操作调用了前递增，由此也可得到前递增操作更高效。

2.2.2 - 基于范围的 for 循环 (range-based for loop)

C++11 为容器增加了基于范围的 for 循环语法，只能够访问和修改容器，但不能够在循环体内对容器进行增/删元素，否则会出现未定义行为 (undefined behavior)

for (auto decl : coll) 
{
	// loop body
}

// 例，访问
std::vector<double> vec;
for (auto elem : vec) { cout << elem << endl; }
// 修改
for (auto & elem : vec) { elem *= 3; }
// 添加元素 undefined behavior
std::vector<int> vec = { 1, 2, 4, 6 };
for (auto temp : vec) {
	if (4 == temp)
		vec.push_back(5);

	std::cout << temp << " "; // 1 2 4 -572662307
}

由于，上述语法在进入循环体之前，容器尾迭代器已经为确定的值，等效代码如下：

auto &&__coll = coll;
for (auto __begin = std::begin(__coll), __end = std::end(__coll);
	__begin != __end; ++__begin)
	{
		auto decl = *__begin;
		// loop body
	}

附加 cppreference 链接：https://en.cppreference.com/w/cpp/language/range-for

2.2.3 - list 不能使用 std::sort

std::list<int> lst = { 5, 6, 10, 1, 4, 8 };
std::sort(lst.begin(), lst.end(), greater<int>()); // (a)
std::sort(lst.begin(), lst.end(), 
[](int a, int b)-> bool { return a > b; }); // (b)

首先，此处代码无法编译通过，因为 std::sort() 入参需要随机访问迭代器，而 list 的迭代器为双向顺序访问迭代器。list 排序只能使用自身类的 sort() 方法。

lambda 表达式可以做到与仿函数一样的效果。(a) 与 (b) 等价。

有些初学者分不清楚， std::less<T>() 和 std::greater<T>() 哪个是从大到小，哪个是从小到大排列，这里有个记忆方法，greater 意为大于，大于号，也就是说此排序方式，使得容器中任意两个相邻元素之间大于号都成立，即 elem1 > elem2 > elem3 …，即为递减排列。less 同理。

III - Traits 方法

算法为了能够更好的适配容器，提高性能，需要了解迭代器的类型。

函数模板，编译器实参推导 (argument deduction)，可以结合函数重载和静态多态来理解。

Traits 方法使用了模板函数偏特化的方式来萃取迭代器类型，理解 Traits 方法，是能看懂 STL 源码的重要一环。

// 范化
template <class type>
struct __type_traits {
    // ...
}
// 特化 Specialization 特化即为特殊处理
template<> struct __type_traits<int> 
{
    //...
}


typedef template<> __STL_TEMPLATE_NULL
    

// 偏特化 Partial Specialization 即为部分特化，部分特殊处理。
template<class Alloc>
class vector<bool, Alloc>
{
    //...
}

算法为了更好的适配迭代器，需要知道迭代器类型，每个STL迭代器都定义了五种类型，迭代器分类，值类型，首尾迭代器差值类型，指针类型，引用类型。

STL 加入中间层 Traits 使用模板偏特化为原生指针封装此五种类型。

template <class I>
struct iterator_traits {
	typedef typename I::iterator_category iterator_category;
	typedef typename I::value_type        value_type;
	typedef typename I::difference_type   difference_type;
	typedef typename I::pointer           pointer;
	typedef typename I::reference         reference;
};

// pointer to T
template <class T>
struct iterator_traits<T*>
	typedef random_access_iterator_tag iterator_category;
	typedef T         value_type;
	typedef ptrdiff_t difference_type;
	typedef T*        pointer;
	typedef T&        reference;
};

// pointer to const T
template <class T>
struct iterator_traits<const T*>
	typedef random_access_iterator_tag iterator_category;
	typedef T         value_type;
	typedef ptrdiff_t difference_type;
	typedef T*        pointer;
	typedef T&        reference;
};
// 由于依然保留模板 所以为偏特化。