【C++】C++ 基础进阶【五】STL 容器进阶

简介: C++ STL 标准模板库中容器相关,以及一些注意事项

I - 简单回顾


STL 六大组件之间的关系:

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

1.1 - 序列式容器(顺序容器)


Sequence containers

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

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

sequencereview.png

array / vector 连续内存空间,支持随机访问。

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

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

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

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

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

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


Associative containers

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

  • 红黑树
  • 哈希表

reviewsequence.png

查找速度:哈希表 > 红黑树

哈希表 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) 。

reviewiterator.png
反向迭代器的递增/递减 (++/--) 操作与正向迭代器方向相反。

II - 容器概述与注意事项

2.1 - 时间复杂度


顺序容器

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

关联容器

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

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

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

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

红黑树如下图所示:

redblacktree.png

红黑树的最左节点为其最小值,最右节点为其最大值。

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

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

对于 O(g(n)) = f(n) ,存在正整数 $n_{0}$ 和 c, 在 $n \geq\ n_{0}$
,$$ 0 \leq\ f(n) \leq\ cg(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$$

$\frac {1} {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;
};
// 由于依然保留模板 所以为偏特化。

Traits 方法,也是为何 Qt 的容器也被 std 算法所支持的原因。

IV - 其他注意事项


push_backemplace_back 的区别。

emplace_back 是直接将构造函数所需的参数传递过去,然后构建一个新的对象出来,填充到容器尾部。也就是 就地构造(直接在容器内构造对象,不用拷贝一个复制品再使用)+ 强制类型转换 的方法来实现,在运行效率方面,由于省去了拷贝构造过程,因此效率更高。

V - 参考书目

  • 《STL源码剖析》— 侯捷
  • 《C++ Primer (中文版)》- 第 5 版
目录
相关文章
|
6月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
169 2
|
6月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
322 73
|
7月前
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
6月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
261 3
|
7月前
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
338 1
|
8月前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
177 21
|
7月前
|
存储 算法 C++
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
|
9月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
189 1
|
7月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
3月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
87 0