C++ STL

ACM C++ 笔记

发布时间 : 2025-04-07 00:00

基础

有符号二进制数表示法

在计算机中，有符号二进制数使用最高位作为符号位，0表示正数，1表示负数。通常使用原码、反码和补码三种形式来表示有符号数。

原码

原码表示法直接使用二进制数的最高位作为符号位，其余位表示数值大小。
例如，8位原码表示的数：
- +5: 0000 0101
- -5: 1000 0101

反码

正数的反码与原码相同。
负数的反码是对原码取反（即0变1，1变0），但符号位不变。
例如，8位反码表示的数：
- +5: 0000 0101
- -5: 1111 1010

补码

正数的补码与原码相同。
负数的补码是对其反码加1。
例如，8位补码表示的数：
- +5: 0000 0101
- -5: 1111 1011

负数转正数与正数转负数

正数转负数：先减1再每位取反。例如：
- 011 (正数3) -> 010 -> 101
负数转正数：先每位取反再加1。例如：
- 101 (负数-3) -> 010 -> 011

32位int范围

正数范围：0 ~ 2^31 - 1
负数范围：-1 ~ -2^31

判断数的某一位是0还是1

可以使用位运算判断某个数的某一位是0还是1，代码示例如下：

bool d = (num & ((long long)1 << i)) == 0 ? 0 : 1;

a/b 向上取整

(a + b - 1)/b

求一个区间[l,r]内满足 % x == 0 的数的个数
r/x - (l-1)/x

匿名函数

auto 写在里面可以避免忘记多测清空和避免传参

// auto 建立链式前向星

int id = 1;
auto ad = [&](int x, int y) {
	to[id] = y;
    nx[id] = head[x];
    head[x] = id++;
};

// auto 遍历递归树

auto dfs = [&] (auto&& self, int cur, int f) -> void {
    sz[cur] = 1;
    for (int i = head[cur]; i; i = nx[i]) {
        if (to[i] == f) {
            continue;
        } 
        self(self,to[i],cur);
        sz[cur] += sz[to[i]];
    }
};
dfs(dfs,1,0);

Vector

初始化一个空的 vector
vector<int> vec;

初始化一个包含 5 个元素，每个元素的值都为 0 的 vector
vector<int> vec1(5);

初始化一个包含 5 个元素，每个元素的值都为 0 的 vector，C++11 之后可以用以下方式
vector<int> vec2(5, 0);

通过初始化列表初始化 vector
vector<int> vec3 = {1, 2, 3, 4, 5};

复制另一个 vector
vector<int> vec4(vec3);

通过赋值运算符赋值
vector<int> vec5;
vec5 = vec4;

通过下标访问元素
int x = vec3[0];

使用 at() 函数访问元素，会进行越界检查
int y = vec3.at(1);

获取第一个和最后一个元素
int first = vec3.front();
int last = vec3.back();

在末尾插入一个元素
vec.push_back(10);

在指定位置插入一个元素
vec.insert(vec.begin() + 2, 20);

删除末尾的元素
vec.pop_back();

删除指定位置的元素
vec.erase(vec.begin() + 1);

清空 vector
vec.clear();

使用范围-based for 循环遍历

for (int x : vec) {
    cout<<x<<endl;
}

使用迭代器遍历

for (auto it = vec.begin(); it != vec.end(); ++it) {
    cout<<*it<<" ";
}

下标遍历

for (size_t i = 0; i < vec.size(); i++) {
    cout<<vec[i]<<" ">>;
}

获取 vector 的大小
int n = vec.size();

检查 vector 是否为空
bool empty = vec.empty();

重设 vector 的大小
vec.resize(10);

翻转 vector
reverse(vec.begin(), vec.end());

对 vector 进行排序
sort(vec.begin(), vec.end());
对 vector 进行降序排序
sort(vec.begin(), vec.end(),greator<int>());

对 vector 进行去重离散化
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
//或者
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());

对于 unique 函数来说，要求元素必须是相邻的才能进行去重操作，而且它只会去除相邻的重复元素。
因此，在使用 unique 去重之前，通常需要先对容器进行排序，以确保相同的元素都相邻排列，才能正确去重

二维vetor

建立空的二维vector数组
vector<vector<int>> vec;

建立有五行，列数未知的的二维vector数组
vector<vector<int>> vec(5);

string

string s = "";

构造函数，n 个重复的字符
string s = string(n,'a')

获取长度

int n = s.length();

取子串

从loc位置开始(包括a)取长度为n
string s1 = s.substr(loc,n);
省略长度，从loc位置开始取到末尾
string s1 = s.substr(loc);

串内排序

把字符串内的字符按字典序排序 “deacb” –> “abcde”
sort(s.begin(),s.end());

查找子串，字符

返回s中出现的第一个s1的第一个字符的位置
int loc = s.find(s1);
从右往左第一个匹配的
int loc = s.rfind(s1);
从startpos开始往后找
int loc = s.find(s1,startpos);
从startpos开始往前找
int loc = s.rfind(s1,startpos);
判断是否找到
if(s.find(s2) == string::npos) cout<<"Not found";

字符串之间比较大小

>,<,=已经被重载，可以直接用于字符串之间大小比较。
方法：从第一位开始按位按照字典序比较，不同的位字典序大的更大，若一个串是另一个串的字串，则字串更小。

与整数相互转换

s(tring) to i(nt)
int a = stoi("1234");

注意stoi有可能会爆ll
最好使用
int a = stoll("1234)

int to string
string s = to_string(1234);

注意

int n;
cin >> n;
string s = "";
for (int i = 1; i <= n; i++) {
    // ans = ans + 'a'; 不能用，时间复杂度为n^2
    ans += 'a'  // 可以使用，每次添加为O(1)，时间复杂度为串的总长 
}

stringstream流提取

#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main() {
    string input = "First line\nSecond line\nThird line";
    stringstream ss(input);
    string line;

    while (std::getline(ss, line)) {
        cout << line << std::endl;
    }

    return 0;
}

分隔一行中空格

while(getline(cin,line)) {
    stringstream ss(line);
    size_t wi = 0;
    while(ss >> word) {
        len[wi] = max(len[wi],word.size());
        wi++;
        words[cnt].push_back(word);
    }
    cnt++;
}

按符号分隔

cin >> line;
stringstream ss(line);
string s;
int cnt = 1;
while (getline(ss, s, '.')) {
    a[i][cnt] = s;
    b[i][cnt] = trans(s);
    cnt++;
}

lowerbound

对vector进行二分查找
时间复杂度O($n\log_2 n$)
用于查找在已排序范围内，大于等于指定值的第一个元素的位置。如果找到了符合条件的元素，则返回一个指向该元素的迭代器；如果没有找到符合条件的元素，则返回一个指向大于指定值的第一个元素的位置的迭代器。
降序序列a，loc是第一个大于等于key的迭代器。如果key比所有元素都要大，返回a.end()
int loc = lower_bound(a.begin(), a.end(), key) - a.begin();
upper_bound : 大于

sort

内部采用快速排序
时间复杂度O($n\log_2 n$)
最坏情况O($n^2$)

int a[n];
sort(a,a+n);//默认升序
sort(a,a+n,[&](int a,int b){ return a>b;} );//降序排列 &用于捕获当前局部变量
vector a(n);
sort(a.begin(),a.end());//默认升序
sort(a.begin(),a.end(),[](int a,int b){return a>b;})//降序

pair

含有两个“元素”first,second
first 和 second 成员的数据类型可以是任意类型。因为 pair 是一个模板类，它的模板参数可以接受任何类型。

pair<int,string> p[n];
int x = p[1].first;
string y = p[1].second;
pair<int,string> p2(6,"Egrvigrf");
pair<int,string> p3;
p3 = {6,"Egrvigrf"};

map

内部用红黑树实现，具有按键从小到大自动排序的功能。
优点：内部元素有序，查询时间复杂度为 O(log n)。
缺点：占用空间较大。

遍历map

使用迭代器遍历

for (auto it = mp.begin(); it != mp.end(); ++it) {
    cout << "Key: " << it->first << ", Value: " << it->second << endl;
}

使用结构化绑定遍历(c++ 17)

for (const auto& [key, value] : mp) {
    cout << "Key: " << key << ", Value: " << value << endl;
}

查询键是否存在

如果键不存在，则返回迭代器的结尾

if(mp.find(key) == mp.end()) {
    cout<<"Not found";
} else {
    cout<<"found";
}

unordered_map

cf会用unordered_map会被hack

内部用哈希表实现，查找速度非常快。
缺点：建立哈希表比较耗时。
用 [] 查找元素时，如果不存在会创建空的键值对，降低后续创建查询删除效率。
最优方法：先判断存在与否，再索引对应值。

总的来说，[]运算符和insert函数都可以用于向map中插入元素，但它们有一些性能方面的区别：

[]运算符插入元素时会先进行查找操作，如果元素不存在则会插入一个默认值的新元素，然后返回该元素的引用。这个过程可能会引起底层容器的重排。
insert函数直接插入一个新的元素，不会先进行查找操作。如果插入的键已经存在，则不会插入新元素。

在插入大量元素时，使用[]运算符可能会比使用insert函数稍慢，因为它可能会引起额外的查找和重排操作。但对于单个元素的插入操作，两者的性能差异可能不太明显。因此，在选择使用哪种方法时，可以根据具体的需求和性能要求进行考虑。

set

元素不重复，插入已存在元素不会插入，保证元素唯一性。
元素按照升序（从小到大）排列。
内部实现通常基于红黑树，因此插入、删除和查找操作的平均时间复杂度为 O(log n)。

multiset

允许元素重复，可以存储相同的元素。
元素按照升序（从小到大）排列。
内部实现通常基于红黑树，因此插入、删除和查找操作的平均时间复杂度为 O(log n)。

unordered_set

元素不重复，插入已存在元素时不会插入，保证元素唯一性。
元素无序存储，内部实现通常基于哈希表。
插入、删除和查找操作的平均时间复杂度为 O(1)，但可能会受到哈希冲突的影响。

unordered_multiset

允许元素重复，可以存储相同的元素。
元素无序存储，内部实现通常基于哈希表。
插入、删除和查找操作的平均时间复杂度为 O(1)，但可能会受到哈希冲突的影响。

总的来说，set 和 multiset 是有序容器，unordered_set 和 unordered_multiset 是无序容器。有序容器在插入、删除和查找操作上通常比无序容器慢，但可以保持元素的顺序。相反，无序容器在插入、删除和查找操作上通常更快，但元素的顺序是不确定的。选择适当的容器取决于具体的需求和性能要求。

queue

优先队列

用top()而不是front()取队头

默认从大到小
priority_queue<int> pq;
从小到大
priority_queue<int, vector<int>, greator<int> > pq2;
自定义
priority_queue<int, vector<int>, cmp> pq;

双端队列

deque<int> dq;

入队
dq.push_front(x)
dq.push_back(x)
读取队首，尾
x = dq.front();
x = dq.back();

出队
pop_front();
pop_back();

stack

·stack<int> s;

入栈
s.push();

出栈
s.pop();

取栈顶
s.top();

next_permutation

用法：生成全排列，时间复杂度O(n)

vector<int> a;
// 一些数
a.sort(a.begin(),a.end()); // 按字典顺序递增生成排列，所以先排序
do {
    //一些操作
    for (auto i : a) {
        cout << i << " ";
    }
} while(next_permutation(a.begin(),a.end()));

bitset

能极大的压缩空间，占用是bool的1/8

基本操作


bitset<8> bs;   // 创建一个大小为 8 的 bitset，默认初始化为 00000000  
  
vector<bitset<5001>> b; // 大小在编译时就要确定，不能读入动态大小

bitset<8> bs1(42);  // 通过整数进行初始化，42 的二进制表示为 00101010  
  

bitset<8> bs2("1101");   // 通过字符串进行初始化，右对齐，结果为 00001101  
  

bitset<8> bs3("1101", 2);   // 通过字符串进行初始化，从第 2 位开始，结果为 00000011

设置位

bs.set();// 全部设置为 1  
bs.set(3);// 将第 3 位设置为 1  
bs.set(3, 0);// 将第 3 位设置为 0

清除位

bs.reset();// 全部清除为 0  
bs.reset(3);// 将第 3 位清除为 0

翻转位

bs.flip();// 全部位翻转
bs.flip(3);// 翻转第 3 位

访问位

bool b = bs.test(3);// 检查第 3 位是否为 1  
bool b = bs[3];// 也可以使用下标访问

获取二进制表示的字符串

std::string str = bs.to_string();// 转换为字符串

其他操作

& | ^ == != 已经重载，可以用于两个bitset类型变量

size_t count = bs.count();// 返回 1 的数量  
size_t size = bs.size();// 返回位的总数  
bool any = bs.any();// 是否有任何一位为 1  
bool none = bs.none();// 是否全为 0

手写位图
手写位图

随机

static mt19937_64 rng(random_device{}()); // 用random_device{}() 作为随机数种子产生随机数序列,每次运行只需调用一次
x = rng();                       // 64位范围[0,2^64-1]
vector<int> a = {1,2,3};
shuffle(a.begin(),a.end(),rng); // 调用随机打乱序列
int p1 = uniform_int_distribution<int>(l,r)(rng); // 产生l到r的均匀分布的整数

手工hash

防止卡umap

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x) {
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30) )*0xbf58476d1ce4e5b9;
        x=(x^(x>>27) )*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator() (uint64_t x) const {
        static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};