行者无畏
20240604 stl
明昧 Lv7
  2024-06-04 19:26:18   2024-06-05 14:11:55  

加油

拿出要搬家的气势！！

STL

Standard Template Library，一套基于模板的容器类库，提高了程序开发效率和复用性

六大部件

  1. Container(容器) ：vector、list、deque、set、map
  2. Adapter(适配器)
  3. Algorithm(算法) ：sort、search、copy、erase
  4. Iterator(迭代器)
  5. Function object(函数对象)
  6. Allocator(分配器)

容器：容纳一组元素的对象。

迭代器：提供一种访问容器中每个元素的方法。

函数对象：一个行为类似函数的对象，调用它就像调用函数一样。

算法：包括查找算法、排序算法等等。

适配器：用来修饰容器等，比如queue和stack，底层借助了deque。

空间配置器：负责空间配置和管理。

内存空间的管理

对象构造前的空间配置和对象析构后的空间释放，由<stl_alloc.h>负责，SGI对此的设计哲学如下：

  • 向system heap要求空间。
  • 考虑多线程状态。
  • 考虑内存不足时的应变措施。
  • 考虑过多“小型区块”可能造成的内存碎片问题。

考虑小型区块造成的内存破碎问题，SGI设计了双层级配置器：

第一级直接使用allocate()调用malloc()、deallocate()调用free()，使用类似new_handler机制解决内存不足（抛出异常），配置无法满足的问题（如果在申请动态内存时找不到足够大的内存块，malloc 和new 将返回NULL 指针，宣告内存申请失败）。

第二级视情况使用不同的策略，当配置区块大于128bytes时，调用第一级配置器，当配置区块小于128bytes时，采用内存池的整理方式：配置器维护16个（128/8）自由链表，负责16种小型区块的此配置能力。内存池以malloc配置而得，如果内存不足转第一级配置器处理。

一、STL的介绍

Standard Template Library，标准模板库，是C++的标准库之一，一套基于模板的容器类库，还包括许多常用的算法，提高了程序开发效率和复用性。STL包含6大部件：容器、迭代器、算法、仿函数、适配器和空间配置器。

  • 容器：容纳一组元素的对象。
  • 迭代器：提供一种访问容器中每个元素的方法。
  • 函数对象：一个行为类似函数的对象，调用它就像调用函数一样。
  • 算法：包括查找算法、排序算法等等。
  • 适配器：用来修饰容器等，比如queue和stack，底层借助了deque。
  • 空间配置器：负责空间配置和管理。

二、空间配置器详解

对象构造前的空间配置和对象析构后的空间释放，由<stl_alloc.h>负责，SGI对此的设计哲学如下：

  • 向system heap要求空间。
  • 考虑多线程状态。
  • 考虑内存不足时的应变措施。
  • 考虑过多“小型区块”可能造成的内存碎片问题。

考虑小型区块造成的内存破碎问题，SGI设计了双层级配置器：

  • 第一级直接使用allocate()调用malloc()、deallocate()调用free()，使用类似new_handler机制解决内存不足（抛出异常），配置无法满足的问题（如果在申请动态内存时找不到足够大的内存块，malloc 和new 将返回NULL 指针，宣告内存申请失败）。
  • 第二级视情况使用不同的策略，当配置区块大于128bytes时，调用第一级配置器，当配置区块小于128bytes时，采用内存池的整理方式：配置器维护16个（128/8）自由链表，负责16种小型区块的此配置能力。内存池以malloc配置而得，如果内存不足转第一级配置器处理。

配置器尚未看

存档后面看

https://blog.csdn.net/daaikuaichuan/article/details/80717222

三、各种容器的特点和适用情况

序列式容器 vector deque list forward_list array string

关联式容器 set multiset map multimap

无序容器 unordered_set unordered_multiset …

(无序又专门搞了容器，到底想干嘛)

无序容器的设计目的

  1. 性能优化：无序容器基于哈希表实现，通常能在平均O(1)时间复杂度内完成插入、查找和删除操作，而关联式容器（如std::map和std::set）基于平衡树实现，操作时间复杂度为O(log n)。因此，在需要快速访问和操作的场景中，无序容器性能更佳。

  2. 无序性需求：有些应用场景并不需要数据按顺序存储，反而更注重操作的速度。无序容器不维护元素的顺序，这使得其在插入和删除操作中无需进行额外的排序调整，从而提高了效率。

  3. 具体使用场景

    1. 高频查找和插入操作：在需要频繁进行查找和插入操作的场景中，无序容器如std::unordered_map和std::unordered_set能够显著提升性能。例如，哈希表常用于缓存机制、计数统计和字典查找等场景。
    2. 元素顺序不重要：在某些应用中，元素的存储顺序并不重要，例如统计元素频率、快速查找元素是否存在等，这些场景下无序容器是更好的选择。
    3. 内存使用情况：由于哈希表需要额外的空间来存储哈希值和处理冲突，无序容器的内存开销通常比关联容器略高。然而在很多情况下，这一点的开销是可以接受的，特别是当性能优先时。

    关联式容器的优势

    尽管无序容器有许多优势，关联式容器在某些方面仍然具有优势：

    1. 有序数据：当需要按顺序存储和访问数据时，关联式容器是首选。例如，需要按键排序的数据结构或需要按顺序遍历元素的场景中，std::map和std::set更为适用。
    2. 范围操作：关联式容器支持高效的范围操作（如查找键在某范围内的所有元素），这是无序容器无法高效完成的。
    3. 稳定的性能：关联式容器的时间复杂度为O(log n)，虽然单次操作时间稍长，但性能更为稳定，不受哈希函数质量和冲突处理策略的影响。

序列式容器

vector deque/先进先出 list forward_list array string

1717539175951

四、各种容器的底层机制和常见面试题

traits技术

原理：利用template的参数推导机制获取传入的参数型别。

被萃取的东西：

value type：描述iterator指向对象的型别。

difference type：描述两个iterator之间的距离，默认情况下使用C++内建的ptrdiff_t类型

reference type：描述iterator所指向对象的引用

pointer type：描述iterator所指向对象的指针

iterator_category

：描述迭代器的相应性别

Input Iterator：只读迭代器

Output Iterator：只写迭代器

Forward Iterator：读写迭代器

Bidirectional Iterator：双向移动迭代器，可读写

Random Access Iterator：随机移动迭代器，可读写

  • 设计适当的型别，是迭代器的责任。
  • 设计适当的迭代器，是容器的责任。

https://blog.csdn.net/weixin_46645965/article/details/136436981

指针和迭代器的区别

一句话，指针是不同的类型们直接通过地址访问内存的

而迭代器是一种访问容器内数据的入口

二者都可以访问数据

指针和迭代器在C++中都是用于访问和操作数据元素的工具，但它们在概念、使用场景和功能上有一些重要的区别。以下是指针和迭代器的主要区别：

指针

  1. 定义：指针是一个变量，它存储另一个变量的内存地址。指针本质上是一个内存地址的直接引用。

  2. 类型：指针有特定的类型，表示它所指向的内存位置存储的数据类型。例如，int*表示一个指向整数的指针。

  3. 语法和操作：

    • 可以通过*操作符解引用，访问指针指向的对象。
    • 可以通过&操作符获取一个变量的地址。
    • 支持指针算术，如加减操作，可以用来遍历数组。

  4. 应用场景：

    • 直接操作内存。
    • 数组遍历和指针算术。
    • 动态内存分配。
    • 函数指针，用于函数回调。

  5. 示例：

    1
    cpp
  6. int x = 10;
int* p = &x; // p指向x的地址
*p = 20;    // 通过指针修改x的值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

    ### 迭代器

    1. **定义**：迭代器是一个抽象的工具，提供了一种访问容器（如数组、向量、链表等）中元素的方法，而不需要了解底层实现细节。

    2. **类型**：迭代器是容器类型的一部分，每个容器类型都定义了自己的迭代器类型。例如，`std::vector<int>::iterator`是一个指向`std::vector<int>`元素的迭代器。

    3. **语法和操作**：

       - 通过解引用操作符`*`访问迭代器指向的元素。
       - 通过`++`和`--`操作符前进和后退。
       - 支持与指针类似的算术操作（随机访问迭代器）。
       - 迭代器类型可以是输入迭代器、输出迭代器、前向迭代器、双向迭代器或随机访问迭代器，支持不同级别的功能。

    4. **应用场景**：

       - 容器遍历。
       - 提供统一接口，支持多种容器类型的泛型算法。
       - STL算法库与容器之间的桥梁。

    5. **示例**：

    
cpp

    1
    2
    3
    4
    5
    6
    7
    8

    1. ```
       std::vector<int> vec = {1, 2, 3, 4, 5};
       std::vector<int>::iterator it = vec.begin();
       while (it != vec.end()) {
           std::cout << *it << " ";
           ++it;
       }

区别总结

  1. 抽象层次：指针是底层的直接内存地址操作工具，而迭代器是更高层次的抽象工具，提供了访问容器元素的统一接口。
  2. 适用范围：指针适用于任何内存地址操作，而迭代器专门用于容器元素的访问和操作。
  3. 安全性和易用性：迭代器提供了更安全和易用的接口，隐藏了底层实现细节，减少了内存操作错误的风险。
  4. 容器兼容性：迭代器与STL算法库紧密结合，提供了容器无关的遍历和操作方式，而指针主要用于简单的数据结构和数组操作。

通过以上分析，可以看出指针和迭代器各有其特点和适用场景，在实际开发中应根据具体需求选择合适的工具。

RAII

  • 一种技术
  • 在对象的构造函数中获取资源，在对象的析构函数中释放资源。
  • 在STL中的应用是

智能指针的特点：

1.不用显式地写出释放资源的语句。

2.资源在智能指针的生命周期中始终有效。

3.可以像指针一样的使用。

4.最重要的是：具有RAII特性

vector

  • vector当调用clear（）的时候清空的是什么
  • vector底层依靠什么在维护
  • vector关于内存的管理是怎样实现的
  • vector的迭代器使用

当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。

一个动态扩张的数组

底层采用三个迭代器来进行维护

开始 被使用结尾 被开辟结尾

vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。

1.分配std::vector 会预先分配一块连续内存来存储元素

2.扩容当 std::vector 的大小（size）达到容量（capacity）时，需要扩容。扩容通常会倍增（即容量乘以 2），以避免频繁的内存分配。扩容时，会进行以下步骤：

分配一块更大的内存。

将旧数据复制到新内存中。

释放旧内存。

3.释放内存：当 std::vector 被销毁时，其析构函数会自动释放内存。此外，可以使用 clear 方法清空元素，或使用 shrink_to_fit 方法请求释放未使用的内存，但具体行为依赖于实现。

  1. 自定义分配

    允许使用自定义分配器来控制内存分配和释放行为。自定义分配器需要满足一定的接口要求。

当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5倍或者2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间【vector内存增长机制】。

因此，对vector的任何操作一旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了。

  • vector 扩容为什么要以1.5倍或者2倍扩容?

  • vector如何删除数据和释放内存

  • vector中的size和capacity的区别

  • vector中的reserve和resize的区别

根据查阅的资料显示，考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2倍的方式扩容，或者以1.5倍的方式扩容。

以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间：

1717561481059

std::vector 在需要扩容时通常以 1.5 倍或 2 倍的倍数增加其容量，这种扩容策略主要出于性能和内存使用效率的考虑。以下是其中的原因和细节：

1. 减少内存分配次数

每次向 std::vector 中添加元素时，如果当前容量不足以容纳新元素，vector 需要分配新的更大容量的内存，并将旧内存中的元素复制到新内存中。这一过程涉及分配内存和复制数据，开销较大。通过成倍增长容量，可以减少内存重新分配的频率，从而提升性能。

2. 平衡内存浪费和重新分配成本

如果每次扩容只增加一个固定的数量，例如增加 1 个或几个元素，那么当有大量元素要插入时，会频繁地进行内存分配和数据复制，严重影响性能。

如果每次扩容成倍增长，例如增加 2 倍，那么内存使用效率较高，但可能导致内存浪费。例如，如果最终需要 1001 个元素，而容器容量为 1024，则浪费了 23 个元素的空间。通过成倍增加容量，std::vector 在性能和内存浪费之间找到了一个折中。

3. 避免时间复杂度过高

扩容的时间复杂度是摊销的线性时间。假设初始容量为 nnn，每次扩容成倍增长，当 vector 容量增加到 2n2n2n 时，之前的所有扩容操作总共复制了约 nnn 次元素。因此，总的时间复杂度是线性的，而不是指数级增长的。

4. 成倍增长的选择

成倍增长可以是 1.5 倍、2 倍或其他比例。这些选择取决于实现和设计权衡。

  • 1.5 倍扩容：较少的内存浪费，但扩容频率更高。
  • 2 倍扩容：更少的扩容频率，但内存浪费较多。

不同的 STL 实现可能选择不同的增长策略。例如，GNU libstdc++ 使用 1.5 倍的扩容策略，而 Microsoft STL 使用 2 倍扩容策略。

vec.clear()：清空内容，但是不释放内存。

vector().swap(vec)：清空内容，且释放内存，想得到一个全新的vector。

vec.shrink_to_fit()：请求容器降低其capacity和size匹配。

vec.clear();vec.shrink_to_fit();：清空内容，且释放内存。

增加 vector 的容量，以便减少未来的内存分配次数。

不改变 vector 的大小，即 vector 的 size 不变。

如果新的容量大于当前容量，则分配新的内存，并将现有元素移动到新的内存位置。如果新的容量小于或等于当前容量，则什么都不做。

reserve是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化push_back），就可以提高效率，其次还可以减少多次要拷贝数据的问题。reserve只是保证vector中的空间大小（capacity）最少达到参数所指定的大小n。reserve()只有一个参数。

resize()可以改变有效空间的大小，也有改变默认值的功能。capacity的大小也会随着改变。resize()可以有多个参数。

list

  • list的底层

  • list的节点结构

  • 迭代器

list的底层是一个双向链表，以结点为单位存放数据，结点的地址在内存中不一定连续，每次插入或删除一个元素，就配置或释放一个元素空间。

list不支持随机存取，如果需要大量的插入和删除，而不关心随即存取

list的节点结构(双向节点)

1
2
3
4
5
6
7
template < class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer next; //型别为void*，也可以设为__list_node<T>*
    void_pointer prev;
    T data;
};

1717562028251

在Vector中，由于是连续的存储空间，支持随机存取，所以其迭代器可以直接用普通指针代替。但是，在List中行不通。List必须有能力指向List的节点，并有能力进行正确的递增、递减、取值和成员存取等操作。

List是一个双向链表，迭代器必须具备前移、后退的能力，所以List的迭代器是一个Bidirectional Iterator！在Vector中如果进行插入和删除操作后迭代器会失效，List有一个重要的性质就是插入和接合操作都不会造成原有的List迭代器失效。而且，再删除一个节点时，也仅有指向被删除元素的那个迭代器失效，其他迭代器不受任何影响。

List的迭代器实现了==,!=,++,–,取值和成员调用等操作，由于是存放在不连续的内存空间，所以并不支持vector那样的p+n的操作。

  • list构造函数
1
2
3
4
5
6
7
std::list<int> l1; // 构造空的l1
std::list<int> l2 (4,100); // l2中放4个值为100的元素
std::list<int> l3 (l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
std::list<int> l4 (l3); // 用l3拷贝构造l4
// 以数组为迭代器区间构造l5
int array[] = {16,2,77,29};
std::list<int> l5 (array, array + sizeof(array) / sizeof(int) );
  • 正反迭代器

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

find()和find_if

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
int main()
{
    list<int> lst;
    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);
    list<int>::iterator it = find(lst.begin(), lst.end(), 10); // 查找list中是否有元素“10”
    if (it != lst.end()) // 找到了
    {
        // do something 
    }
    else // 没找到
    {
        // do something
    }
    return 0;
}
  • find的实现

std::find 可以用于 std::list 及其他任何提供了迭代器的标准容器。它通过迭代器逐个遍历元素，找到满足条件的第一个元素，并返回其迭代器。在 std::list 中，std::find 的查找操作是线性的，因为链表不支持随机访问，只能逐个节点进行比较。

  • find的延伸出的问题

那么，如果容器里的元素是一个类呢？例如，有list ，其中CPerson类定义如下：

1
2
3
4
5
6
7
8
9
10

class CPerson
{
public:
    CPerson(void); 
    ~CPerson(void);

public:
    int age; // 年龄
};

那么如何用find()函数进行查找呢？这时，我们需要提供一个判断两个CPerson对象“相等”的定义，find()函数才能从一个list中找到与指定的CPerson“相等”的元素。

这个“相等”的定义，是通过重载“==”操作符实现的，我们在CPerson类中添加一个方法，定义为：

1
2
3
4
5
6
7
8
bool operator==(const CPerson &rhs) const; 

实现为： 

bool CPerson::operator==(const CPerson &rhs) const 
{ 
    return (id == rhs.age); 
}

然后我们就可以这样查找（假设list中已经有了若干CPerson对象）了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

list<CPerson> lst; 

// 

// 向lst中添加元素，此处省略 

// 

CPerson cp_to_find; // 要查找的对象 

cp_to_find.age = 50; 

list<CPerson>::iterator it = find(list.begin(), list.end(), cp_to_find); // 查找 


if (it != lst.end()) // 找到了 

{ 

    // do something  

} 

else // 没找到 

{ 

    // do something 

}

这样就实现了需求。

有人说，如果我有自己定义的“相等”呢？例如，有一个list<CPerson*>，这个list中的每一个元素都是一个对象的指针，我们要在这个list中查找具有指定age的元素，找到的话就得到对象的指针。

这时候，你不再能像上面的例子那样做，我们需要用到find_if函数，并自己指定predicate function（即find_if函数的第三个参数，请查阅STL手册）。先看看find_if函数的定义：

未完待续

https://blog.csdn.net/CNHK1225/article/details/48678203

find_if

std::find_if 是 C++ 标准模板库 (STL) 中的一个算法，用于在范围内查找满足特定条件的第一个元素。它提供了一种灵活的方式，通过使用谓词（即返回布尔值的函数对象或函数）来查找符合条件的元素。

功能和用法

std::find_if 可以用于任何符合迭代器要求的容器，如 std::vector, std::list, std::deque 等等。它遍历容器中的元素，并返回第一个满足谓词条件的元素的迭代器。如果找不到这样的元素，则返回指向范围末尾的迭代器。

函数原型

1
2
3
template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );

InputIt first, last：定义要查找的范围 [first, last)，左闭右开区间。

UnaryPredicate p：一个谓词，接收元素并返回布尔值。谓词可以是函数指针、函数对象或 lambda 表达式。

示例

以下是一些使用 std::find_if 的示例：

示例 1：查找第一个大于 10 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <algorithm>

bool is_greater_than_10(int value) {
    return value > 10;
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 15, 6, 7, 20};

    auto it = std::find_if(vec.begin(), vec.end(), is_greater_than_10);

    if (it != vec.end()) {
        std::cout << "First element greater than 10: " << *it << std::endl;
    } else {
        std::cout << "No element greater than 10 found." << std::endl;
    }

    return 0;
}

示例 2：使用 lambda 表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 15, 6, 7, 20};

    auto it = std::find_if(vec.begin(), vec.end(), [](int value) {
        return value > 10;
    });

    if (it != vec.end()) {
        std::cout << "First element greater than 10: " << *it << std::endl;
    } else {
        std::cout << "No element greater than 10 found." << std::endl;
    }

    return 0;
}


示例 3：查找具有特定属性的结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <algorithm>

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 40}
    };

    auto it = std::find_if(people.begin(), people.end(), [](const Person& person) {
        return person.age > 30;
    });

    if (it != people.end()) {
        std::cout << "First person older than 30: " << it->name << " (" << it->age << ")" << std::endl;
    } else {
        std::cout << "No person older than 30 found." << std::endl;
    }

    return 0;
}


总结

std::find_if 是一个非常强大的工具，可以在范围内查找符合特定条件的第一个元素。它通过使用谓词来实现灵活的查找功能，能够处理各种类型的容器和复杂的查找条件。它的用法简单，结合 C++11 引入的 lambda 表达式，可以极大地提升代码的简洁性和可读性。

map

map与multimap是STL中的关联容器、提供一对一key-value的数据处理能力； map与multimap的区别在于，multimap允许关键字重复，而map不允许重复。

这两个关联容器的底层数据结构均为红黑树，关于红黑树的理解可以参考教你透彻了解红黑树一文。

根据红黑树的原理，map与multimap可以实现**O(lgn)**的查找，插入和删除。

  • map的基础节点
1
2
3
4
5
6
7
8
9
template <typename Key, typename T>
struct Node {
    std::pair<const Key, T> value;
    Node* parent;
    Node* left;
    Node* right;
    bool isRed;
};

核心操作

  1. 查找操作：

    • 从根节点开始，依次比较键值，向左子树或右子树递归，直到找到目标键或到达叶节点。
    • 时间复杂度为 O(log n)。

  2. 插入操作：

    • 插入新节点后，按照红黑树的规则进行调整（旋转和重新着色），以保持树的平衡。
    • 时间复杂度为 O(log n)。

  3. 删除操作：

    • 删除节点后，同样需要按照红黑树的规则进行调整，保证树的平衡。
    • 时间复杂度为 O(log n)。

红黑树的平衡调整

红黑树的平衡调整是通过旋转和重新着色来实现的：

  1. 旋转：分为左旋和右旋，用于改变节点的结构，使树保持平衡。
  2. 重新着色：根据红黑树的规则，调整节点的颜色，以满足红黑树的特性。

例如，插入一个新节点后可能导致连续的红色节点，通过重新着色和旋转来调整树的结构：

  • 左旋：将当前节点与其右子节点进行旋转。
  • 右旋：将当前节点与其左子节点进行旋转。

红黑树是一种自平衡二叉搜索树，通过节点的颜色和结构调整来保持平衡。节点的选择和重新着色遵循一系列严格的规则，以确保树的平衡性和操作的高效性。下面是红黑树的基本规则和在插入、删除操作中进行选择和重新着色的具体规则：

红黑树的基本性质

  1. 节点颜色：每个节点是红色或黑色。
  2. 根节点：根节点是黑色。
  3. 叶节点（NIL节点）：每个叶节点（即空节点）是黑色。
  4. 红色节点限制：红色节点的两个子节点必须是黑色（即红色节点不能连续）。
  5. 黑色节点平衡：从任一节点到其每个叶节点的所有路径都包含相同数量的黑色节点。

插入操作中的调整规则

插入操作可能打破红黑树的平衡，需要通过重新着色和旋转来修复。具体步骤如下：

  1. 插入节点并着色：新插入的节点总是红色。

  2. 调整

    ：

    • Case 1: 插入节点是根节点。将其重新着色为黑色。

    • Case 2: 插入节点的父节点是黑色。红黑树仍然平衡，无需调整。

    • Case 3
      插入节点的父节点是红色。

      • Case 3.1: 叔叔节点（父节点的兄弟节点）是红色。将父节点和叔叔节点重新着色为黑色，祖父节点重新着色为红色，然后将祖父节点作为新的插入节点进行下一轮调整。

      • Case 3.2
        叔叔节点是黑色或NIL。
        • Case 3.2.1: 插入节点是父节点的右子节点，父节点是祖父节点的左子节点。以父节点为中心左旋。
        • Case 3.2.2: 插入节点是父节点的左子节点，父节点是祖父节点的右子节点。以父节点为中心右旋。
        • Case 3.2.3: 进行对称旋转和重新着色。

以下是一个插入操作的示例图解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
插入操作前：
       B
      / \
     R   R

插入节点后：
       B
      / \
     R   R
      \
       R  (新插入的节点)

调整后的红黑树：
       R
      / \
     B   B
      \
       R

删除操作中的调整规则

删除操作也可能打破红黑树的平衡，尤其是删除黑色节点，需要通过重新着色和旋转来修复。具体步骤如下：

  1. 标记节点和子节点：
    • 如果删除的节点是红色，直接删除即可。
    • 如果删除的节点是黑色，标记替代它的子节点（如果有）为双重黑色节点。
  2. 调整：
    • Case 1: 双重黑色节点是根节点。直接移除双重黑色标记。
    • Case 2: 双重黑色节点的兄弟节点是红色。将兄弟节点重新着色为黑色，将父节点重新着色为红色，然后进行旋转。
    • Case 3: 双重黑色节点的兄弟节点是黑色，兄弟节点的两个子节点都是黑色。将兄弟节点重新着色为红色，双重黑色上移到父节点。
    • Case 4: 双重黑色节点的兄弟节点是黑色，兄弟节点的一个子节点是红色。进行旋转和重新着色，使双重黑色节点平衡。

以下是一个删除操作的示例图解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
删除操作前：
       B
      / \
     R   B
         /
        R

删除节点后：
       B
      / \
     R   B (双重黑色)

调整后的红黑树：
       B
      / \
     B   R
         /
        B

旋转操作

旋转操作用于在调整红黑树时保持树的平衡，包括左旋和右旋：

  • 左旋：以某个节点为中心，右子节点成为新的根，原来的根成为新根的左子节点。
  • 右旋：以某个节点为中心，左子节点成为新的根，原来的根成为新根的右子节点。

旋转的示例：

1717565623756

map 和multimap

map与multimap在STL底层的区别在哪

std::map 和 std::multimap 是 C++ 标准模板库 (STL) 中的两种关联容器，它们的底层实现都基于红黑树，但它们在键值对的存储和处理上有一些重要的区别。

主要区别

  1. 唯一键 vs. 允许重复键：
    • std::map：存储唯一的键值对，每个键只能出现一次。
    • std::multimap：允许存储重复的键，每个键可以对应多个值。
  2. 插入操作：
    • std::map：如果插入具有相同键的元素，插入操作将失败，或者替换已有元素的值。
    • std::multimap：可以插入具有相同键的多个元素。

底层实现的共同点

  • 红黑树：两者都使用红黑树作为底层数据结构，以保持键值对的有序性和操作的对数时间复杂度。
  • 平衡和旋转：红黑树通过颜色标记和旋转操作保持树的平衡，这在 std::map 和 std::multimap 中是相同的。

底层实现的不同点

  • 处理重复键

    ：

    • std::map：红黑树中的每个节点包含唯一的键值对。插入时，如果键已存在，则不插入新元素（或者替换旧值，具体行为取决于插入方法）。
    • std::multimap：红黑树中的节点可以包含具有相同键的多个键值对。插入时，总是插入新的节点，即使键已存在。

C的前置和后置++

对于迭代器和其他模板对象使用前缀形式 (++i) 的自增, 自减运算符.，理由是 前置自增 (i) 通常要比后置自增 (i) 效率更高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//一起来看看源码

class Age   
	{   
	public:   
	  
	    Age& operator++() //前置++   
	    {   
	        ++i;   
	        return *this;   
	    }   
	  
	    const Age operator++(int) //后置++   
    {   
	        Age tmp = *this;   //tmp是一个临时对象，会造成一次构造函数和一次析构函数的额外开销。
	        ++(*this);  //利用前置++   
	        return tmp;   
	    }   
	  
	    Age& operator=(int i) //赋值操作   
	    {   
	        this->i = i;   
	        return *this;   
	    }   
	  
	private:   
	    int i;   
	};

1.返回值类型的区别

前置的返回类型是（引用）Age&，后置的返回类型const Age（临时对象）。这意味着，前置返回的是左值，后置返回的是右值。

2.形参的区别

前置没有形参，而后置有一个int形参，但是该形参也没有被用到。很奇怪，难道有什么特殊的用意？
其实也没有特殊的用意，只是为了绕过语法的限制。
前置与后置的操作符重载函数，函数原型必须不同。否则就违反了“重载函数必须拥有不同的函数原型”的语法规定。

3.代码实现的区别

前置++的实现比较简单，自增之后，将this返回即可。需要注意的是，一定要返回this。

后置++的实现稍微麻烦一些。因为要返回自增之前的对象，所以先将对象拷贝一份，再进行自增，最后返回那个拷贝。

4.效率的区别

map 、set、multiset、multimap

hashtable

STL 中并没有直接提供 hashtable 这个容器，但在 C++11 及之后的标准库中提供了基于哈希表实现的无序关联容器，包括 std::unordered_map、std::unordered_set、std::unordered_multimap 和 std::unordered_multiset。这些容器实际上是哈希表的实现。

数据结构复习与理解

1717566101857

上图就是一个散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。但是当关键字数量比较大的时候，难免就会造成一个问题，就是不一样的关键字隐射到同一个地址上，这样就造成了一个问题，就是hash冲突。那么如何解决呢？

冲突解决方法

线性探测

当前项目冲突，就线性向后搜索，直到找到一个可以存放的位置，该方法复杂度较高。该方法会导致主集团(primary clustering)的问题，即多数的冲突会导致数据在array中较为集中的排列。

二次探测

当冲突时，向后搜索1717566947647

等位置，为了消除每次计算时需要计算二次函数，进行如下变换

1717566958747

开链(seperate chaining)

每个array的位置上，维护一个list，每次通过hash function得到array的位置，在该位置上的list进行插入、搜寻和删除。list够短时，这些操作效率是可以接受的。
STL中就是用的这种方法。

hashtable的桶(buckets)和节点(nodes)

每个hash table表格内的元素为桶子，一就是说一个元素维护的是一桶节点。

这样表述意思是说：哈希表中的每个单元，有可能是一” 桶 “元素。

1717567534250

哈希表的节点定义为：

1
2
3
4
5
6

template <class Value>
struct __hashtable_node {
    __hashtable_node *next; // 指向下一个节点的指针
    Value val; // 节点的值
};

需要注意的是，bucket 维护的链表，并不使用 STL 的 list，而是自行维护节点。但是哈希表，也就是 bucket 的聚合体，以 STL 的 vector 完成，以便有动态扩充能力。

hashtable 的迭代器

hashtable 的迭代器处理维持当前指向的 bucket 的节点的关联，还需要维持与整个 hash 表的关联。
这样前进操作从当前节点出发，通过节点的 next 指针访问下一个节点；

如果当前节点恰好是当前 bucket 的尾端，则需要利用与 hash 表的关联跳转到下一个 bucket 上。

由于 hashtable 迭代器是一个正向迭代器，所以没有后退操作。

https://guomw.net/posts/3225459827/

其他

一般比较常用的方法有开放地址法：（内容来自百度百科）

\1. 开放寻址法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

1.1. di=1,2,3，…，m-1，称线性探测再散列；顺序查看表的下一单元，直至找到某个空单元，或查遍全表。

1.2. di=12,-12,22,-22，⑶2，…，±（k)2,(k<=m/2）称二次探测再散列；在表的左右进行跳跃式探测。

1.3. di=伪随机数序列，称伪随机探测再散列。根据产生的随机数进行探测。

2 再散列法：建立多个hash函数，若是当发生hash冲突的时候，使用下一个hash函数，直到找到可以存放元素的位置。

3 拉链法（链地址法）：就是在冲突的位置上简历一个链表，然后将冲突的元素插入到链表尾端，

4 建立公共溢出区：将哈希表分为基本表和溢出表，将与基本表发生冲突的元素放入溢出表中。

底层的hashMap是由数组和链表来实现的，就是上面说的拉链法。首先当插入的时候，会根据key的hash值然后计算出相应的数组下标，计算方法是index = hashcode%table.length，（这个下标就是上面提到的bucket），当这个下标上面已经存在元素的时候那么就会形成链表，将后插入的元素放到尾端，若是下标上面没有存在元素的话，那么将直接将元素放到这个位置上。

当进行查询的时候，同样会根据key的hash值先计算相应的下标，然后到相应的位置上进行查找，若是这个下标上面有很多元素的话，那么将在这个链表上一直查找直到找到对应的元素。

迭代器底层和失效的原因

线程安全问题

静态类型转换

在 C++ 中，static_cast<T*> 是一种类型转换操作符，用于进行静态类型转换。静态转换是一种在编译时期进行的转换，主要用于转换相关类型之间的指针或引用关系，例如将基类指针或引用转换为派生类指针或引用。它具有以下特点和用途：

  1. 用法：
    • static_cast<T*>(expression) 表示将 expression 转换为类型 T*。其中 T 可以是任意类型，包括基本数据类型、指针、引用、类类型等。
  2. 转换的情况：
    • 类型之间必须存在直接或间接的转换关系。
    • 安全性由程序员保证，编译器不会检查类型转换的合法性。

3.转换示例：

1
2
3
4
5
6
7
8
9
10
11
12
// 示例 1：基本数据类型转换
double d = 3.14;
int i = static_cast<int>(d); // d 被转换为 int，结果是 3

// 示例 2：指针类型转换
Base* basePtr = new Derived();
Derived* derivedPtr = static_cast<Derived*>(basePtr); // Base* 转换为 Derived*

// 示例 3：引用类型转换
Base baseObj;
Derived& derivedRef = static_cast<Derived&>(baseObj); // Base& 转换为 Derived&

4.适用场景：

  • 对于基本数据类型的转换，static_cast 可以用于显式转换。
  • 在类层次结构中，static_cast 可以进行父类指针或引用向子类指针或引用的转换，前提是安全的向下转型（即转换后可以安全使用）。

5.不适用场景：

  • 不能用于类型之间不存在转换关系的转换。
  • 不能用于在指针或引用之间进行动态类型检查的类型转换。

总之，static_cast<T*> 是一种在编译时进行的类型转换操作符，用于执行程序员明确知道安全的类型转换

 Comments
Comment plugin failed to load
Loading comment plugin
  1. 1. 加油
  2. 2. STL
  3. 3. 六大部件
  4. 4. 内存空间的管理
  5. 5. 一、STL的介绍
  6. 6. 二、空间配置器详解
  7. 7. 三、各种容器的特点和适用情况
    1. 7.0.1. 无序容器的设计目的
    2. 7.0.2. 具体使用场景
    3. 7.0.3. 关联式容器的优势
  8. 7.1. 序列式容器
  • 8. 四、各种容器的底层机制和常见面试题
    1. 8.1. traits技术
    2. 8.2. 指针和迭代器的区别
      1. 8.2.1. 指针
      2. 8.2.2. 区别总结
    3. 8.3. RAII
    4. 8.4. vector
      1. 8.4.0.1. vector 扩容为什么要以1.5倍或者2倍扩容?
      2. 8.4.0.2. vector中的size和capacity的区别
      3. 8.4.0.3. vector中的reserve和resize的区别
    5. 8.4.1. 1. 减少内存分配次数
    6. 8.4.2. 2. 平衡内存浪费和重新分配成本
    7. 8.4.3. 3. 避免时间复杂度过高
    8. 8.4.4. 4. 成倍增长的选择
  • 8.5. list
    1. 8.5.1. find()和find_if
    2. 8.5.2. find_if
    3. 8.5.3. 功能和用法
    4. 8.5.4. 函数原型
    5. 8.5.5. 示例
      1. 8.5.5.1. 示例 1：查找第一个大于 10 的元素
    6. 8.5.6. 总结
  • 8.6. map
    1. 8.6.1. 核心操作
    2. 8.6.2. 红黑树的基本性质
    3. 8.6.3. 插入操作中的调整规则
    4. 8.6.4. 删除操作中的调整规则
    5. 8.6.5. 旋转操作
  • 8.7. map 和multimap
    1. 8.7.1. 主要区别
    2. 8.7.2. 底层实现的共同点
    3. 8.7.3. 底层实现的不同点
  • 8.8. C的前置和后置++
  • 8.9. map 、set、multiset、multimap
  • 8.10. hashtable
    1. 8.10.1. 数据结构复习与理解
    2. 8.10.2. 冲突解决方法
    3. 8.10.3. 线性探测
    4. 8.10.4. 二次探测
  • 8.11. 开链(seperate chaining)
  • 8.12. hashtable的桶(buckets)和节点(nodes)
    1. 8.12.1. hashtable 的迭代器
    2. 8.12.2. 其他
  • 8.13. 迭代器底层和失效的原因
  • 8.14. 线程安全问题
  • 8.15. 静态类型转换
    • © 2020 - 2025    明昧
    Powered by Hexo & Theme Keep
    Unique Visitor Page View
    1. 1. 加油
    2. 2. STL
    3. 3. 六大部件
    4. 4. 内存空间的管理
    5. 5. 一、STL的介绍
    6. 6. 二、空间配置器详解
    7. 7. 三、各种容器的特点和适用情况
      1. 7.0.1. 无序容器的设计目的
      2. 7.0.2. 具体使用场景
      3. 7.0.3. 关联式容器的优势
    8. 7.1. 序列式容器
  • 8. 四、各种容器的底层机制和常见面试题
    1. 8.1. traits技术
    2. 8.2. 指针和迭代器的区别
      1. 8.2.1. 指针
      2. 8.2.2. 区别总结
    3. 8.3. RAII
    4. 8.4. vector
      1. 8.4.0.1. vector 扩容为什么要以1.5倍或者2倍扩容?
      2. 8.4.0.2. vector中的size和capacity的区别
      3. 8.4.0.3. vector中的reserve和resize的区别
    5. 8.4.1. 1. 减少内存分配次数
    6. 8.4.2. 2. 平衡内存浪费和重新分配成本
    7. 8.4.3. 3. 避免时间复杂度过高
    8. 8.4.4. 4. 成倍增长的选择
  • 8.5. list
    1. 8.5.1. find()和find_if
    2. 8.5.2. find_if
    3. 8.5.3. 功能和用法
    4. 8.5.4. 函数原型
    5. 8.5.5. 示例
      1. 8.5.5.1. 示例 1：查找第一个大于 10 的元素
    6. 8.5.6. 总结
  • 8.6. map
    1. 8.6.1. 核心操作
    2. 8.6.2. 红黑树的基本性质
    3. 8.6.3. 插入操作中的调整规则
    4. 8.6.4. 删除操作中的调整规则
    5. 8.6.5. 旋转操作
  • 8.7. map 和multimap
    1. 8.7.1. 主要区别
    2. 8.7.2. 底层实现的共同点
    3. 8.7.3. 底层实现的不同点
  • 8.8. C的前置和后置++
  • 8.9. map 、set、multiset、multimap
  • 8.10. hashtable
    1. 8.10.1. 数据结构复习与理解
    2. 8.10.2. 冲突解决方法
    3. 8.10.3. 线性探测
    4. 8.10.4. 二次探测
  • 8.11. 开链(seperate chaining)
  • 8.12. hashtable的桶(buckets)和节点(nodes)
    1. 8.12.1. hashtable 的迭代器
    2. 8.12.2. 其他
  • 8.13. 迭代器底层和失效的原因
  • 8.14. 线程安全问题
  • 8.15. 静态类型转换