C++ STL_Note - Hanni Rio’s Blog

关于lower_bound和upper_bound

std::lower_bound：在有序序列中查找第一个大于或等于给定值的元素的位置。如果序列中存在等于给定值的元素，则返回第一个等于给定值的元素的位置；如果序列中不存在等于给定值的元素，则返回第一个大于给定值的元素的位置。如果所有元素都小于给定值，则返回序列的结束位置。

std::upper_bound：在有序序列中查找第一个大于给定值的元素的位置。如果序列中存在等于给定值的元素，则返回第一个大于给定值的元素的位置；如果序列中不存在等于给定值的元素，则返回第一个大于给定值的元素的位置。如果所有元素都不小于给定值，则返回序列的结束位置。

⚠️：如果要取得下标的时候，需要用static_cast<int>对迭代器进行数据类型转换

⚠️：底层原理是用二分查找，所以时间复杂度是O(log N)

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> nums = {-9, 1100, 43, 4, 300, 20};
    sort(nums.begin(), nums.end());
    //sort后数组为： -9 4 20 43 300 1100
    auto left = lower_bound(nums.begin(), nums.end(), 20);
    auto right = upper_bound(nums.begin(), nums.end(), 1000);
    cout <<"下标是:"<<static_cast<int>(left - nums.begin())<< " 数值是 ：" << *left << endl;
    cout <<"下标是:"<<static_cast<int>(right - nums.begin())<< " 数值是 ：" << *right << endl;
    //下标是:2 数值是 ：20
    //下标是:5 数值是 ：1100
    return 0;
}

关于unique

std::unique 将重复的元素移动到范围的末尾，并返回一个新的迭代器，指向去重后的元素序列的尾部。被移动到末尾的重复元素并没有真正被删除，如果需要，可以使用容器的 erase 成员函数来删除这些重复元素。

⚠️一定要是有序数组才可以用unique ❕

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> nums = {100, 90, 2, 1000, 99, 2, 89, 2, 90, 2222, 0, -199};
    sort(nums.begin(), nums.end());           //这个步骤是最重要的，一定要是有序数组才能用unique
    auto last = unique(nums.begin(), nums.end());   //返回去冲后末尾位置的迭代器
    nums.erase(last, nums.end());              // 删除末尾的剩余元素
    for(auto x : nums){
        cout << x << " ";
    }
    return 0;
}
//-199 0 2 89 90 99 100 1000 2222

关于sort

sort 是 C++ 标准库 <algorithm> 头文件中提供的函数，用于对数组或容器中的元素进行排序。它可以接受两个迭代器参数，表示排序范围的起始和结束位置。通常情况下，sort 函数会按照默认的升序方式对元素进行排序。

在这个代码示例中，sort 被用来对字符串进行排序。字符串是一个字符序列，可以被当做容器来处理。因此，sort 函数可以直接对字符串进行排序，从字符串的起始位置 begin() 到结束位置 end()。

在对字符串排序后，原始的字符串内容会被改变，变成按照字典序排列的新字符串。

⬇️下面是一个演示，大致顺序是：标点符号 < 大写字母 < 小写字母

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "faslkhjglasioqahfjaxczlkjflqwasjfiasjopi";
    string t = "faksdasdjfalgkjsakfdaskfjkanakjfjcjzhjfhasf";
    string q = "AZfaskfjsocmBBB;;!!!cccaaaazzzz";
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    sort(q.begin(), q.end());
    cout << s << endl;
    cout << t << endl;
    cout << q << endl;
    return 0;
}
// aaaaaacffffghhiiijjjjjkklllloopqqsssswxz
// aaaaaaaacdddfffffffghhjjjjjjjkkkkkklnsssssz
// !!!;;ABBBZaaaaaccccffjkmosszzzz

关于unordered_set

unordered_set 是 C++ 标准库中的一种容器，用于存储不重复的元素集合。与 set 不同的是，unordered_set 使用哈希表来存储元素，因此元素的插入、删除和查找操作的平均时间复杂度为 O(1)。但是，由于哈希表的存储方式，unordered_set 中元素的顺序是不确定的。

unordered_set 的用法与 set 类似，但由于底层数据结构不同，unordered_set 提供了一些额外的方法和操作。例如，unordered_set 不提供 lower_bound、upper_bound 等方法，因为这些方法的实现需要有序容器的支持。

以下是 unordered_set 的基本用法示例：

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个空的 unordered_set
    std::unordered_set<int> mySet;

    // 插入元素
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(4);

    // 检查元素是否存在
    if (mySet.find(1) != mySet.end()) {
        std::cout << "1 is in the set" << std::endl;
    }

    // 删除元素
    mySet.erase(3);

    // 遍历元素
    for (int x : mySet) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

⚠️关于string类型

length() 和 size():

用于返回字符串的长度。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "Hanni Rio";
    string t = "dope boy right here";
    string y = "不打扰是我的温柔";      // 中文一个汉字占多个字节,这里一个汉字对应3字节
    cout << s.size() << endl;       // 9
    cout << t.length() << endl;     // 19
    cout << y.length() << endl;     // 24
    return 0;
}

substr():

用于提取子字符串。
参数是起始位置和子字符串的长度。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "Hanni Rio";
    string y = "不打扰是我的温柔";      // 中文一个汉字占多个字节,这里一个汉字对应3字节
    string z = s.substr(6,3);        // Rio
    string q = y.substr(18,6);       // 温柔
    cout << z << endl;
    cout << q << endl;
    return 0;
}

当你需要在一个字符串中查找特定子字符串的位置时，你可以使用 find() 和 rfind() 函数。这两个函数都返回子字符串在原始字符串中的位置索引，如果未找到则返回 string::npos。

find() 函数：
- find() 函数从字符串的开头开始搜索子字符串。
- 如果找到了子字符串，它返回第一次出现的位置索引。
- 如果未找到，则返回 string::npos，这是一个特殊的静态成员常量，表示未找到。
- 例如：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "Hanni Rio";
    size_t x = s.find("baby");
    if(x == string::npos) cout << "Not found" << endl;
    else cout << "Found" << endl;
    return 0;
}
//Not found

rfind() 函数：

rfind() 函数从字符串的末尾开始搜索子字符串。
如果找到了子字符串，它返回最后一次出现的位置索引。
如果未找到，则返回 string::npos。
例如：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string t = "Hanni Rio iiiii";
    size_t y = t.find("i"); // 4,记录第一次出现的
    size_t x = t.rfind("i"); //14,记录最后一次出现
    size_t z = t.find("z");
    if(z == string::npos) cout << "不存在z" << endl; // 不存在z
    cout << y << endl;
    cout << x << endl;
    return 0;
}

//在 C++ 中，size_t 是一种用于表示对象大小的无符号整数类型。使用 size_t 有几个好处：
//
//一致性：size_t 类型在 C++ 标准库中被广泛使用来表示容器的大小、字符串的长度等。因此，使用 size_t 可以保持与标准库的一致性。
//
//无符号性：size_t 是无符号整数类型，它可以表示大于等于 0 的整数值。对于表示对象大小或索引等非负整数的情况，无符号类型更加合适。
//
//足够大：size_t 在不同平台上的大小可能会有所不同，但通常足够大以容纳任何合理的对象大小。
//
//语义清晰：使用 size_t 可以使代码更加清晰和具有可读性，因为它明确表示了变量是用于表示大小的。
//
//因此，虽然 int 类型也可以用于表示对象大小，但为了保持一致性、避免符号问题并提高代码的可读性，建议在 C++ 中使用 size_t 类型来表示对象的大小。

erase():

用于删除指定位置的字符或子字符串。
参数是起始位置和要删除的长度。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string t = "We like to eat";
    t.erase(2,8);
    cout << t << endl;  // We eat
    return 0;
}

insert():

用于在指定位置插入字符或子字符串。
参数是插入位置和要插入的字符串。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string t = "Hello!";
    t.insert(5,",World");  // 往当前下标的前面插的
    cout << t << endl;    //Hello,World!
    return 0;
}

replace():

用于替换指定位置的字符或子字符串。
参数是起始位置、要替换的长度和替换的字符串。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string t = "Hello, World!";
    t.replace(7, 5, "everyone"); // 起始位置、要替换的长度和替换的字符串
    cout << t << endl;            // Hello, everyone!
    return 0;
}

append() 和 +=:

用于在字符串末尾添加字符或字符串。

push_back():

用于在字符串末尾添加单个字符。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string t = "Fuck";
    t.append(" Damnshine");  // append可以添加string类型
    t.push_back('!');     // push_back只能添加单个字符,char类型
    cout << t << endl;  // Fuck Damnshine!
    return 0;
}

关于Stack

stack 提供了以下几个基本操作：

push(g): 将元素 g 加入栈顶。
pop(): 移除栈顶元素。
top(): 访问栈顶元素。
empty(): 判断栈是否为空。
size(): 返回栈中元素的数量。

关于queue

queue 提供了以下几个基本操作：

push(g): 将元素 g 添加到队列的末尾。
pop(): 移除队列前端的元素。
front(): 访问队列前端的元素。
back(): 访问队列末尾的元素。
empty(): 判断队列是否为空。
size(): 返回队列中元素的数量。

关于deque

deque （双端队列）是一种非常灵活的容器，允许从两端进行高效的插入和删除操作。

#include<bits/stdc++.h>
using namespace std;
int main(){
    deque<int> d1;     // 空的deque
    deque<int> d2(5, 10);  // // 长度为5，每个元素初始化为10
    deque<int> d3(d2.begin(), d2.end());  // 用d2初始化d3
    //添加元素的操作
    d1.push_back(10);    // 在末尾添加元素
    d1.push_back(20);
    d1.push_front(30);
    d1.push_front(40);    // d1现在是 {40,30,10,20}
    d1.pop_back();        // 删除末尾元素 {40,30,10}
    d1.pop_front();       // 删除开头元素 {30,10}
    // 访问元素
    int front = d1.front();    // 访问头部元素 30
    int back = d1.back();      // 访问尾部元素 10
    int element = d1[1];       // 用下标访问 10
    cout << front << endl;
    cout << back << endl;
    cout << element << endl;
    bool isEmpty = d1.empty();    // 返回false
    size_t n = d1.size();     // 获取大小 2
    if(!isEmpty) cout << n << endl;
    d1.clear();              // 清空deque
    if(d1.empty()) cout << "队列已经被清空" << endl;
}
//10
//10
//2
//队列已经被清空

关于multiset

multiset 是 C++ 标准模板库（STL）中一个非常有用的容器，它提供了一种存储元素的方式，其中元素可以按照特定顺序自动排序，且允许存储重复元素。

特点：

自动排序：multiset 中的元素默认以升序排列，因为内部通常实现为一个平衡二叉搜索树（如红黑树）。
元素重复：与 set 不同，multiset 允许相等的元素存在多次。
只读键：multiset 中的元素一旦添加，就不能修改（因为它们是键），但可以删除后重新插入修改后的元素。

#include<bits/stdc++.h>
using namespace std;
int main(){
    multiset<int> ms1;   //空的multiset
    ms1.insert(1);
    ms1.insert(1);       // 插入元素的操作
    ms1.insert(2);
    for(auto num : ms1) cout << num << "  ";
    cout << endl;
    multiset<int> ms2 = {3, 3, 2, 2, 4};     // 会自动调整为升序排列
    for(auto num : ms2) cout << num << "  ";    // 2  2  3  3  4
    cout << endl;
    ms2.erase(2);     // 删除所有值为2的元素
    for(auto num : ms2) cout << num << "  ";   // 3  3  4
    cout << endl;
    ms2.erase(ms2.find(3));      // 删除一个值为3的元素
    for(auto num : ms2) cout << num << "  ";  // 3  4
    cout << endl;
    multiset<int> ms3 = {3,2,1,2,3,4,4,4,5,5};    // 自动调整为升序
    for(auto num : ms3) cout << num << "  ";    // 1  2  2  3  3  4  4  4  5  5
    cout << endl;
    auto it = ms3.find(3);        // 查找值为 3 的元素，返回指向第一个匹配元素的迭代器
    if(it != ms3.end()) cout << *it << endl;     //如果找得到就输出
    int count = (int)ms3.count(1);  // 计算值为1的元素的数量
    cout << "元素值为1的数量有：" << count << endl;
    if(!ms3.empty()){          // 判空条件
        cout << "size of multiset :"  << ms3.size() << endl;    //输出容器大小 size of multiset :10
    }
    return 0;
}

注意⚠️：

C++ 标准库中的 multiset 使用的是迭代器，这些迭代器是双向迭代器，而不是随机访问迭代器。这意味着不能直接使用减法操作来计算两个迭代器之间的距离。

在 multiset（以及 set、list 等）中，您不能像在 vector 或 deque 这样的容器中那样使用减法操作符来找到元素的索引，因为这些容器的迭代器不支持随机访问。

如果您希望获取特定元素（比如值为 3 的元素）的索引或位置，您需要遍历 multiset 并手动计数，直到找到该元素。下面是一个示例代码：

#include<bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> ms3 = {3, 2, 1, 2, 3, 4, 4, 5, 5};  // 自动调整为升序
    for(auto num : ms3) cout << num << "  ";
    cout << endl;
    auto it = ms3.find(3);  // 查找值为 3 的元素，返回指向第一个匹配元素的迭代器
    if (it != ms3.end()) {
        int index = 0;  // 用于记录位置的计数器
        for (auto itr = ms3.begin(); itr != it; ++itr) {
            ++index;  // 对每个元素进行计数，直到到达目标迭代器
        }
        cout << "Index of 3: " << index << endl;  // 输出元素 3 的索引
    }

    return 0;
}
// 1  2  2  3  3  4  4  5  5
// Index of 3: 3

关于容器迭代器🔁

在 C++ 标准模板库（STL）中，容器类提供了多种类型的迭代器，用于访问和操作其中的元素。这些迭代器非常类似于指针，允许程序员通过迭代器进行元素访问和范围遍历。以下是一些最常用的迭代器方法：

.begin() 和 .end()

.begin() 返回一个指向容器中第一个元素的迭代器。如果容器为空，返回的迭代器将等同于 .end() 返回的迭代器。
.end() 返回一个指向容器中最后一个元素之后的位置的迭代器。这不是一个有效的元素位置，而是用于表示容器的边界。在循环中，这通常用作循环结束的条件。

.rbegin() 和 .rend()

.rbegin() 返回一个反向迭代器，指向容器的最后一个元素。反向迭代器用于从容器的尾部向头部遍历。
.rend() 返回一个反向迭代器，指向容器第一个元素之前的位置。同 .end() 一样，这也不是一个有效的元素位置，而是用来表示容器反向遍历的终点。

⚠️注意⚠️：反向迭代器（如 reverse_iterator）的设计本质上已经颠倒了前进和后退的方向。这意味着，当你对反向迭代器使用递增操作符 ++ 时，迭代器实际上是在内部向容器的开始方向移动，即向前一个元素。相反，当使用递减操作符 -- 时，迭代器实际上是向容器的结束方向移动，即向后一个元素。

迭代器的使用

以下示例展示了如何使用这些迭代器：

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vec = {1,2,3,4,5};
    cout << "正向迭代: " << endl;
    for(auto it = vec.begin(); it != vec.end(); it++){
        cout << *it << "  ";
    }
    cout << endl;
    cout << "反向迭代: " << endl;
    for(auto it = vec.rbegin(); it != vec.rend(); it++){  // 本质上已经颠倒了前进和后退的方向，所以迭代器it是++
        cout << *it << "  ";
    }
    cout << endl;
    return 0;
}

//正向迭代:
//1  2  3  4  5
//反向迭代:
//5  4  3  2  1

关于priority_queue

在 C++ 中，priority_queue 是一种基于堆的数据结构，可以高效地管理按优先级排序的数据。它实现了一个最大堆，其中队列的头部（top() 返回的元素）总是最大元素。标准库 <queue> 提供了这个容器适配器。

基本用法

priority_queue 的基本用法涉及几个主要函数：

push(x): 将元素 x 插入队列。
pop(): 移除最大元素。
top(): 返回最大元素。
empty(): 返回队列是否为空。
size(): 返回队列中的元素数量。

创建 `priority_queue`

默认情况下，priority_queue 使用 vector 作为其底层容器，并使用 less 作为比较函数，这意味着元素是按降序排序的（最大的元素位于顶部）。你也可以指定不同的底层容器或不同的比较逻辑。比如，你可以使用 greater 来创建一个最小堆：

#include<bits/stdc++.h>
using namespace std;
int main(){
    // 正确的声明应该包括三个模板参数：元素类型、容器类型和比较函数类型。
    priority_queue<int, vector<int>, greater<int>> min_heap;
    // 添加元素
     min_heap.push(10);
     min_heap.push(30);
     min_heap.push(20);
     min_heap.push(5);
     min_heap.push(1);
    while(!min_heap.empty()){
        cout << min_heap.top() << "  ";
        min_heap.pop();
    }
    cout << endl;
    return 0;
}
//1  5  10  20  30

如果你想在 priority_queue 中使用自定义类型，你需要定义比较逻辑。这通常通过重载 operator< 或提供一个比较类（比如使用结构体实现 operator()）来完成：

#include<bits/stdc++.h>
using namespace std;

struct Compare {
    bool operator()(const int& a, const int& b) {
        return a > b; // 最小堆
    }
};

int main() {
    priority_queue<int, std::vector<int>, Compare> pq;
    pq.push(5);
    pq.push(1);
    pq.push(10);
    while (!pq.empty()) {
        std::cout << pq.top() << ' ';
        pq.pop();
    }
    cout << endl;
    return 0;
}
//1 5 10

LONG_MIN 和 LONG_MAX，它们分别代表 long long 类型能表示的最小值和最大值。

运算符重载与友元运算符重载🔃：

在C++中，运算符重载是一种特殊的函数，它改变了某个运算符的行为。C++允许在同一作用域中的某个函数和运算符指定多个定义，分别称为函数重载和运算符重载。
函数重载是指在同一个作用域内，可以声明几个功能类似的同名函数，但是这些同名函数的形式参数（指参数的个数、类型或者顺序）必须不同。您不能仅通过返回类型的不同来重载函数1。
运算符重载是指改变某个运算符的行为。重载的运算符是带有特殊名称的函数，函数名是由关键字operator和其后要重载的运算符符号构成的。与其他函数一样，重载运算符有一个返回类型和一个参数列表。
例如，我们可以重载+运算符，使其可以用于我们自定义的类。假设我们有一个名为Box的类，我们可以这样重载+运算符：

Box operator+(const Box& b) {
    Box box;
    box.length = this->length + b.length;
    box.breadth = this->breadth + b.breadth;
    box.height = this->height + b.height;
    return box;
}

在C++中，友元运算符重载是一种特殊的运算符重载方式。当我们需要改变某个运算符的行为，但该运算符不是类的成员函数时，我们可以使用友元函数来实现运算符重载。
友元运算符重载函数的一般格式为：

friend 返回值类型 operator 需要被重载的运算符(类名 &对象名){
    // ... 实现细节 ...
}

这里的friend关键字表示该函数是类的友元，可以访问类的私有和保护成员。例如，我们可以重载+运算符，使其可以用于我们自定义的类。假设我们有一个名为Complex的类，我们可以这样重载+运算符：

class Complex {
public:
    // ... 其他成员函数和数据成员 ...
    friend Complex operator+(const Complex& c1, const Complex& c2);
};

Complex operator+(const Complex& c1, const Complex& c2) {
    Complex result;
    result.real = c1.real + c2.real;
    result.imag = c1.imag + c2.imag;
    return result;
}

在这个例子中，operator+函数接受两个Complex对象作为参数，然后返回一个新的Complex对象，其实部和虚部分别是两个Complex对象的实部和虚部的和。需要注意的是，当我们使用友元函数重载运算符时，运算符的左操作数可以是类的对象，也可以是其他类型的值。这给我们提供了更大的灵活性，使我们能够更自然地使用自定义的类。

字符转换大小写：

在C++中，tolower和toupper是两个非常有用的函数，它们分别用于将字符转换为小写和大写。

tolower(int c)函数：如果参数c是一个大写字母（‘A’到’Z’），那么这个函数会返回对应的小写字母（‘a’到’z’）。如果参数c不是大写字母，那么这个函数会直接返回参数c。
toupper(int c)函数：如果参数c是一个小写字母（‘a’到’z’），那么这个函数会返回对应的大写字母（‘A’到’Z’）。如果参数c不是小写字母，那么这个函数会直接返回参数c。

这两个函数都定义在<cctype>头文件中。在使用这两个函数时，需要确保参数c是一个有效的字符（即在ASCII表中的值为0到255的字符）。如果参数c不是一个有效的字符，那么这两个函数的行为是未定义的。

Bitset的用法：

bitset是C++标准库中的一个类，它可以用来处理固定大小的位序列。bitset的主要用途是进行位操作，包括位的设置、重置、翻转等。

以下是一些基本的bitset操作：

初始化：可以使用整数或字符串来初始化bitset。

bitset<4> b1(2); // 二进制表示为0010
bitset<4> b2(string("1010")); // 二进制表示为1010

访问位：可以使用数组索引操作符来访问bitset中的位。

cout << b1[0]; // 输出0
cout << b2[3]; // 输出1

位操作：bitset支持各种位操作，如位与(&)、位或(|)、位异或(^)、位非(~)等。

bitset<4> b3 = b1 & b2; // 位与操作
bitset<4> b4 = b1 | b2; // 位或操作
bitset<4> b5 = b1 ^ b2; // 位异或操作
bitset<4> b6 = ~b1; // 位非操作

其他操作：bitset还提供了其他一些有用的操作，如count()（返回置位的位数）、size()（返回位数）、flip()（翻转所有位）、set()（设置所有位）、reset()（重置所有位）等。

cout << b1.count(); // 输出1
cout << b1.size(); // 输出4
b1.flip(); // 翻转所有位
b1.set(); // 设置所有位
b1.reset(); // 重置所有位

特点：

.begin() 和 .end()

.rbegin() 和 .rend()

迭代器的使用

基本用法

创建 priority_queue

创建 `priority_queue`