STL笔记

发表于 更新于 分类于

2024.4.8

1
2
3
void _construct(T1* p, const T2& value){
    new(p) T1(value);
}

new(p) T1(value);使用的是placement new运算符来构造对象，不会动态分配内存，而是在给定的地址（指针p指向的位置）上构造一个类型为T1的对象，并使用T2类型的value来初始化他。

1
2
3
void _deallocat(T* buffer){
::operater delete (buffer);
}

::operater delete是一个全局作用的删除函数，用于释放new动态分配的内存。

operater delete是一个预定义的全局作用的删除函数，当我们调用delete函数时，在底层实现中该函数调用了operater delete函数

这种释放方式只是释放指定的地址的内存（两个版本，一个是单个的释放，只有一个参数(地址)，另一个版本是两个参数（地址+大小)）

它不会释放对象的内存，对象的内存释放需要析构函数，析构函数只是释放对象的内存，对于动态分配给对象的空间不会通过析构函数直接释放，除非显式释放（自己写一个）。

举例子说:我有一个对象中有一个指针，我给指针动态分配了一些内存，当调用析构函数时只会释放指针，不会释放指针指向那块空间。

结构体的定义可以写在类里

typedef的作用是为已有类型创建一个别名，可以使用别名进行已有类型的操作。

全文是这样的：

1
2
3
4
5
6
7
8
9
10
template <calss T> 
inline T* _allocate(ptrdiff_t size, T*){
set_new_handler(0);
T* tem=(T*)(::operator new((size_t)(size*sizeof(T))));
if(tem==0){
cerr<<"out of memory"<<endl;
exit(1);
}
return tem;
}

set_new_handler(0);这一行意为取消先前设置的内存分配失败处理函数

这里留有疑问，前面没有设置对于内存分配失败的处理函数

可能是为了当分配失败时将后面的tem设置为0

1
2
3
4
template <calss T>
inline void _deallocate(T* buffer){
::operator delete(buffer);
}
1
void deallocate(pointer p,ssize_type n){ _deallocate(p)};

这里有一个问题，如果p是一个指向大块空间的指针的话，只释放了指针p，那剩余的空间是不是造成了内存泄露

2024.44.10

trivial destructor 中文意思(直译:琐碎的爆炸装置)哈哈哈)gpt翻译是平凡析构函数，意思是：

当一个析构函数是用户未定义或者是使用的编译器默认的析构函数或被显式声明为“=default”时我们称这个析构函数是trivial的析构函数

1
2
=default 是 C++11 中的一个特殊语法,只能用于特定的成员函数：如拷贝构造，析构，构造，操作符重载
用法：函数() =default;

如果有的析构函数什么事也不做，用一个词”无关痛痒”,那么对[first ,last)的析构就不需要做任何事情，当这个范围很大的时候还去一个一个调用对应对象的析构函数很浪费时间，降低效率。因此在进行对象的析构时会利用value_type()对对象的类型进行判断，再利用

1
type_traits<T>看是否对应的析构函数是trivial的，如果是__ture_type,则什么也不做就结束，如果是__false_type,再循环遍历整个范围进行调用对应析构函数(第一个版本的destory)

对Alloc的包装

1
2
3
4
5
6
7
8
template<class T,class Alloc>
    class simple_alloc{
        public:
        static T *allocate(size_t);
        static T *allocate(void);
        static void dellocate(T* ,size_t);
        static void deallocate(T*);
    }

一个疑问:下面两种分配方式的区别

1
2
3
4
typedef simple_alloc<T,Alloc> data_alloctor;
typedef simple_alloc<t*,Alloc> map_alloctor;
data_alloctor::allocate(n);//配置n个元素
map_alloctor::allocate(n);//配置n个节点

data_alloctor::allocate(n);//配置n个元素分配出来的是T对象

map_alloctor::allocate(n);//配置n个节点分配出来的是指向T类型数据的指针，整个指针所指向的地址是后面再去初始化的

gpt的例子

1
2
T* data_ptr = data_alloctor::allocate(5); // 分配 5 个 T 类型的对象
T** map_ptr = map_alloctor::allocate(5); // 分配 5 个指向 T 类型对象的指针

可能有些绕，上面的是分配的空间赋值给了一个指针，说的可能不太对，让那个data_ptr指向我们分配的地址

下面的分配是分配出一个指针赋值给了一个二级指针

2024.4.17

__STL_BEGIN_NAMESPACE是c++中定义命名空间的语句

与之配合使用的是__STL_END_NAMESPACE

2024.4.22

1
void *realloc(void *ptr,size_t size);

作用是重新分配内存，有以下几种情况

  1. 如果 ptr 是空指针，那么 realloc 就等同于 malloc(size)，直接分配 size 大小的内存块，并返回指向该内存块的指针。
  2. 如果 size 是 0，并且 ptr 不是空指针，那么 realloc 的行为类似于 free(ptr)，即释放 ptr 指向的内存，并返回空指针。
  3. 如果 ptr 不是空指针，并且 size 不为 0，那么 realloc 尝试重新分配 ptr 指向的内存空间为 size 大小。如果成功，返回指向重新分配后内存块的指针；如果失败，返回空指针，原来的内存块不会被修改。
  4. 如果 ptr 不是空指针，并且 size 小于等于原来分配的大小，那么 realloc 可能会缩小内存块，返回指向原来内存块的指针。这种情况下，原来的数据可能会被截断。
  5. 如果 ptr 不是空指针，并且 size 大于原来分配的大小，那么 realloc 会尝试扩展内存块。如果在原内存块后有足够的连续空间，那么就在原来的内存块上扩展；否则会重新分配一个足够大的内存块，将原数据复制过去，释放原来的内存块，并返回指向新分配内存的指针。
1
2
3
4
#include<cstddef>//提供了一些与指针和偏移量相关的常量和类型，例如"std::ptrdiff_t"
#include<cstdlib>//包含了一些与C标准库相关的函数和宏定义，例如内存分配函数'malloc()'和'free()'
#include<cstdio>//包含了一些与C标准I/O相关的函数，例如文件操作函数'fopen()'和'fclose()'

1
2
#define __STL_BEGIN_NAMESPACE namespace yw_stl{
#define __STL_END_NAMESPACE }
  • __STL_BEGIN_NAMESPACE 被定义为 namespace yw_stl{，意味着每当代码中出现 __STL_BEGIN_NAMESPACE 时，它都会被替换为 namespace yw_stl{。
  • __STL_END_NAMESPACE 被定义为 }，意味着每当代码中出现 __STL_END_NAMESPACE 时，它都会被替换为 }。

作用是定义命名空间用的。

2024.4.23

1
2
3
4
template<class _T1,class _T2>
inline void _Construct(_T1* __p,const _T2 __value){
new((void*)__p) _T1(__value);
}

之前提到过，一种特殊的new函数，placement new 在给定内存上创建对象，_T1(__value)是构造函数

_T1是一个类。

1
2
3
4
5
6
7
8
struct __type_traits {
    typedef __true_type this_dummy_member_must_be_first;//无实际作用，强调放在第一位的占位符
    typedef __false_type has_trivial_default_constructor;//有平凡构造函数
    typedef __false_type has_trivial_copy_constructor;//有平凡拷贝构造函数
    typedef __false_type has_trivial_assignment_operator;//有平凡的赋值操作符
    typedef __false_type has_trivial_destructor;//有平凡的析构函数
    typedef __false_type is_POD_type;//是POD类型
};

这个与视频课里的对象释放时的方式有关，如果是“无关痛痒”的函数，那就不做任何事情就好了。

POD：Plain Old Data，简单的数据类型（整数、浮点数、指针等）。

跟着卡码网写容器

2024.9.2

list部分

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

int main() {
	std::list<int> myList = {1,2,3,4,5,6,7 };
	myList.push_front(1);//头加
	myList.push_back(2);//尾加
	std::cout << myList.front() << std::endl;//访问第一个元素
	std::cout << myList.back() << std::endl;//访问最后一个元素
	//迭代器遍历方式
	for (auto it = myList.begin(); it != myList.end(); ++it) {//auto 这里是 std::list<int>::iterator
		std::cout << *it << " ";
	}
	std::cout << std::endl;
	myList.pop_front();//头减
	myList.pop_back();//尾减
	//范围基for循环
	for (auto& element : myList) {
		std::cout << element << " ";
	}
	std::cout << std::endl;
	return 0;

}

对于list的图解

蓝色矩形：堆内存

红色矩形：栈内存

2024.9.4

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

int main() {
	std::deque<int> myDeque = {1,2,3,4,5,6,7 };
	myDeque.push_front(1);//头加
	myDeque.push_back(2);//尾加
	std::cout << myDeque.front() << std::endl;//访问第一个元素
	std::cout << myDeque.back() << std::endl;//访问最后一个元素
	//迭代器遍历方式
	for (auto it = myDeque.begin(); it != myDeque.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
	myDeque.pop_front();//头减
	myDeque.pop_back();//尾减
	//范围基for循环
	for (auto& element : myDeque) {
		std::cout << element << " ";
	}
	std::cout << std::endl;
	return 0;

}

链表能做的，deque也能做

  • 无论是push_front还是push_back, 都需要判断当前数组是否已满, 已满的话将其扩容为原容量的2倍, 将原来的数组元素复制到新的数组中。
  • push_front需要将frontIndex自减后在frontIndex位置插入, frontIndex自减后需要加上capacity后对capacity取模, 这使得如果frontIndex为负, frontIndex将指向从数组末尾
  • push_back直接在backIndex位置插入, 然后将backIndex自增, backIndex自增后需要对capacity取模, 这使得如果backIndex越界, backIndex将指向从数组开始的位置

这里的deque并不是stl实现的deque，stl实现的deque是靠多个分段数组连接制成，

这里的deqeu只用一个数组，扩充时是像vector翻倍复制一样，我觉得不好。

但是也有可以学到的东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//打印deque中的元素
void printElements()const {
    size_t index = frontIndex;
    for (size_t i = 0; i < size; ++i) {
        std::cout << elements[index] << " ";
        index = (index + 1) % capacity;
    }
    //这里注意，下面注释掉的循环输出是有问题的，当容器满了时就会直接跳出循环
    //因为满的时候两个索引都指向一个位置
    //while(index!=backIndex){
    //    std::cout<<elements[index]<<" ";
    //    index=(index+1)%capacity;
    //}
    std::cout << std::endl;
}

2024.9.7

HashTable

2024.9.8

红黑树：自动平衡二叉树，节点附加一种属性表示节点颜色，非红即黑。

有如下特性：

  • 节点颜色：非红即黑
  • 根节点颜色：根节点是黑色的
  • 叶子节点（NIL节点）颜色：所有叶子节点（NIL节点）都是黑色
  • 相邻节点颜色：如果一个节点是红的，则它的两个子节点都是黑的
  • 路径黑高度相等：从任意节点到其每个叶子节点的简单路径上，黑色节点数量相同。

这些特性确保了红黑树的关键性质，如再最坏的情况下查找、插入和删除操作时间复杂度都是O（log n）

红黑树工作流程：

  1. 插入新节点

    • 将新节点插入到红黑树中，新节点颜色初始化为红色。

  2. 检查红黑树性质：

    1. 如果新插入的节点是根节点，仅将其颜色改为黑色即可满足所有性质。
    2. 如果新节点的父节点是黑色，不违反红黑树的性质，不需要做额外的操作。
    3. 如果新节点的父节点是红色，就需要进行一些调整来修复树的特性，因为这违反了性质：红色节点的子节点必须是黑色。

  3. 调整红黑树：如果新节点的父节点是红色的，有以下几种情况需要处理：

    1. 父节点是爷爷节点的左孩子
      1. 叔叔节点为红色
        1. 更改叔叔节点和父节点为黑色
        2. 将爷爷节点设置为红色
        3. 以爷爷节点为目标继续判断是否需要调整
      2. 叔叔节点为黑色或者不存在
        1. 如果新节点是父节点的右孩子，将操作的目标节点变为其父亲，并左旋
        2. 将操作节点（可能因为上一步的右旋，操作节点发生了变化）设为黑色，爷爷节点设为红色
        3. 右旋爷爷节点
    2. 父亲节点是爷爷节点的右孩子
      1. 叔叔节点为红色
        1. 更改叔叔节点和父节点为黑色
        2. 将爷爷节点设为红色
        3. 以爷爷节点为目标继续判断是否需要调整
      2. 叔叔节点为黑色或者不存在
        1. 如果新节点是父节点的左孩子，将操作目标节点变为其父亲，并右旋
        2. 将操作节点（可能因为上一步的右旋，操作节点发生了变化）设为褐色，爷爷节点设为红色
        3. 左旋爷爷节点

能需要向上递归地调整，直到根节点，或者直到不再违反红黑树的性质为止。

旋转操作解释：

  • 左旋：节点x的右孩子y变成x的父节点，x变成了y的左孩子。如果y有一个左孩子，它会变成x的右孩子。
  • 右旋：与左线相反，节点x的左节点y变成x的父节点，x变成了y的右孩子。如果y有一个右孩子，它会变成x的左孩子。

每次插入的时间复杂度为O(log n),因为红黑树的高度保持在log2(n)以内。

图示说明如下操作的插入过程:

1
2
3
4
5
6
7
8
RedBlackTree<int> mySet;
// 插入元素
mySet.insert(42);
mySet.insert(63);
mySet.insert(10);
mySet.insert(4);
mySet.insert(30);
mySet.insert(36);
  1. 插入42(红)为根节点, 将其调整为黑色
  2. 插入21(红)为42(黑)的左孩子, 无需调整
  3. 插入63(红)为42(黑)的右孩子, 无需调整
  4. 插入10(红)为21(红)的左孩子, 调整如下:
    1. 由于父亲和叔叔也是红色, 直接将父亲和叔叔变为黑色
    2. 将爷爷42变为红色
    3. 重新将根节点42变为黑色
  5. 插入4(红)为10(红)的左孩子, 调整如下:
    1. 由于其没有叔叔节点且父节点为红, 将父节点变黑, 爷爷节点变红
    2. 右旋爷爷节点
  6. 插入30(红)为21(红)的右孩子, 调整如下:
    1. 父节点和叔叔节点为红, 直接将其边黑
    2. 爷爷10节点变红
  7. 插入36(红)为30(红)的右孩子, 调整如下:
    1. 由于其没有叔叔节点且父节点为红, 将父节点变黑, 爷爷节点变红
    2. 左旋爷爷节点

2024.9.11

set

底层用红黑树实现，算是红黑树的一层封装

特性：

  • 唯一性：std::set中不允许存储重复的元素，每个元素都是唯一的。插入重复元素的操作会被忽略。

  • 有序性：std::set中的元素是按照升序进行排序的。这种排序是通过红黑树的自平衡性质实现的，保证了插入、删除等操作的高效性。

  • 插入元素：使用insert成员函数可以将元素插入到集合中，如果元素已经存在，则插入会呗忽略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<set>
int main() {
	std::set<int> mySet;
	mySet.insert(42);
	mySet.insert(21);
	mySet.insert(63);
	mySet.insert(21);

	mySet.erase(63);

	auto it = mySet.find(42);
	if (it != mySet.end()) {

	}
	for (const int& element : mySet) {
		std::cout << element << " ";
	}
	std::cout << std::endl;
	return 0;
}

map

特性：

  • 键值对存储：std::map通过键值对的形式存储数据，其中每个键都是唯一的，并且与每一个值相关联。
  • 自动排序：std::map内部使用一种平衡二叉搜索树（通常是红黑树）来存储元素，这使得元素根据键值自动排序。
  • 元素唯一性：在std::map中，键必须是唯一的。如果尝试插入一个已经存在的键，插入操作将是失败。
  • 直接访问：可以使用键值直接访问std::map中的元素，这提供了高效的查找能力。
  • 灵活的元素操作：std::map提供了丰富的元素操作，包括插入、删除、查找等。
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
32
33
34
#include<iostream>
#include<map>
int main() {
	std::map<int, int> myMap;

	myMap.insert({ 1,100 });
	myMap[2] = 200;//使用下标操作符直接插入或修改
	myMap.insert({ 3,300 });

	std::cout << "Element with key 2:" << myMap[2] << std::endl;
	//迭代查询
	std::cout << "Iterating over elements:" << std::endl;
	for (const auto& pair : myMap) {
		std::cout << pair.first << "=>" << pair.second << std::endl;
	}
	//查找元素
	auto search = myMap.find(2);//查找键为2的元素
	if (search != myMap.end()) {
		std::cout << "Found element with key 2:" << search->second << std::endl;
	}
	else {
		std::cout << "Element with key 2 not found." << std::endl;
	}
	//删除元素
	myMap.erase(2);//删除键为2的元素
	std::cout << "Element with key 2 erased." << std::endl;

	//再次遍历，查看删除效果
	std::cout << "Iterator over elements ahter deletion:" << std::endl;
	for (const auto& pair : myMap) {
		std::cout << pair.first << "=>" << pair.second << std::endl;
	}
	return 0;
}

2024.9.13

unordered_map的性能

  1. 访问性能 在理想情况下，访问元素（增删查）的时间复杂度为O（1）。但是，如果发生哈希冲突，这些操作的性能可能会降至O（n），其中n是同一个哈希桶中元素的数量。
  2. 冲突解决，unordered_map通过链表（活其他数据结构，具体取决于实现）解决哈希冲突，当多个元素被映射到同一个哈希桶时，他们将被存储在一个链表中。
  3. 加载因子和重哈希，加载因子是存储在哈希表中的元素数量与哈希桶数量的比率。当加载因子超过某个阈值时（通常是1），unordered_map将进行重哈希操作，以增加哈希桶的数量并重新分配元素，以保持操作的高效性。
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
32
#include<iostream>
#include<string>
#include<unordered_map>

int main() {
	std::unordered_map<std::string, int> wordCount;
	//插入元素
	wordCount["apple"] = 1;//方法一：使用下标运算符超乳或修改元素
	wordCount.insert({ "banana",2 });//方法二：使用哦个insert函数插入元素
	wordCount.emplace("cherry", 3);//方法三：使用emplace直接构造元素，避免临时对象的构造，效率更高
	//访问元素
	std::cout << "apple count:" << wordCount["apple"] << std::endl;
	std::cout << "banana count:" << wordCount.at("banana") << std::endl;

	//检查元素是否存在
	if (wordCount.find("cherry") != wordCount.end()) {
		std::cout << "chreey found" << std::endl;
	}
	//更新元素
	wordCount["apple"] = 5;//更新apple的计数

	//删除元素
	wordCount.erase("banana");//删除键为“banana”的元素

	//遍历unordered_map
	for (const auto& pair : wordCount) {
		std::cout << pair.first << ":" << pair.second << std::endl;
	}
	//获取unordered_map的大小
	std::cout << "Size of unordered_map:" << wordCount.size() << std::endl;
	return 0;
}

multimap

特性：键的多重性：与std::map不同，std::multimap允许两个或多个元素拥有相同的键。这使得multimap非常适合于那些需要根据键将多个值分组的场景。

元素的有序性：std::multimap中的元素根据键自动排序。默认情况下，它使用std::less来比较键，这意味着元素会按照键的升序排序。也可自定义比较函数，实现不同的排序逻辑。

基于红黑树实现：带哦是STL实现使用平衡二叉搜索树（如红黑树）来实现multimap，这确保了即使在最坏的情况下，大部分操作（如插入、查找和删除）的时间复杂度也是对数的。

不支持直接修改键：由于multimap中的元素是根据键排序的，直接修改键可能会破坏容器的内部顺序。如果需要修改键，通常的做法是删除旧元素并插入一个新元素。

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<map>
int main() {
	std::multimap<int, std::string> mm;

	mm.insert(std::make_pair(1, "Apple"));
	mm.insert(std::make_pair(1, "Avocado"));
	mm.insert(std::make_pair(2, "Banana"));
	mm.insert(std::make_pair(2, "Cherry"));

	std::cout << "Multimap elements:" << std::endl;
	for (const auto& element : mm) {
		std::cout << element.first << "=>" << element.second << std::endl;
	}

	//查找键为1的所有元素
	auto range = mm.equal_range(1);//获取一个范围，包含所有键为1的元素
	std::cout << "Elements with key 1:" << std::endl;
	for (auto it = range.first; it != range.second; ++it) {
		std::cout << it->first << "=>" << it->second << std::endl;
	}
	//删除键为2的所有元素
	mm.erase(2);

	//遍历multimap，查看删除操作的结果
	std::cout << "\nMultimap after erasing key 2:" << std::endl;
	for (const auto& element : mm) {
		std::cout << element.first << "=>" << element.second << std::endl;
	}
	return 0;
}

2024.9.14

priority_queue

堆的工作原理：

结构特性：堆是一个完全二叉树，这意味着除了最后一层外，每一层都是完全填满的，而最后一层的节点则尽可能地集中在左边。

堆性质：在一个大根堆中，每个节点的值都大于或等于其子节点的值，根节点的值时堆中最大值。小根堆则相反。

优先队列中有一个堆一个其他容器（Vetctor、deque、list之类）