基础杂项

auto的使用

• 当你想要拷贝range的元素时，使用 for(auto x : range).
• 当你想要修改range的元素时，使用 for(auto && x : range)
• 当你想要只读range的元素时，使用 for(const auto & x : range).

容器间的转换

使用begin end

1
2
3
4
5

vector<int>& nums1
unordered_set<int> nums_set(nums1.begin(), nums1.end());

unordered_set<int> result;
return vector<int>(result.begin(), result.end());

以下是整理和改正后的迭代器笔记。

迭代器知识

随机访问迭代器

• 定义：随机访问迭代器是一种迭代器类型，允许在常数时间内访问序列中的任何元素，并支持灵活的迭代器操作。

• 运算支持：

  • 支持指针算术运算，如 + 和 - 运算符，允许轻松地在迭代器位置上进行移动。
  • 支持下标运算符 []，使其用法与指针类似。
  • 例如，对于一个指向数组的随机访问迭代器 it，可以通过 *(it + i) 或 it[i] 语法访问第 i 个元素。

• 使用场景：

  • STL 容器：vector 和 deque 都提供随机访问迭代器。
  • 算法：一些标准库算法（例如 std::sort、std::nth_element）要求输入的迭代器必须是随机访问迭代器，以便快速定位和排序。

正向迭代器与反向迭代器

• 概述：在 C++ 中，容器一般提供正向迭代器（begin() 到 end()）和反向迭代器（rbegin() 到 rend()），二者在遍历方向上相反。

• 转换：正向迭代器和反向迭代器可以相互转换，但类型不同，需要显式转换。

  • 正向迭代器到反向迭代器：可以将一个正向迭代器转换为反向迭代器。

    1 2	Iterator it; // 假设 it 是正向迭代器 std::reverse_iterator<Iterator> rit(it); // 将 it 转换为反向迭代器 rit

  • 反向迭代器到正向迭代器：反向迭代器的 base() 成员函数可以返回一个指向反向迭代器当前元素的下一个位置的正向迭代器。

    1 2	std::reverse_iterator<Iterator> rit; Iterator it = rit.base(); // 转换为正向迭代器，指向 rit 所指位置的后一个元素

• 注意：

  • 反向迭代器 rit.base() 指向的并不是 rit 当前元素本身，而是 rit 指向元素的下一个位置。

反向遍历

C++ 提供了 rbegin() 和 rend() 来支持容器的反向遍历：

• rbegin() 返回一个反向迭代器，指向容器的最后一个元素。
• rend() 返回一个反向迭代器，指向容器反向遍历时的“结束位置”，即第一个元素之前的一个位置。
• 在循环中，注意使用 ++it 而非 --it，因为反向迭代器的递增操作相当于在正向迭代器上进行递减操作。

1
2
3
4
5

for (auto it = collection.rbegin(); it != collection.rend(); ++it) {
    std::cout << *it << std::endl;
    // 或者如果是键值对容器：
    // std::cout << it->first << ", " << it->second << std::endl;
}

1
2
3
4
5

auto it = showedPositive.end();
while (it != showedPositive.begin()) {
    --it;  // 注意：先递减迭代器，再访问元素
    std::cout << *it << std::endl;
}

前后第k个元素

• std::prev 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向前移动指定偏移量后的迭代器。
• std::next 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向后移动指定偏移量后的迭代器。

1
2
3
4
5
6

auto prevIt = std::prev(it);

auto next2It = std::next(it, 2);

auto it2 = it;
advance(it2,k);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template <typename InputIt, typename Distance>
void advance(InputIt& it, Distance n) {
    if constexpr (std::is_same_v<std::random_access_iterator_tag,
                typename std::iterator_traits<InputIt>::iterator_category>) {
        it += n; //如果迭代器是随机访问迭代器（后面解释），它会使用 += 运算符来移动；
    } else {
        if (n >= 0) {
            while (n--) {
                ++it; //否则，它会使用循环来移动。
            }
        } else {
            while (n++) {
                --it;
            }
        }
    }
}

bitset

bitset类型存储二进制数位。

初始化

1
2
3
4
5
6
7

std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));

//foo: 0000000000000000
//bar: 0000111110100010
//baz: 0000000101111001

格式转换

将数转化为其二进制的字符串表示

1
2
3

int i = 3;
string bin = bitset<16>(i).to_string(); //bin = "0000000000000011"
bin = bin.substr(bin.find('1'));        //bin = "11"

pair

1
2
3
4
5
6
7
8

#include <utility>
pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

tuple

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <tuple> // 包含 tuple

std::tuple<int, std::string, double> t1(1, "one", 1.0);

// 使用 make_tuple 函数
auto t2 = std::make_tuple(2, "two", 2.5);

//使用 tuple 时，访问/修改元素使用 std::get<index>。
std::cout << "Tuple t2: ("
            << std::get<0>(t2) << ", "
            << std::get<1>(t2) << ", "
            << std::get<2>(t2) << ")"
            << std::endl;

char 与 字符串

元音与index的相互映射

1
2
3
4

string vowel = "AEIOUaeiou";
if vowel.find(c) != std::string::npos;

voewl[0] = 'A';

string

初始化与读取

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

std::string s0 ("Initial string");

// constructors used in the same order as described above:
std::string s1;
std::string s2 (s0);
std::string s3 (s0, 8, 3);
std::string s4 ("A character sequence");
std::string s5 ("Another character sequence", 12);
std::string s6a (10, 'x');
std::string s6b (10, 42);      // 42 is the ASCII code for '*'
std::string s7 (s0.begin(), s0.begin()+7);

std::cout << "s1: " << s1 << "\ns2: " << s2 << "\ns3: " << s3;
std::cout << "\ns4: " << s4 << "\ns5: " << s5 << "\ns6a: " << s6a;
std::cout << "\ns6b: " << s6b << "\ns7: " << s7 << '\n';

//output
s1: 
s2: Initial string
s3: str
s4: A character sequence
s5: Another char
s6a: xxxxxxxxxx
s6b: **********
s7: Initial

读取空格分割的

1
2
3
4
5

stringstream txt(s);
string word;
while(txt>>word){
    // to do
}

增

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

// inserting into a string
#include <iostream>
#include <string>

std::string str="to be question";
std::string str2="the ";
std::string str3="or not to be";
std::string::iterator it;

// used in the same order as described above:
str.insert(6,str2);                 // to be (the )question
str.insert(10,"to be ");            // to be not (to be )that is the question
it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
str.insert(6,str3,3,4);             // to be (not )the question
str.insert(10,"that is cool",8);    // to be not (that is )the question
str.insert(str.end(),3,'.');       // to be, not to be: that is the question(...)
str.insert(15,1,':');               // to be not to be(:) that is the question
// ???
str.insert (it+2,str3.begin(),str3.begin()+3); // (or )

1
2
3
4
5
6
7
8
9
10
11
12
13

std::string s = "C+";
char ch = '+';

s.push_back(ch);
s += ch; //string::operator+=, which is overloaded for chars and internally calls to the push_back() function.
s.append(1, ch); //1*ch个字符
s.append("abcd"); //后面添加abcd字符串

std::stringstream ss;
ss << s << ch;
ss >> s;

s.insert(s.length(), 1, ch);

1
2
3
4
5

//连接 string, 很简单。
str1 = str1 + str2;
//连接 char * , src 和 dest 所指内存区域不可以重叠且 dest 必须有足够的空间来容纳 src 的字符串。结果返回指向 dest 的指针。
#include <cstring>
strcat(dest, src);

删

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

// string::erase
#include <iostream>
#include <string>

int main ()
{
std::string str ("This is an example sentence.");
std::string str1(str) ;
std::cout << str << '\n';
                                        // "This is an example sentence."
str.erase (10,8);                        //            ^^^^^^^^
//去除index=10的连续8个元素，

//去除从index=3开始的所有元素, 后面全删除
str1.erase (3);
// "Thi"

std::cout << str << '\n';
                                        // "This is an sentence."
str.erase (str.begin()+9);               //           ^
//去除itr指向的元素
std::cout << str << '\n';
                                        // "This is a sentence."
str.erase (str.begin()+5, str.end()-9);  //       ^^^^^
//去除[first,last).的元素
std::cout << str << '\n';
                                        // "This sentence."
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

std::string s = "C,C++,Java,";
if (!s.empty()) {
s.pop_back();
}

if (!s.empty()) {
s.resize(s.size() - 1);
}

if (!s.empty()) {
s.erase(std::prev(s.end()));
}

if (!s.empty()) {
s.erase(s.size() - 1);
}

改

1
2
3
4

// Copy three characters of s1 (starting
// from position 1)
//第一个参数是要截取的字符串，第二个参数是截取的开始位置，第三个参数是截取长度（可选）1。如果没有指定长度，则子字符串将延续到源字符串的结尾。
string r = s1.substr(1, 3);

1
2
3
4
5
6
7
8

// Take any string
string s = "dog:cat";
// Find position of ':' using find()
int pos = s.find(":");
// Copy substring after pos(include pos)
string sub = s.substr(pos);
// Copy substring before pos(not include pos)
string sub = s.substr(0 , pos);

1

reverse(greeting.begin(),greeting.end());

查

1
2
3
4

//总长度
len = str3.size();
// strlen 大部分情况结果和size一样，但是字符串里有\0, strlen会提前返回。
len = strlen(s1);

1
2

string s;
for(auto && x : s)

1
2

printf("%s", your_string.c_str()); //不推荐
cout << your_string;

1
2
3
4
5
6

// log1 中找空格
int pos1 = log1.find_first_of(" ");

// 判断是否找到
if(s.find(goal) != string::npos){
}

1
2
3

#include <cctype>  // 对应 isdigit 函数
// 判断数字
bool isDigit1 = isdigit(log1[pos1 + 1]);

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

#include <iostream>
#include <string>

bool hasPrefix(const std::string& str, const std::string& prefix) {
    return str.compare(0, prefix.size(), prefix) == 0;
}

int main() {
    std::string text = "Hello, world!";
    std::string prefix = "Hello";

    if (hasPrefix(text, prefix)) {
        std::cout << "The string starts with the prefix." << std::endl;
    } else {
        std::cout << "The string does not start with the prefix." << std::endl;
    }

    return 0;
}

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

#include <iostream>
#include <string>

bool hasPrefix(const std::string& str, const std::string& prefix) {
    return str.find(prefix) == 0;
}

int main() {
    std::string text = "Hello, world!";
    std::string prefix = "Hello";

    if (hasPrefix(text, prefix)) {
        std::cout << "The string starts with the prefix." << std::endl;
    } else {
        std::cout << "The string does not start with the prefix." << std::endl;
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
#include <string>

int main() {
    std::string text = "Hello, world!";
    std::string prefix = "Hello";

    if (text.starts_with(prefix)) {
        std::cout << "The string starts with the prefix." << std::endl;
    } else {
        std::cout << "The string does not start with the prefix." << std::endl;
    }

    return 0;
}

1
2
3

size_t rfind(const std::string& str, size_t pos = std::string::npos) const;
size_t rfind(const char* s, size_t pos = std::string::npos) const;
size_t rfind(char c, size_t pos = std::string::npos) const;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
#include <string>

int main() {
    std::string text = "Hello, world! Hello, C++!";
    size_t pos = text.rfind("Hello");

    if (pos != std::string::npos) {
        std::cout << "'Hello' found at position: " << pos << std::endl;
    } else {
        std::cout << "'Hello' not found." << std::endl;
    }

    return 0;
}

1

'Hello' found at position: 14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
#include <string>

int main() {
    std::string text = "abcdefgabc";
    size_t pos = text.rfind('a');

    if (pos != std::string::npos) {
        std::cout << "'a' found at position: " << pos << std::endl;
    } else {
        std::cout << "'a' not found." << std::endl;
    }

    return 0;
}

1

'a' found at position: 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
#include <string>

int main() {
    std::string text = "Hello, world! Hello, C++!";
    size_t pos = text.rfind('o', 10);

    if (pos != std::string::npos) {
        std::cout << "'o' found at position: " << pos << std::endl;
    } else {
        std::cout << "'o' not found." << std::endl;
    }

    return 0;
}

1

'o' found at position: 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
25
26
27
28
29
30
31
32
33

#include <vector>
#include <regex> //important

// 解析字符串中的所有单个数字和范围
void parseNumbers(const std::string& input, std::vector<std::pair<int, int>>& ranges) {
    // 在 C++ 中，使用 R"(...)" 定义原始字符串，可以避免转义字符
    std::regex rangePattern(R"(\b(\d+)\s+to\s+(\d+)\b)");  // 匹配范围形式

    std::smatch match;
    std::string::const_iterator searchStart(input.cbegin());

    // 找到所有的范围
    while (std::regex_search(searchStart, input.cend(), match, rangePattern)) {
        int start = std::stoi(match[1]);
        int end = std::stoi(match[2]);
        ranges.emplace_back(start, end);
        searchStart = match.suffix().first;  // 更新搜索起点
    }


}

int main() {
    std::string input = "undo xxx aaa 1 2 4 to 10";
    std::vector<std::pair<int, int>> ranges;

    parseNumbers(input, ranges);


    // 输出范围

    return 0;
}

顺序容器与关联容器

• 顺序容器包括vector、deque、list、forward_list、array、string，

  • 支持快速顺序访问元素。

• 关联容器包括set、map，

  • 支持高效的关键字查找和访问。
  • 不支持顺序容器的位置相关的操作。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。
  • 也不支持构造函数或插入操作这些接受一个元素值和一个数量值得操作。

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

二叉树

存储方式

链表，或者数组(如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。)

链式结构如下，注意左右孩子节点

1
2
3
4
5
6
7
8
9
10
11

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* a = new TreeNode();
a->val = 9;
a->left = NULL;
a->right = NULL;

遍历方式

深度遍历： 前/中/后序遍历。

注意：这里前中后，其实指的就是中间节点/根节点的遍历顺序

heap 堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值。

  • 大顶堆：每个结点的值都大于或等于其左右孩子结点的值；
  • 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

• 堆总是一棵完全二叉树。

• make_heap()​​将区间内的元素转化为heap.

• ​push_heap()​​对heap增加一个元素.

• ​​pop_heap()​​对heap取出下一个元素.

• ​sort_heap()​​对heap转化为一个已排序群集.

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

#include <algorithm>
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;

make_heap (v.begin(),v.end());//male_heap就是构造一棵树，使得每个父结点均大于等于其子女结点
cout << "initial max heap   : " << v.front() << endl;

pop_heap (v.begin(),v.end());//pop_heap不是删除某个元素而是把第一个和最后一个元素对调后[first,end-1]进行构树，最后一个不进行构树
v.pop_back();//删除最后一个的结点
cout << "max heap after pop : " << v.front() << endl;

v.push_back(99);//在最后增加一个结点
push_heap (v.begin(),v.end());//重新构树
cout << "max heap after push: " << v.front() << endl;

//请在使用这个函数前，确定序列符合堆的特性，否则会报错！
sort_heap (v.begin(),v.end());//把树的结点的权值进行排序，排序后，序列将失去堆的特性
std::cout << "sorted array       : ";
for (int i = 0; i < v.size(); ++i) {
    std::cout << v[i] << ' ';
}
std::cout << std::endl;

map / unordered_map / hash_map

1. map
   1. 内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。其中每个键都是唯一的，可以插入或删除，但不能更改。但是与键关联的值可以更改。
   2. 红黑树是一种含有红黑结点并能自平衡的二叉查找/搜索树, 别称平衡二叉B树（symmetric binary B-trees）
2. unordered_map(hash_map)
   1. 基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
   2. 标准库的unordered_map，底层实现是基于hashtable的，其避免冲突的方法是使用开链（seperate chaining）法，这种做法是在每一个表格元素中维护一个list，每个表格元素称之为buket（桶）

初始化

map的value是int，默认为0。可以直接++

1
2
3
4
5
6
7
8
9
10

#include <map>
#include <unordered_map>
//c++11以上
map<string,int> m3 = {
    {"string",1}, {"sec",2}, {"trd",3}
};
map<string,string> m4 = {
    {"first","second"}, {"third","fourth"},
    {"fifth","sixth"}, {"begin","end"}
};

增改

1
2
3
4

// insert 不能覆盖元素，已经存在会失败
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
// 数组方式可以覆盖
mapStudent[1] = "student_one";

1
2
3

pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, "student_one"));

删除

1

mymap.erase ('c');               // erasing by key

查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//unordered_map 类模板中，还提供有 at() 成员方法，和使用 [ ] 运算符一样，at() 成员方法也需要根据指定的键，才能从容器中找到该键对应的值；
//不同之处在于，如果在当前容器中查找失败，该方法不会向容器中添加新的键值对（[]会插入默认值），而是直接抛出out_of_range异常。
cnt.at(num)

// c++17 支持
for (auto &[num, c] : cnt) {
}
for (auto &[x, _] : cnt) {
    //sth
}
// 否则
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
    auto& key = it->first;
    auto& value = it->second;
    // 使用 key 和 i 进行操作
}

1
2
3
4
5
6
7
8

unordered_map<string, string>::iterator iter = umap.find("GO教程");
if (iter == umap.end()) {
    //查找失败
    cout << "当前容器中没有以\"GO教程\"为键的键值对";
}else {
    //查找成功
    cout << iter->first << " " << iter->second << endl;
}

1
2
3
4
5

// 检查键30是否存在
if (mp.count(30))
cout << "键30存在\n";
else
cout << "键30不存在\n";

set

常用于 一个值是否存在 的相关问题

1. 按关键字有序：
   1. set(关键字即值，即只保存关键字的容器)；使用红黑树，自动排序，关键字唯一。
   2. multiset(关键字可重复出现的set)；
2. 无序集合：
   1. unordered_set(用哈希函数组织的set)；
   2. unordered_multiset(哈希组织的set，关键字可以重复出现)。

set/map 的有序性

默认红黑树，使用std::less 作为比较器, 升序序列。

1
2
3
4
5
6
7

// 自定义比较器，按降序排列
struct Greater {
    bool operator()(const int& a, const int& b) const {
        return a > b;
    }
};
std::set<int, Greater> s = {5, 3, 8, 1, 4};

1
2
3
4
5
6
7
8
9
10
11

template < class T,                             // set::key_type/value_type
        class Compare = less<T>,        // set::key_compare/value_compare
        class Alloc = allocator<T>         // set::allocator_type
        > class set;

//初始化
set<char> vowel {'a','e','i','o','u'};

template <class T, class Compare, class Alloc>
bool operator== ( const set<T,Compare,Alloc>& lhs,
                    const set<T,Compare,Alloc>& rhs ); // 和map类似的，重载相等判断

1
2
3
4
5
6

auto hash_p = [](const pair<int, int> &p) -> size_t {
static hash<long long> hash_ll;
return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
};
unordered_set<pair<int, int>, decltype(hash_p)> points(0, hash_p); //(0,hash_p)分别为迭代器的开始和结束的标记（数组多为数据源）
//多用于数组 set<int> iset(arr,arr+sizeof(arr)/sizeof(*arr));

1
2

auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

1
2
3
4
5
6

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};
std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

增删改查

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

//增改
insert()–在集合中插入元素
emplace() 最大的作用是避免产生不必要的临时变量

erase()–删除集合中的元素
//删除 set 容器中值为 val 的元素
//第 1 种格式的 erase() 方法，其返回值为一个整数，表示成功删除的元素个数；
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
//后 2 种格式的 erase() 方法，返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素。
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);
clear()–删除集合中所有元素

//查询
find()–返回一个指向被查找到元素的迭代器。返回值：该函数返回一个迭代器，该迭代器指向在集合容器中搜索的元素。如果找不到该元素，则迭代器将指向集合中最后一个元素之后的位置end
count()- 查找的bool结果
size()–集合中元素的数目

swap()–交换两个集合变量

并差集

• 并查集主要用于处理一些不相交集合的合并和查询问题。它在很多算法问题中都有广泛的应用，特别是在图论和动态连通性问题中。

并查集的基本操作

• 初始化UnionFind(int n)：每个元素初始化为自己的父节点。
• 查找int find(int x)：查找某个元素的根节点，并进行路径压缩以优化后续查找。
• 合并int find(int x)：将两个元素所在的集合合并为一个集合。

核心是

1. 同一个并查集内的元素会指向同一个parent
2. 维护并查集深度Rank，来按秩合并。
3. 数据结构用数组和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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 5;
    UnionFind uf(n);

    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);

    cout << "Is 0 and 2 connected? " << (uf.connected(0, 2) ? "Yes" : "No") << endl; // Yes
    cout << "Is 0 and 3 connected? " << (uf.connected(0, 3) ? "Yes" : "No") << endl; // No

    return 0;
}

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <iostream>
#include <map>
using namespace std;

class UnionFind {
public:
    map<int, int> parent;
    map<int, int> rank;

    // 初始化
    void makeSet(int x) {
        parent[x] = x;
        rank[x] = 0;
    }

    // 查找根节点，并进行路径压缩
    int find(int x) {
        if (parent.find(x) == parent.end()) {
            makeSet(x); // 如果 x 不存在，先初始化
        }
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并两个集合
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // 判断两个元素是否在同一个集合中
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    UnionFind uf;

    // 初始化一些元素
    uf.makeSet(1);
    uf.makeSet(2);
    uf.makeSet(3);
    uf.makeSet(4);
    uf.makeSet(5);

    // 合并一些集合
    uf.unite(1, 2);
    uf.unite(2, 3);
    uf.unite(4, 5);

    // 查询
    cout << "Is 1 and 3 connected? " << (uf.connected(1, 3) ? "Yes" : "No") << endl; // Yes
    cout << "Is 1 and 4 connected? " << (uf.connected(1, 4) ? "Yes" : "No") << endl; // No

    // 动态添加新元素并合并
    uf.unite(6, 7);
    cout << "Is 6 and 7 connected? " << (uf.connected(6, 7) ? "Yes" : "No") << endl; // Yes

    return 0;
}

容器适配器

C++ 中的容器适配器 stack、queue 和 priority_queue 依赖不同的基础容器来实现特定的数据结构行为。每种容器适配器都有特定的成员函数要求，默认选择的基础容器是为了更好地满足这些要求。

stack 栈

堆栈，先进先出

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

stack<int> minStack;
minStack = stack<int>();

// 支持初始化，但是注意将整个数组元素推入堆栈，堆栈的顶部元素top将是数组的第一个元素。
std::vector<int> elements = {1, 2, 3, 4, 5};
std::stack<int> myStack(elements.begin(), elements.end());

//增
s.push(x);  // 复制 x 到栈中
std::stack<std::pair<int, int>> s;
s.emplace(1, 2);  // 在栈中直接构造 std::pair<int, int> (1, 2)

//删
minStack.pop(); //该函数仅用于从堆栈中删除元素，并且没有返回值。因此，我们可以说该函数的返回类型为void。

//改

//查
!minStack.empty()
top_value = minStack.top();
stIn.size() //该函数返回堆栈容器的大小，该大小是堆栈中存储的元素数量的度量。

注意pop仅用于从堆栈中删除元素，并且没有返回值, 一般用法如下

1
2

top_value = stIn.top();
stIn.pop();

1
2
3
4
5
6
7

std::stack<int> myStack;
// 添加元素到 myStack

myStack = std::stack<int>(); // 清空 myStack, 丢弃原有对象

std::stack<int> emptyStack;
myStack.swap(emptyStack); // 清空 myStack

queue

1. 队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构；
2. 在队尾添加元素，在队头删除元素。

1
2
3
4
5
6
7
8

#include <queue>

// 初始化
queue<int> q;

// 相对于stack的操作, 没有top(), 但新增
q.front()               返回队首元素的值，但不删除该元素
q.back()                返回队列尾元素的值，但不删除该元素

1
2
3
4

queue<int> q1;
// process
// ...
q1 = queue<int>();

1
2
3
4

void clear(queue<int>& q) {
    queue<int> empty;
    swap(empty, q);
}

1
2
3
4
5
6
7
8

queue<pair<int, int>> gq;
gq.push({ 10, 20 });

pair<int, int> p;
int x,y;
p = gq.front();
x = p.first;
y = p.second;

deque 双端队列

deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。

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
35
36
37
38
39
40
41

#include <deque>
using namespace std;
std::deque<int> d;

//相对于stack queue支持迭代器，前两者可以强制通过reinterpret_cast来使用迭代器
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。

size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。

at() 使用经过边界检查的索引访问元素。

front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。

insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素，容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。
// 但是对于原始数据需要提供类型
vec.emplace_back<std::array<int, 4>>({1,2,3,4});
// or
vec.emplace_back(std::array<int, 4>{{1, 2, 3, 4}});

priority_queue(优先队列)

• 自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队
• 默认利用max-heap（大顶堆）完成对元素的排序，是以vector为表现形式的complete binary tree（完全二叉树）。
• 基本操作和queue一样。

初始化

1
2

#include <queue>
priority_queue<Type, Container, Functional>

1. Type 就是数据类型，
2. Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），
3. Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

排序规则

1
2
3
4
5

//降序队列(默认less<>), map/set默认也是使用less，但是是升序序列
priority_queue <int>q;
priority_queue <int,vector<int>,less<int> >q;
//升序队列
priority_queue <int,vector<int>,greater<int> > q;

1
2
3
4
5
6
7

class _c{
public:
    bool operator () (const pair<int, int> &p, const pair<int, int> &q) const {
        return p.first < q.first;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, _c> pq;

1
2
3
4
5
6
7
8
9
10
11

struct Compare {
    bool operator()(const std::pair<TimeType, ipType>& a, const std::pair<TimeType, ipType>& b) const {
        if (a.first == b.first)
            return a.second < b.second;  // 第一元素相等时按第二元素降序
        return a.first > b.first;         // 第一元素按升序排列
    }
};
class MyClass {
public:
    std::priority_queue<std::pair<TimeType, ipType>, std::vector<std::pair<TimeType, ipType>>, Compare> _arpQueue;
};

1
2
3
4
5
6
7
8
9
10
11
12

class MyClass {
public:
    // 比较函数作为静态成员函数
    static bool cmp(const std::pair<TimeType, ipType>& a, const std::pair<TimeType, ipType>& b) {
        if (a.first == b.first)
            return a.second < b.second;  // 第一元素相等时按第二元素降序
        return a.first > b.first;         // 第一元素按升序排列
    }

    // 使用比较函数指针初始化优先队列
    std::priority_queue<std::pair<TimeType, ipType>, std::vector<std::pair<TimeType, ipType>>, decltype(&MyClass::cmp)> _arpQueue{cmp};
};

1
2
3

//自定义降序2
auto cmp = [](pair<int,int>&a, pair<int,int>&b){return a.second<=b.second;};
priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> q(cmp);

单链表 （自定义）

一般是题目要求自己实现链表，而不是使用STL提供的链表list。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

ListNode* head = new ListNode(5);
//或者
ListNode* head = new ListNode();
head->val = 5;

while(result != nullptr && result->val == val){
    ListNode* tmp_free = result;
    result = result->next;
    delete tmp_free; // 注意释放空间
}

list 双向链表

STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。

• 特点：
  • 可以看到，list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。
  • vector是连续的容器，而list是非连续的容器，即vector将元素存储在连续的存储器中，而list存储在不连续的存储器中。
• 优点: list 容器具有一些其它容器（array、vector 和 deque）所不具备的优势
  • 可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。
  • 并且在 list 容器中移动元素，也比其它容器的效率高。
• 缺点
  • 不能像 array 和 vector 那样，通过位置直接访问元素。
    • 举个例子，如果要访问 list 容器中的第 6 个元素，它不支持容器对象名[6]这种语法格式，
  • 也不支持find()语法，经常使用unorder_map<key, list<xxx>::iterator> listMap保存元素位置来加速查找。
    • 正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置。for (it = list.begin(); it != list.end(); it++) if (it->key == key) break;
  • 应用场景：需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。

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

//插入
push_front：在链表头部插入元素。
emplace_front(value_type&& val)
push_back：在链表尾部插入元素。
emplace_back(value_type&& val)
insert：在指定位置插入元素。list1.insert(list1.begin(), 0);
emplace(iterator pos, value_type val)

//删除
pop_front：删除链表头部的元素。
pop_back：删除链表尾部的元素。
erase：删除指定位置的元素。
remove：删除所有匹配的元素。
clear：清空链表。

//查询
size：返回链表的大小。
empty：检查链表是否为空。
front：返回链表的第一个元素。
back：返回链表的最后一个元素。
reverse：反转链表。
sort：对链表进行排序。

数组

1
2
3
4

int array[2][3] = {
  {0, 1, 2},
  {3, 4, 5}
    };

1
2
3
4
5
6
7

//直接初始化为0
int a[SIZE]={0};

#include<string.h>
int a[SIZE];
memset(a, 0, sizeof(a));
memset(a, 0, sizeof(int)*1000);//这里的1000是数组大小，需要多少替换下就可以了。 

1
2
3
4
5
6
7

//区分
//calloc() 函数是动态申请内存函数之一，相当于用malloc函数申请并且初始化一样，calloc函数会将申请的内存全部初始化为0。
int *res = (int*)calloc(numsSize, sizeof(int));
//方法二：
int *res = (int*)malloc(numsSize * sizeof(int));
memset(res, 0, numsSize * sizeof(int));
//错误写法： memset(res, 0, sizeof(res)); res是指针变量，不管 res 指向什么类型的变量，sizeof( res ) 的值都是 4。

1
2
3
4
5
6
7
8

int *p = new int();//此时p指向内存的单变量被初始化为0
int *p = new int (5);//此时p指向内存的单变量被初始化为5
int *p = new int[100]()//此时p指向数组首元素，且数组元素被初始化为0
//c++11 允许列表初始化，因此也有了以下几种形式形式
int *p = new int{}//p指向的单变量被初始化为0
int *p = new int{8}//p指向变量被初始化为8
int *p = new int[100]{}//p指向的数组被初始化为0
int *p = new int[100]{1,2,3}//p指向数组的前三个元素被初始化为1，2，3，后边97个元素初始化为0；

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

int ***array;
// 假定数组第一维为 m， 第二维为 n， 第三维为h
// 动态分配空间
array = new int **[m];
for( int i=0; i<m; i++ )
{
    array[i] = new int *[n];
    for( int j=0; j<n; j++ )
    {
        array[i][j] = new int [h];
    }
}
//释放
for( int i=0; i<m; i++ )
{
    for( int j=0; j<n; j++ )
    {
        delete[] array[i][j];
    }
    delete[] array[i];
}
delete[] array;

1
2
3
4
5

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        int f[n][26][26];

array

• 与数组同样,array对象的长度也是固定的,
• 分配空间的规则也与数组类似，
• 其效率与数组相同,但更方便,更安全。

1
2
3
4
5
6
7
8
9
10
11
12

#include <array>

// array<typeName, nElem> arr;
array<int, 5> ai;
array<double, 4> ad = {1.1,1.2,1.2,1.3};

//通过如下创建 array 容器的方式，可以将所有的元素初始化为 0 或者和默认元素类型等效的值：
std::array<double, 10> values {};
//使用该语句，容器中所有的元素都会被初始化为 0.0。

//二维
std::array<std::array<int, 2>, 3> m = { {1, 2}, {3, 4}, {5, 6} };

vector

vector是变长的连续存储：

• 对于简单的类型，是直接存储
• 对于复杂的类，存储的是，该元素的信息（比如新构造元素的begin地址,end地址,capacity信息)

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

vector<vector<int>> v2d(3,vector<int>(0));      // 间隔 6 个int
// vector<set<int>> v2d(3);                     // 间隔 12 个int 
// vector<unordered_set<int>> v2d(3);           // 间隔 14 个int 
// vector<map<int,int>> v2d(3);                 // 间隔 12 个int 
// vector<unordered_map<int,int>> v2d(3);       // 间隔 14 个int 

const int STEP = 6;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
    for(int j=0; j<STEP; j++)
        cout << " " << hex << *(int *)((void *)(&v2d[i])+j*4);
    cout << endl;
}

// add elements to v2d[0]
const int ADDNUM = 10;
for(int i = 0; i<ADDNUM; i++){
    v2d[0].emplace_back(2);
    // v2d[0].insert(i);
    // v2d[0][i]=i*i;
}

// check the space change
cout << "Ele[0] size : " << v2d[0].size() << endl;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
}

//check ele[0] location
cout << endl;
for(int i = 0; i<ADDNUM; i++){
    cout << " " << &v2d[0][i];
}

1
2
3
4
5

size() – 返回目前存在的元素数。即： 元素个数
capacity() – 返回容器能存储 数据的个数。 即：容器容量
reserve() --设置 capacity 大小
resize() --设置 size ，重新指定有效元素的个数 ，区别与reserve()指定 容量的大小
clear() --清空所有元素，把size设置成0，capacity不变

初始化

1
2
3
4
5
6
7
8
9
10

//创建一个vector,元素个数为nSize
vector(int nSize)

//指定值初始化，ilist5被初始化为包含7个值为3的int
//vector(int nSize,const t& t)
//创建一个vector，元素个数为nSize,且值均为t
vector<int> ilist5(7,3);

//区分列表初始化, 包含7 和 3两个元素
vector<int> ilist5{7,3};

1
2
3
4

//改变大小,预分配空间,增加 vector 的容量（capacity），但 size 保持不变。
vals.reserve(cnt.size());
// 将 vector 大小调整为 10，用 0 填充新位置
vec.resize(10, 0);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 二维vector, 两个维度的长度都未知时：
std::vector<std::vector<int>> matrix;

// 假设我们知道行数，但列数未知
int numRows = 3;

// 预先分配行数
matrix.resize(numRows);

// 动态添加列
matrix[0].push_back(1);
matrix[0].push_back(2);
matrix[1].push_back(3);
matrix[1].push_back(4);
matrix[2].push_back(5);

1
2
3
4
5
6
7
8
9
10
11
12
13

//已知一个维度，第二维度为空
// vector<vector<bool>> name (xSize, vector<bool>(ySize, false));
vector<vector<int>> alphaIndexList{26, vector<int>(0)};

//或者
vector<int> alphaIndexList[26];
alphaIndexList[i].push_back(x);

//两个都不知道 ，也可以使用指针
vector<int>* todo;
todo= &alphaIndexList[i];
int n = todo->size(); // (*todo).size();
for(auto &x: *todo)

增加

vector 也支持中间insert元素，但是性能远差于list。

1
2
3
4
5
6

void push_back(const T& x)      //向量尾部增加一个元素X
void emplace_back(const T& x)
//iterator insert(iterator it,const T& x)   :向量中迭代器指向元素前增加一个元素x
result.insert(result.begin()+p,x);     :在result的index为p的位置插入元素
iterator insert(iterator it,int n,const T& x) :向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

删除

1
2
3
4

iterator erase(iterator it)     :删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back()        :删除向量中最后一个元素
void clear()        :清空向量中所有元素

修改

1
2
3
4
5
6
7

void swap(vector&)    :交换两个同类型向量的数据
void assign(int n,const T& x) :设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

#include <algorithm> //或者#include <bits/stdc++.h>
reverse(a.begin(), a.end());
std::reverse(a,a+5);  //转换0～5下标的元素

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

#include <algorithm>  // 包含 sort 函数
#include <functional> // 包含 std::greater 比较器

//默认是从低到高，加入std::greater<int>() 变成从高到低排序
sort(nums.begin(),nums.end(),std::greater<int>());

//vector of pair
vector<pair<int, char>> arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};

//c++11 using lambda and auto
std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});
// or
sort(arr.begin(), arr.end(),
    [](const pair<int, char> & p1, const pair<int, char> & p2) {
    return p1.first > p2.first;
    }
);

//origin
struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};
std::sort(v.begin(), v.end(), sort_pred());

1
2
3
4

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arrs2(First, Second); // 将值直接初始化到Arrs2

1
2
3
4
5

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arr2;
Arr2.assign(First,Second); //使用assign() 成员函数将Arrs对应位置的值存入Arrs2数组中

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

reference at(int pos)  :返回pos位置元素的引用
reference front()   :返回首元素的引用
reference back()   :返回尾元素的引用
iterator begin()   :返回向量头指针，指向第一个元素
iterator end()    :返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin() :反向迭代器，指向最后一个元素
reverse_iterator rend()  :反向迭代器，指向第一个元素之前的位置

// 判断函数
bool empty() const   :判断向量是否为空，若为空，则向量中无元素

// 大小函数
int size() const  :返回向量中元素的个数
int capacity() const :返回当前向量所能容纳的最大元素值
int max_size() const :返回最大可允许的vector元素数量值

其余

返回表示

1
2
3
4
5
6

vector<int> func() {
    //sth
    return {it->second, i}; //no []
    //or
    return {};
}

hash 哈希

1
2
3
4
5
6

#include<functional>
auto hash_p = [](const pair<int, int> &p) -> size_t {
            static hash<long long> hash_ll;
            return hash_ll(p.first + (static_cast<long long>(p.second) << 32));//64位高低一半存储x和y
        };

static_cast 用于良性类型转换，一般不会导致意外发生，风险很低。

hash <K> 模板专用的算法取决于实现，但是如果它们遵循 C++14 标准的话，需要满足一些具体的要求。这些要求如下：

• 不能拋出异常
• 对于相等的键必须产生相等的哈希值
• 对于不相等的键产生碰撞的可能性必须最小接近 size_t 最大值的倒数

参考文献

[^1]: How to use unordered_set with custom types?

https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

【C++容器】数组和vector、array三者区别和联系
https://blog.51cto.com/liangchaoxi/4056308

https://blog.csdn.net/y601500359/article/details/105297918

————————————————
版权声明：本文为CSDN博主「stitching」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40250056/article/details/114681940

————————————————
版权声明：本文为CSDN博主「FishBear_move_on」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/haluoluo211/article/details/80877558

————————————————
版权声明：本文为CSDN博主「SOC罗三炮」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/luolaihua2018/article/details/109406092

————————————————
版权声明：本文为CSDN博主「鱼思故渊」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yusiguyuan/article/details/40950735

可执行文件历史溯源

• COFF是32位System V平台上使用的一种格式。
  • 它允许使用共享库和调试信息。
  • 然而，它在节的最大数量和节名称的长度限制方面存在缺陷。
  • 它也不能提供C++等语言的符号调试信息。
• 然而，像XCOFF(AIX)和ECOFF(DEC，SGI)这样的扩展克服了这些弱点，并且有一些版本的Unix使用这些格式。
• Windows的PE+格式也是基于COFF的。
  可见可执行文件在不同平台上的规则还是有所不同的，后续会以UNIX ELF来分析

ELF 可执行目标文件

可执行目标文件的格式类似于可重定位目标文件的格式。

1. ELF 头描述文件的总体格式。它还包括程序的入口点（entry point），也就是当程序运行时要执行的第一条指令的地址。
2. .text、.rodata 和 .data 节与可重定位目标文件中的节是相似的，除了这些节已经被重定位到它们最终的运行时内存地址以外。
3. .init 节定义了一个小函数，叫做 _init，程序的初始化代码会调用它。
4. 因为可执行文件是完全链接的（已被重定位），所以它不再需要 .rel 节。

可重定位目标文件

• 下面内容来自 深入理解计算机系统（CSAPP）的7.4 可重定位目标文件一节
• 图 7-3 展示了一个典型的 ELF 可重定位目标文件的格式。
• ELF 头（Executable Linkable Format header）
  • 以一个 16 字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。
  • ELF 头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。
    • 其中包括 ELF 头的大小、目标文件的类型（如可重定位、可执行或者共享的）、机器类型（如 X86-64）、节头部表（section header table）的文件偏移，以及节头部表中条目的大小和数量。
• 节头部表描述不同节的位置和大小，其中目标文件中每个节都有一个固定大小的条目（entry）。

夹在 ELF 头和节头部表之间的都是节。一个典型的 ELF 可重定位目标文件包含下面几个节：

• .text：已编译程序的机器代码。
  • 通常代码区是可共享的（即另外的执行程序可以调用它），使其可共享的目的是对于频繁被执行的程序，只需要在内存中有一份代码即可。
  • 代码区通常是只读的，使其只读的原因是防止程序意外地修改了它的指令。
• .rodata：只读数据，比如 printf 语句中的格式串和开关语句的跳转表。
• .data：已初始化的全局和静态 C 变量。
  • 已经初始化的全局变量、已经初始化?的静态变量（包括全局静态变量和局部静态变量）和常量数据（如字符串常量）。
  • 局部 C 变量在运行时被保存在栈中，既不岀现在 .data 节中，也不岀现在 .bss 节中。
• .bss：未初始化的全局和静态 C 变量，以及所有被初始化为 0 的全局或静态变量。
  • 在目标文件中这个节不占据实际的空间，它仅仅是一个占位符。
  • 目标文件格式区分已初始化和未初始化变量是为了空间效率：在目标文件中，未初始化变量不需要占据任何实际的磁盘空间。运行时，在内存中分配这些变量，初始值为 0。
    • 用术语 .bss 来表示未初始化的数据是很普遍的。它起始于 IBM 704 汇编语言（大约在 1957 年）中“块存储开始（Block Storage Start）”指令的首字母缩写，并沿用至今。
  • 区分 .data 和 .bss 节的简单方法是把 “bss” 看成是“更好地节省空间（Better Save Space）” 的缩写。
• .symtab：一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。
  • 一些程序员错误地认为必须通过 -g 选项来编译一个程序，才能得到符号表信息。实际上，每个可重定位目标文件在 .symtab 中都有一张符号表（除非程序员特意用 STRIP 命令去掉它）。
  • 然而，和编译器中的符号表不同，.symtab 符号表不包含局部变量的条目。
• .rel.text：一个 .text 节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。
  • 一般而言，任何调用外部函数或者引用全局变量的指令都需要修改。另一方面，调用本地函数的指令则不需要修改。
  • 注意，可执行目标文件中并不需要重定位信息，因此通常省略，除非用户显式地指示链接器包含这些信息。
• .rel.data：被模块引用或定义的所有全局变量的重定位信息。
  • 一般而言，任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改。
• .debug：一个调试符号表，其条目是
  • 程序中定义的局部变量和类型定义，
  • 程序中定义和引用的全局变量，
  • 以及原始的 C 源文件。
  • 只有以 -g 选项调用编译器驱动程序时，才会得到这张表。
• .line：原始 C 源程序中的行号和 .text 节中机器指令之间的映射。
  • 只有以 -g 选项调用编译器驱动程序时，才会得到这张表。
• .strtab：一个字符串表，其内容包括 .symtab 和 .debug 节中的符号表，以及节头部中的节名字。字符串表就是以 null 结尾的字符串的序列。

符号和符号表

每个可重定位目标模块 m 都有一个符号表**.symtab**，它包含 m 定义和引用的符号的信息。在链接器的上下文中，有三种不同的符号：

• (出)由模块 m 定义并能被其他模块引用的全局符号。

  • 全局链接器符号对应于非静态的 C 函数和全局变量。

• (入)由其他模块定义并被模块 m 引用的全局符号。

  • 这些符号称为外部符号，对应于在其他模块中定义的非静态 C 函数和全局变量。

• 只被模块 m 定义和引用的局部符号。

  • 对应于带 static 属性的 C 函数和全局变量。这些符号在模块 m 中任何位置都可见，但是不能被其他模块引用。

• 本地链接器符号和本地程序变量的不同是很重要的。

  • .symtab 中的符号表不包含对应于本地非静态程序变量的任何符号。
  • 这些符号在运行时在栈中被管理，链接器对此类符号不感兴趣。

• 有趣的是，定义为带有 C static 属性的本地过程变量是不在栈中管理的。

  • 相反，编译器在 .data 或 .bss 中为每个定义分配空间，并在符号表中创建一个有唯一名字的本地链接器符号。

实践：readelf

使用命令readelf -s simple.o 可以读取符号表的内容。

示例程序的可重定位目标文件 main.o 的符号表中的最后三个条目。

• 开始的 8 个条目没有显示出来，它们是链接器内部使用的局部符号。

• 全局符号 main 定义的条目，

  • 它是一个位于 .text 节
  • 偏移量为 0（即 value 值）处的 24 字节函数。

• 其后跟随着的是全局符号 array 的定义

  • 位于 .data 节
  • 偏移量为 0 处的 8 字节目标。

• 外部符号 sum 的引用。

• type 通常要么是数据，要么是函数。

  • 符号表还可以包含各个节的条目，以及对应原始源文件的路径名的条目。

• binding 字段表示符号是本地的还是全局的。

• Ndx=1 表示 .text 节

  • Ndx=3 表示 .data 节。
  • ABS 代表不该被重定位的符号；
  • UNDEF 代表未定义的符号，也就是在本目标模块中引用，但是却在其他地方定义的符号；

实践: 查看exe信息相关命令

1
2

# read ELF header
readelf -h naive

进一步思考

• 小结：开辟局部变量、全局变量、malloc空间会影响可执行文件大小吗？对应汇编如何？存放的位置？运行时如何？

  • 设计一个代码量小但是占空间很大的可执行文件。
    • 因为已经初始化的全局变量、已经初始化的静态变量（包括全局静态变量和局部静态变量）会存储在data段，所以这些变量的大小会影响可执行文件的大小。

• 

  • static 与 const效果一样。
  • 设计一个代码量小但是运行时占内存空间很大的可执行文件。
    • malloc的空间会影响运行时的内存空间，但是不会影响可执行文件的大小。

• 将exe各节内容可视化解释(虽然现在是二进制)

• 编译的时候，头文件是怎么处理的？

• data 与 bbs在存储时怎么区分全局与静态变量

  • 符号表为什么有全局变量的符号，这些静态局部变量不需要吗？应该是需要的

• 请给出 .rel.text .rel.data的实例分析