Liuye Notebook
0%

Cpp-Standard-Library

发表于 更新于 分类于 阅读次数： Valine：

阅读更多

C++ Standard Library headers

1 algorithm

Standard library header

1.1 Modifying Sequence Operations

  1. std::copy
  2. std::copy_if
  3. std::copy_n
  4. std::copy_backward
  5. std::move
  6. std::move_backward
  7. std::fill
  8. std::fill_n
  9. std::transform
  10. std::generate
  11. std::generate_n
  12. std::remove
  13. std::remove_if
  14. std::remove_copy
  15. std::remove_copy_if
  16. std::replace
  17. std::replace_if
  18. std::replace_copy
  19. std::replace_copy_if
  20. std::swap
  21. std::swap_ranges
  22. std::iter_swap
  23. std::reverse
  24. std::reverse_copy
  25. std::rotate
  26. std::rotate_copy
  27. std::shift_left
  28. std::shift_right
  29. std::random_shuffle
  30. std::shuffle
  31. std::sample
  32. std::unique
  33. std::unique_copy

1.1.1 std::copy

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

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int32_t> source{1, 3, 5, 7, 9};

    std::vector<int32_t> dest1;
    std::copy(source.begin(), source.end(), std::back_inserter(dest1));
    std::copy(dest1.begin(), dest1.end(), std::ostream_iterator<int32_t>(std::cout, ","));
    std::cout << std::endl;

    std::vector<int32_t> dest2;
    dest2.resize(source.size());
    std::copy(source.begin(), source.end(), dest2.begin());
    std::copy(dest2.begin(), dest2.end(), std::ostream_iterator<int32_t>(std::cout, ","));
    std::cout << std::endl;

    return 0;
}

1.1.2 std::remove_if

用于将容器中满足条件的元素挪到最后，并返回指向这部分元素的起始迭代器，一般配合erase一起用

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> container{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    container.erase(std::remove_if(container.begin(), container.end(), [](int v) { return v % 2 != 0; }),
                    container.end());
    for (const auto& v : container) {
        std::cout << v << std::endl;
    }
    return 0;
}

1.2 Sorting operations

  1. std::is_sorted
  2. std::is_sorted_until
  3. std::sort
  4. std::partial_sort
  5. std::partial_sort_copy
  6. std::stable_sort
  7. std::nth_element
  8. std::merge
  9. std::inplace_merge

1.2.1 std::sort

注意：comparator要返回的是bool，而非整型

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
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int32_t> nums{1, 4, 2, 5, 7};

    std::sort(nums.begin(), nums.end());
    std::copy(nums.begin(), nums.end(), std::ostream_iterator<int32_t>(std::cout, ","));
    std::cout << std::endl;

    std::sort(nums.begin(), nums.end(), [](int32_t i, int32_t j) { return j < i; });
    std::copy(nums.begin(), nums.end(), std::ostream_iterator<int32_t>(std::cout, ","));
    std::cout << std::endl;

    std::vector<std::vector<int>> intervals;
    intervals.emplace_back(std::vector<int>{1, 3});
    intervals.emplace_back(std::vector<int>{2, 6});
    intervals.emplace_back(std::vector<int>{8, 10});
    intervals.emplace_back(std::vector<int>{15, 18});

    // Get wrong order if using i1[0] - i2[0], should be i1[0] < i2[0] here
    std::sort(intervals.begin(), intervals.end(), [](auto& i1, auto& i2) { return i1[0] - i2[0]; });

    std::cout << intervals[0][0] << std::endl;

    return 0;
}

1.2.2 std::merge

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 <stdint.h>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int32_t> left{1, 3, 5, 7, 9};
    std::vector<int32_t> right{2, 4, 6, 8, 10};

    std::vector<int32_t> dest1;
    std::merge(left.begin(), left.end(), right.begin(), right.end(), std::back_inserter(dest1));
    std::copy(dest1.begin(), dest1.end(), std::ostream_iterator<int32_t>(std::cout, ","));
    std::cout << std::endl;

    std::vector<int32_t> dest2;
    dest2.resize(left.size() + right.size());
    std::merge(left.begin(), left.end(), right.begin(), right.end(), dest2.begin());
    std::copy(dest2.begin(), dest2.end(), std::ostream_iterator<int32_t>(std::cout, ","));
    std::cout << std::endl;

    return 0;
}

1.2.3 std::inplace_merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdint.h>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int32_t> nums{2, 4, 6, 8, 10, 1, 3, 5, 7, 9};

    std::vector<int32_t> dest;
    std::inplace_merge(nums.begin(), nums.begin() + 5, nums.end());
    std::copy(nums.begin(), nums.end(), std::ostream_iterator<int32_t>(std::cout, ","));
    std::cout << std::endl;

    return 0;
}

1.3 Non-modifying Sequence Operations

  1. std::all_of
  2. std::any_of
  3. std::none_of
  4. std::for_each
  5. std::for_each_n
  6. std::count
  7. std::count_if
  8. std::mismatch
  9. std::find
  10. std::find_if
  11. std::find_if_not
  12. std::find_end
  13. std::find_first_of
  14. std::adjacent_find
  15. std::search
  16. std::search_n
  17. std::max_element：return iterator of the max element
  18. std::min_element：return iterator of the min element
  19. std::max
  20. std::min

1.3.1 std::for_each

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdint.h>

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int32_t> nums{1, 3, 5, 7, 9};

    std::for_each(nums.begin(), nums.end(), [](int32_t num) { std::cout << num << ", "; });

    return 0;
}

1.4 Binary Search Operations (on sorted ranges)

  1. std::lower_bound: Returns an iterator pointing to the first element in the range [first, last) such that element < value (or comp(element, value)) is false, (i.e. that is greater than or equal to value), or last if no such element is found.
  2. std::upper_bound: Returns an iterator pointing to the first element in the range [first, last) such that value < element (or comp(value, element)) is true (i.e. that is strictly greater than value), or last if no such element is found.
  3. std::binary_search
  4. std::equal_range

1.4.1 std::lower_bound & std::upper_bound

Case 1:

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>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums{0, 1, 2, 3, 3, 3, 4, 4, 5, 10, 11, 13};

    auto find_lower_bound = [&nums](int target) {
        std::cout << "the lower_bound of " << target << " is: ";
        auto it = std::lower_bound(nums.begin(), nums.end(), target);
        if (it == nums.end()) {
            std::cout << "nullptr" << std::endl;
        } else {
            std::cout << *it << std::endl;
        }
    };

    for (int i = -1; i < 15; ++i) {
        find_lower_bound(i);
    }

    return 0;
}

Case 2:

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>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums{0, 1, 2, 3, 3, 3, 4, 4, 5, 10, 11, 13};

    auto find_upper_bound = [&nums](int target) {
        std::cout << "the upper_bound of " << target << " is: ";
        auto it = std::upper_bound(nums.begin(), nums.end(), target);
        if (it == nums.end()) {
            std::cout << "nullptr" << std::endl;
        } else {
            std::cout << *it << std::endl;
        }
    };

    for (int i = -1; i < 15; ++i) {
        find_upper_bound(i);
    }

    return 0;
}

Case 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
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
#include <algorithm>
#include <iostream>
#include <list>
#include <vector>

struct Value {
    size_t pos;
    int32_t val;
    Value(const size_t pos, const int32_t val) : pos(pos), val(val) {}

    static bool comp(const Value& v1, const Value& v2) { return v1.val < v2.val; }
};

std::ostream& operator<<(std::ostream& os, const Value& value) {
    os << "(" << value.pos << ", " << value.val << ")";
    return os;
}

int main() {
    auto lower_bound_insert = [](std::list<Value>& l, const Value& value) {
        l.insert(std::lower_bound(l.begin(), l.end(), value, Value::comp), value);
    };
    auto upper_bound_insert = [](std::list<Value>& l, const Value& value) {
        l.insert(std::upper_bound(l.begin(), l.end(), value, Value::comp), value);
    };

    {
        std::list<Value> l;
        lower_bound_insert(l, {1, 1});
        lower_bound_insert(l, {2, 1});
        lower_bound_insert(l, {3, 2});
        lower_bound_insert(l, {4, 2});
        lower_bound_insert(l, {5, 2});
        lower_bound_insert(l, {6, 2});
        lower_bound_insert(l, {7, 3});
        lower_bound_insert(l, {8, 4});
        std::copy(l.begin(), l.end(), std::ostream_iterator<Value>(std::cout, ","));
        std::cout << std::endl;
    }

    {
        std::list<Value> l;
        upper_bound_insert(l, {1, 1});
        upper_bound_insert(l, {2, 1});
        upper_bound_insert(l, {3, 2});
        upper_bound_insert(l, {4, 2});
        upper_bound_insert(l, {5, 2});
        upper_bound_insert(l, {6, 2});
        upper_bound_insert(l, {7, 3});
        upper_bound_insert(l, {8, 4});
        std::copy(l.begin(), l.end(), std::ostream_iterator<Value>(std::cout, ","));
        std::cout << std::endl;
    }

    return 0;
}

Output:

1
2
(2, 1),(1, 1),(6, 2),(5, 2),(4, 2),(3, 2),(7, 3),(8, 4),
(1, 1),(2, 1),(3, 2),(4, 2),(5, 2),(6, 2),(7, 3),(8, 4),

1.5 Set Operations

  1. std::set_intersection
  2. std::set_union
  3. std::set_difference
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
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

int main() {
    std::vector<int32_t> nums1{1, 2, 3, 4, 5, 6};
    std::vector<int32_t> nums2{3, 4, 5, 6, 7, 8};

    std::vector<int32_t> intersection_res;
    std::vector<int32_t> union_res;
    std::vector<int32_t> difference_res;

    std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), std::back_inserter(intersection_res));
    std::set_union(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), std::back_inserter(union_res));
    std::set_difference(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), std::back_inserter(difference_res));

    auto print = [](const std::string& name, const std::vector<int32_t>& nums) {
        std::cout << name << ": ";
        std::copy(nums.begin(), nums.end(), std::ostream_iterator<int32_t>(std::cout, ","));
        std::cout << std::endl;
    };

    print("intersection", intersection_res);
    print("union", union_res);
    print("difference", difference_res);

    return 0;
}

2 any

std::any用于持有任意类型的对象，类似于Java中的java.lang.Object

  • std::any_cast用于将any对象转换成对应的类型。若类型错误则会抛出std::bad_any_cast

其实现方式也很直观，在堆上分配内存，用该分配的内存存储拷贝后的对象

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 <any>
#include <iostream>

struct Object {
    Object() { std::cout << "Object()" << std::endl; }
    Object(const Object& obj) { std::cout << "Object(const Object& obj)" << std::endl; }
    Object(Object&& obj) { std::cout << "Object(Object&& obj)" << std::endl; }
    Object operator=(const Object&) = delete;
    Object operator=(Object&&) = delete;
};

int main() {
    Object obj1;
    Object obj2;

    std::cout << "declare any" << std::endl;
    std::any a1 = obj1;
    std::any a2 = std::move(obj2);

    std::cout << "any_cast" << std::endl;
    [[maybe_unused]] Object obj3 = std::any_cast<Object>(a1);

    std::cout << "any_cast reference" << std::endl;
    [[maybe_unused]] Object& obj4 = std::any_cast<Object&>(a2);

    return 0;
}

3 atomic

compare_exchange_strong(T& expected_value, T new_value)方法的第一个参数是个左值

  • 当前值与期望值expected_value相等时，修改当前值为设定值new_value，返回true
  • 当前值与期望值expected_value不等时，将期望值修改为当前值，返回false（这样更加方便循环，否则还得手动再读一次）
1
2
3
4
5
6
7
std::atomic_bool flag = false;
bool expected = false;

std::cout << "result: " << flag.compare_exchange_strong(expected, true)
              << ", flag: " << flag << ", expected: " << expected << std::endl;
std::cout << "result: " << flag.compare_exchange_strong(expected, true)
              << ", flag: " << flag << ", expected: " << expected << std::endl;
1
2
result: 1, flag: 1, expected: 0
result: 0, flag: 1, expected: 1

compare_exchange_weak(T& expected_value, T new_value)方法与strong版本基本相同，唯一的区别是weak版本允许偶然出乎意料的返回（相等时却返回了false），在大部分场景中，这种意外是可以接受的，通常比strong版本有更高的性能

3.1 std::memory_order

这是个枚举类型，包含6个枚举值

  • memory_order_relaxed
  • memory_order_consume
  • memory_order_acquire
  • memory_order_release
  • memory_order_acq_rel
  • memory_order_seq_cst

3.1.1 Sequential Consistency Ordering

memory_order_seq_cst属于这种内存模型

SC作为默认的内存序，是因为它意味着将程序看做是一个简单的序列。如果对于一个原子变量的操作都是顺序一致的，那么多线程程序的行为就像是这些操作都以一种特定顺序被单线程程序执行

该原子操作前后的读写（包括非原子的读写操作）不能跨过该操作乱序；该原子操作之前的写操作（包括非原子的写操作）都能被所有线程观察到

3.1.2 Relaxed Ordering

memory_order_relaxed属于这种内存模型

  • 不满足atomic-write happens-before atomic-read的规则
  • 同一个线程内，同一个原子变量的多个操作不可重排
  • 同一个线程内，不同原子变量之间的操作可以重排（x86不允许这么做）
  • 同一个线程内，normal write和atomic write允许重排（x86不允许这么做）
  • 同一个线程内，normal read和atomic read允许重排（x86不允许这么做）
  • 唯一能保证的是，不同线程看到的该变量的修改顺序是一致的

3.1.3 Acquire-Release Ordering

memory_order_release、memory_order_acquire、memory_order_acq_rel属于这种内存模型

memory_order_release用于写操作store，memory_order_acquire用于读操作load

  • memory_order_release「原子操作之前的读写（包括非原子的读写）」不能往后乱序；并且之前的写操作（包括非原子的写操作），会被使用acquire/consume的线程观察到，这里要注意它和seq_cst不同的是只有相关的线程才能观察到写变化，所谓相关线程就是使用acquire或consume模式加载同一个共享变量的线程；而seq_cst是所有线程都观察到了
  • memory_order_acquire「原子操作之后的读写」不能往前乱序；它能看到release线程在调用load之前的那些写操作
  • memory_order_acq_rel是memory_order_release与memory_order_acquire的合并，前后的读写都是不能跨过这个原子操作，但仅相关的线程能看到前面写的变化
  • memory_order_consume和memory_order_acquire比较接近，也是和memory_order_release一起使用的；和memory_order_acquire不一样的地方是加了一个限定条件：依赖于该读操作的后续读写不能往前乱序；它可以看到release线程在调用load之前那些依赖的写操作，依赖于的意思是和该共享变量有关的写操作

看个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
-Thread 1-
 n = 1
 m = 1
 p.store (&n, memory_order_release)

-Thread 2-
 t = p.load (memory_order_acquire);
 if (*t == 1)
    assert(m == 1);

-Thread 3-
 t = p.load (memory_order_consume);
 if (*t == 1)
    assert(m == 1);
  • 线程2的断言会成功，因为线程1对n和m在store之前修改；线程2在load之后，可以观察到m的修改
  • 但线程3的断言不一定会成功，因为m是和load/store操作不相关的变量，线程3不一定能观察看到

4 chrono

4.1 clock

三种时钟：

  1. steady_clock：是单调的时钟。其绝对值无意义，只会增长，适合用于记录程序耗时。
  2. system_clock：是系统的时钟，且系统的时钟可以修改，甚至可以网络对时。所以用系统时间计算时间差可能不准
  3. high_resolution_clock：是当前系统能够提供的最高精度的时钟。它也是不可以修改的。相当于steady_clock的高精度版本
1
2
3
4
5
auto start = std::chrono::steady_clock::now();
auto end = std::chrono::steady_clock::now();
auto nanos = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
auto now_nanos = std::chrono::duration_cast<std::chrono::nanoseconds>(
        std::chrono::steady_clock::now().time_since_epoch()).count();

4.2 time_point

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

int main() {
    using Clock = std::chrono::system_clock;
    // Convert from std::chrono::time_point to time_t
    Clock::time_point now_tp = Clock::now();
    time_t now_tt = Clock::to_time_t(now_tp);
    std::cout << "Current time (time_t): " << now_tt << std::endl;

    // Convert from time_t to std::tm (local time)
    std::tm now_tm = *std::localtime(&now_tt);
    std::cout << "Current time (std::tm): " << now_tm.tm_hour << ":" << now_tm.tm_min << ":" << now_tm.tm_sec
              << std::endl;

    // Convert from std::tm to std::chrono::time_point
    time_t back_to_tt = std::mktime(&now_tm);
    Clock::time_point back_to_tp = Clock::from_time_t(back_to_tt);
    std::cout << "Back to std::chrono::time_point" << std::endl;

    return 0;
}

5 filesystem

  1. std::filesystem::copy
  2. std::filesystem::copy_file
  3. std::filesystem::exist
  4. std::filesystem::file_size
  5. std::filesystem::is_directory
  6. std::filesystem::is_regular_file
  7. std::filesystem::remove
  8. std::filesystem::rename

6 fstream

6.1 std::ifstream

Case 1: Read entire content at one time.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <fstream>
#include <iostream>
#include <sstream>

int main() {
    std::ifstream ifs("main.cpp");
    std::stringstream ss;
    // Read entire content
    ss << ifs.rdbuf();
    std::cout << ss.str() << std::endl;
    ifs.close();
    return 0;
}

Case 2: Read line.

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

int main() {
    std::ifstream file("main.cpp");
    if (!file.is_open()) {
        std::cerr << "Error opening file" << std::endl;
        return 1;
    }

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

    file.close();
    return 0;
}

Case 3: Read content separated by a specific delimiter.

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

int main() {
    std::ifstream file("main.cpp");
    if (!file.is_open()) {
        std::cerr << "Error opening file" << std::endl;
        return 1;
    }

    std::string line;
    const char delimiter = ' ';
    while (std::getline(file, line, delimiter)) {
        std::cout << line << std::endl;
    }

    file.close();
    return 0;
}
  1. std::ofstream

7 functional

  1. std::less, std::greater, std::less_equal, std::greater_equal: Comparator
  2. std::function：其功能类似于函数指针，在需要函数指针的地方，可以传入std::function类型的对象（不是指针）
  3. std::bind
  4. std::hash: Function object, use it like this std::hash<int>()(5)
  5. std::mem_fn
  6. std::reference_wrapper 
    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
    #include <algorithm>
    #include <functional>
    #include <iostream>
    #include <iterator>
    #include <list>
    #include <numeric>
    #include <random>
    #include <vector>

    void print(auto const rem, const auto& c) {
        std::cout << rem;
        std::ranges::copy(c, std::ostream_iterator<int32_t>(std::cout, ","));
        std::cout << std::endl;
    }

    int main() {
        std::list<int> l(10);
        std::iota(l.begin(), l.end(), -4);
        // can't use shuffle on a list (requires random access), but can use it on a vector
        std::vector<std::reference_wrapper<int>> v(l.begin(), l.end());
        std::ranges::shuffle(v, std::mt19937{std::random_device{}()});
        print("Contents of the list: ", l);
        print("Contents of the list, as seen through a shuffled vector: ", v);
        std::cout << "Doubling the values in the initial list...\n";
        std::ranges::for_each(l, [](int& i) { i *= 2; });
        print("Contents of the list, as seen through a shuffled vector: ", v);

        return 0;
    }

7.1 Reference

8 future

  1. std::promise
  2. std::future

9 iomanip

iomanip stands for input/output manipulators

  1. std::get_time: Refer to std::get_time for all supported time format.

  2. std::put_time

    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 <chrono>
    #include <ctime>
    #include <iomanip>
    #include <iostream>
    #include <sstream>

    int main() {
        std::string date_str = "2023-09-15 20:30";
        std::tm tm = {};
        std::istringstream ss(date_str);

        ss >> std::get_time(&tm, "%Y-%m-%d %H:%M");
        if (ss.fail()) {
            std::cout << "Parse error." << std::endl;
        } else {
            std::cout << "Successfully parsed: "
                    << "Year: " << tm.tm_year + 1900 << ", Month: " << tm.tm_mon + 1 << ", Day: " << tm.tm_mday
                    << ", Hour: " << tm.tm_hour << ", Minute: " << tm.tm_min << std::endl;
        }

        auto now = std::chrono::system_clock::now();
        time_t now_c = std::chrono::system_clock::to_time_t(now);
        std::tm* now_tm = std::localtime(&now_c);

        std::cout << "Current time: " << std::put_time(now_tm, "%Y-%m-%d %H:%M:%S") << std::endl;
        return 0;
    }

  3. std::get_money

  4. std::put_money

10 iostream

  1. std::cout
  2. std::cin
  3. std::endl
  4. std::boolalpha
  5. std::noboolalpha

11 iterator

11.1 Stream Iterators

  1. std::istream_iterator
  2. std::ostream_iterator
  3. std::istreambuf_iterator
  4. std::ostreambuf_iterator

11.2 Operations

  1. std::advance
  2. std::distance
  3. std::next
  4. std::prev
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 <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Using std::distance to find the number of elements between two iterators
    auto first = numbers.begin();
    auto last = numbers.end();
    std::cout << "Number of elements in the vector: " << std::distance(first, last) << std::endl;
    std::cout << "Number of elements in the vector (reverse): " << std::distance(last, first) << std::endl;

    auto it = std::find(numbers.begin(), numbers.end(), 3);
    std::cout << "Distance between start and 3 is: " << std::distance(it, numbers.begin()) << std::endl;
    std::cout << "Distance between start and 3 is (reverse): " << std::distance(numbers.begin(), it) << std::endl;

    // Using std::advance to move an iterator by a specific number of positions
    it = numbers.begin();
    std::advance(it, 2); // Advance the iterator by 2 positions
    std::cout << "Value at position 2: " << *it << std::endl;

    // Using std::next to get an iterator pointing to an element at a specific position
    auto nextIt = std::next(numbers.begin(), 3); // Get an iterator to the element at position 3
    std::cout << "Value at position 3: " << *nextIt << std::endl;

    // Using std::prev to get an iterator pointing to an element at a specific position
    auto prevIt = std::prev(numbers.end(), 2); // Get an iterator to the element at position 3 from the end
    std::cout << "Value at position 3 from the end: " << *prevIt << std::endl;

    return 0;
}
1
2
3
4
5
6
7
Number of elements in the vector: 5
Number of elements in the vector (reverse): -5
Distance between start and 3 is: -2
Distance between start and 3 is (reverse): 2
Value at position 2: 3
Value at position 3: 4
Value at position 3 from the end: 4

12 limits

  1. std::numeric_limits
    • std::numeric_limits<int32_t>::max()

13 memory

13.1 std::shared_ptr

类型转换

  • std::static_pointer_cast
  • std::dynamic_pointer_cast
  • std::const_pointer_cast
  • std::reinterpret_pointer_cast

只在函数使用指针，但并不保存对象内容

假如我们只需要在函数中，用这个对象处理一些事情，但不打算涉及其生命周期的管理，也不打算通过函数传参延长shared_ptr 的生命周期。对于这种情况，可以使用raw pointer或者const shared_ptr&

1
2
3
void func(Widget*);
// 不发生拷贝，引用计数未增加
void func(const shared_ptr<Widget>&)

在函数中保存智能指针

假如我们需要在函数中把这个智能指针保存起来，这个时候建议直接传值

1
2
// 传参时发生拷贝，引用计数增加
void func(std::shared_ptr<Widget> ptr);

这样的话，外部传过来值的时候，可以选择move或者赋值。函数内部直接把这个对象通过move的方式保存起来

13.2 std::enable_shared_from_this

std::enable_shared_from_this能让一个由std::shared_ptr管理的对象，安全地生成其他额外的std::shared_ptr实例，原实例和新生成的示例共享所有权

  • 只能通过std::make_shared来创建实例（不能用new），否则会报错
  • 普通对象（非只能指针管理）调用std::enable_shared_from_this::shared_from_this方法，也会报错

有什么用途？当你持有的是某个对象的裸指针时（该对象的生命周期由智能指针管理），但此时你又想获取该对象的智能指针，此时就需要依赖std::enable_shared_from_this

  • 不能将this直接放入某个std::shared_ptr中，这样会导致delete野指针
1
2
3
4
5
6
7
8
9
10
class Demo : public std::enable_shared_from_this<Demo> {
};

int main() {
    auto ptr = std::make_shared<Demo>();
    auto another_ptr = ptr->shared_from_this();

    std::cout << ptr << std::endl;
    std::cout << another_ptr.get() << std::endl;
}

13.3 std::unique_ptr

  • release是指让出控制权，不再管理生命周期，而不是释放。要释放的话可以用reset方法，或者直接赋值成nullptr
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 <iostream>
#include <memory>

class Foo {
public:
    Foo() { std::cout << "ctor" << std::endl; }
    ~Foo() { std::cout << "dctor" << std::endl; }
};

int main(void) {
    {
        std::unique_ptr<Foo> u_ptr = std::make_unique<Foo>();
        u_ptr.release();
        std::cout << "after calling unique_ptr::release\n" << std::endl;
    }
    {
        std::unique_ptr<Foo> u_ptr = std::make_unique<Foo>();
        u_ptr.reset();
        std::cout << "after calling unique_ptr::reset\n" << std::endl;
    }
    {
        std::unique_ptr<Foo> u_ptr = std::make_unique<Foo>();
        u_ptr = nullptr;
        std::cout << "after assigning to nullptr direcly\n" << std::endl;
    }
    return 0;
}

13.4 std::weak_ptr

用于指向由std::shared_ptr管理的对象，但不负责管理改对象的生命周期。也就是说，它指向的对象可能已经被析构了

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 <iostream>
#include <memory>

int main() {
    auto print = [](auto& w_ptr) {
        if (auto ptr = w_ptr.lock()) {
            std::cout << "active" << std::endl;
        } else {
            std::cout << "inactive" << std::endl;
        }
    };
    std::shared_ptr<int32_t> s_ptr;
    std::weak_ptr<int32_t> w_ptr = s_ptr;

    print(w_ptr);

    s_ptr = std::make_shared<int32_t>(1);
    print(w_ptr);

    w_ptr = s_ptr;
    print(w_ptr);

    s_ptr.reset();
    print(w_ptr);

    return 0;
}

13.5 Reference

14 memory_resource

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 <memory_resource>

int main() {
    // Create a polymorphic allocator using the default memory resource
    std::pmr::polymorphic_allocator<int> allocator;

    // Allocate memory for an array of integers
    int* p = allocator.allocate(10);

    // Initialize the allocated memory
    for (int i = 0; i < 10; ++i) {
        p[i] = i;
    }

    // Do something with the allocated memory

    // Deallocate memory when done
    allocator.deallocate(p, 10);

    return 0;
}

15 mutex

  1. std::mutex：不可重入的互斥量

  2. std::recursive_mutex：可重入的互斥量

  3. std::lock_guard

    • 直接使用std::mutex，如下面的例子。如果getVar方法抛出异常了，那么就会导致m.unlock()方法无法执行，可能会造成死锁
    1
    2
    3
    4
    mutex m;
    m.lock();
    sharedVariable= getVar();
    m.unlock();
    • 一种优雅的方式是使用std::lock_guard，该对象的析构方法中会进行锁的释放，需要将串行部分放到一个{}中，当退出该作用域时，std::lock_guard对象会析构，并释放锁，在任何正常或异常情况下都能够释放锁
    1
    2
    3
    4
    5
    {
        std::mutex m;
        std::lock_guard<std::mutex> lockGuard(m);
        sharedVariable= getVar();
    }

  4. std::unique_lock：比std::lock_guard提供更多的操作，允许手动加锁解锁

  5. std::condition_variable

    • 需要链接libpthread库，否则wait方法会立即唤醒，且编译不会报错
    • 调用wait方法时，必须获取监视器。而调用notify方法时，无需获取监视器
    • wait方法被唤醒后，仍然处于获取监视器的状态
    1
    2
    3
    4
    5
    std::mutex m;
    std::condition_variable cv;
    std::unique_lock<std::mutex> l(m);
    cv.wait(l);
    // wake up here, and still under lock

  6. std::call_once、std::once_flag

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

    void say_hello() {
        std::cout << "hello world" << std::endl;
    }

    int main() {
        std::once_flag flag;
        std::vector<std::thread> threads;
        for (int i = 0; i < 10; i++) {
            threads.emplace_back([&]() { std::call_once(flag, say_hello); });
        }
        for (int i = 0; i < 10; i++) {
            threads[i].join();
        }
        return 0;
    }

15.1 Reference

16 numeric

  1. std::accumulate

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int main() {
        std::set<std::string> col = {"a", "b", "c"};

        std::string res = std::accumulate(std::begin(col),
                                        std::end(col),
                                        std::string(),
                                        [](const std::string &a, const std::string &b) {
                                            return a.empty() ? b
                                                            : a + ", " + b;
                                        });

        std::cout << res << std::endl;
    }

  2. std::iota：给指定区间以递增的方式赋值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include <algorithm>
    #include <iostream>
    #include <numeric>
    #include <ranges>
    #include <vector>

    int main() {
        std::vector<int> nums(10);
        std::iota(nums.begin(), nums.end(), 1);
        std::ranges::copy(nums, std::ostream_iterator<int32_t>(std::cout, ","));
        std::cout << std::endl;

        return 0;
    }

17 optional

  1. std::optional
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 <iostream>
#include <optional>

std::optional<std::string> create(bool flag) {
    if (flag) {
        return "Godzilla";
    } else {
        return {};
    }
}

int main() {
    create(false).value_or("empty"); // == "empty"
    create(true).value();            // == "Godzilla"
    // optional-returning factory functions are usable as conditions of while and if
    if (auto str = create(true)) {
        std::cout << "create(true) is true, str=" << str.value() << std::endl;
    } else {
        std::cout << "create(true) is false" << std::endl;
    }

    if (auto str = create(false)) {
        std::cout << "create(false) is true, str=" << str.value() << std::endl;
    } else {
        std::cout << "create(false) is false" << std::endl;
    }
}

18 queue

18.1 std::priority_queue

std::priority_queue in C++ Standard Template Library (STL) is a container adapter that provides functionality to maintain a collection of elements sorted by priority. It is typically implemented as a max-heap, meaning the largest element is always at the front of the queue. There are three template parameters in std::priority_queue, each serving a specific purpose:

  • First Template Parameter - T:
    • This represents the type of elements stored in the priority queue. For example, if you want a priority queue that stores integers, you would use std::priority_queue<int>.
  • Second Template Parameter - Container:
    • This specifies the type of the underlying container used to store the elements of the queue. By default, std::priority_queue uses std::vector as its underlying container, but you can use other container types like std::deque. The chosen container must support front(), push_back(), and pop_back() operations.
  • Third Template Parameter - Compare:
    • This is a comparison function object that determines the order of priority of the elements. By default, std::priority_queue uses std::less<T>, meaning that larger elements are considered to have higher priority. If you want a min-heap (where the smallest element is at the front), you can use std::greater<T> as this parameter.
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
#include <iostream>
#include <queue>
#include <vector>

struct Item {
    int32_t value;

    struct Cmp {
        bool operator()(const Item& i1, const Item& i2) { return i1.value < i2.value; }
    };
};

int main() {
    std::priority_queue<Item, std::vector<Item>, Item::Cmp> max_heap;

    max_heap.push({1});
    max_heap.push({2});
    max_heap.push({3});
    max_heap.push({4});
    max_heap.push({5});

    while (!max_heap.empty()) {
        std::cout << max_heap.top().value << std::endl;
        max_heap.pop();
    }

    return 0;
}

19 random

  1. std::default_random_engine
  2. std::uniform_int_distribution：左闭右闭区间

20 ranges

ranges可以看做是对于algorithm中算法的封装，可以省去begin()、end()等调用，如下

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

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main() {
    std::vector<int32_t> nums{1, 3, 5, 7, 9};

    std::for_each(nums.begin(), nums.end(), [](int32_t num) { std::cout << num << ","; });
    std::cout << std::endl;

    std::ranges::for_each(nums, [](int32_t num) { std::cout << num << ","; });
    std::cout << std::endl;

    std::ranges::copy(nums, std::ostream_iterator<int32_t>(std::cout, ","));

    return 0;
}

21 stdexcept

  1. std::logic_error
  2. std::invalid_argument
  3. std::domain_error
  4. std::length_error
  5. std::out_of_range
  6. std::runtime_error
  7. std::range_error
  8. std::overflow_error
  9. std::underflow_error

22 exception

  1. std::uncaught_exceptions

    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
    #include <exception>
    #include <iostream>
    #include <stdexcept>

    struct Foo {
        char id{'?'};
        int count = std::uncaught_exceptions();

        ~Foo() {
            count == std::uncaught_exceptions() ? std::cout << id << ".~Foo() called normally\n"
                                                : std::cout << id << ".~Foo() called during stack unwinding\n";
        }
    };

    int main() {
        Foo f{'f'};

        try {
            Foo g{'g'};
            std::cout << "Exception thrown\n";
            throw std::runtime_error("test exception");
        } catch (const std::exception& e) {
            std::cout << "Exception caught: " << e.what() << '\n';
        }
    }
    1
    2
    3
    4
    Exception thrown
    g.~Foo() called during stack unwinding
    Exception caught: test exception
    f.~Foo() called normally

  2. std::current_exception

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

    int main() {
        try {
            throw std::runtime_error("An error occurred");
        } catch (...) {
            std::exception_ptr ptr = std::current_exception();
            if (ptr) {
                try {
                    std::rethrow_exception(ptr);
                } catch (const std::exception& e) {
                    std::cout << "Caught exception: " << e.what() << std::endl;
                }
            } else {
                std::cout << "Caught unknown exception" << std::endl;
            }
        }
        return 0;
    }

22.1 sstring

  1. std::stringstream
  2. std::istringstream: Use this and std::getline to achieve the function of spliting a string
  3. std::ostringstream
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <sstream>
#include <string>

int main(int32_t argc, char* argv[]) {
    std::istringstream str("a,b,c,d,e,f,g");
    std::string next;
    while (std::getline(str, next, ',')) {
        std::cout << next << std::endl;
    }

    return 0;
}

23 string

  1. std::string
  2. std::to_string
  3. std::string::npos: This is a special value equal to the maximum value representable by the type size_type.
  4. std::getline: getline reads characters from an input stream and places them into a string.

24 thread

  1. std::thread::hardware_concurrency
  2. std::this_thread

24.1 How to set thread name

  1. pthread_setname_np/pthread_getname_np，需要引入头文件<pthread.h>，np表示non-portable，即平台相关
  2. prctl(PR_GET_NAME, name)/prctl(PR_SET_NAME, name)，需要引入头文件<sys/prctl.h>
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
#include <pthread.h>
#include <sys/prctl.h>

#include <chrono>
#include <functional>
#include <iostream>
#include <sstream>
#include <thread>

void* change_thread_name(void* = nullptr) {
    // avoid change name before set original thread name
    std::this_thread::sleep_for(std::chrono::seconds(1));

    char original_thread_name[16];
    prctl(PR_GET_NAME, original_thread_name);
    uint32_t cnt = 0;

    while (true) {
        if (cnt > 1000) {
            cnt = 0;
        }

        std::stringstream ss;
        ss << original_thread_name << "-" << cnt++;
        prctl(PR_SET_NAME, ss.str().data());

        char current_thread_name[16];
        prctl(PR_GET_NAME, current_thread_name);
        std::cout << current_thread_name << std::endl;

        std::this_thread::sleep_for(std::chrono::seconds(1));
    }
    return nullptr;
}

void create_thread_by_pthread() {
    pthread_t tid;
    pthread_create(&tid, nullptr, change_thread_name, nullptr);
    pthread_setname_np(tid, "pthread");
    pthread_detach(tid);
}

void create_thread_by_std() {
    std::function<void()> func = []() { change_thread_name(); };
    std::thread t(func);
    pthread_setname_np(t.native_handle(), "std-thread");
    t.detach();
}

int main() {
    std::this_thread::sleep_for(std::chrono::milliseconds(333));
    create_thread_by_pthread();

    std::this_thread::sleep_for(std::chrono::milliseconds(333));
    create_thread_by_std();

    prctl(PR_SET_NAME, "main");
    change_thread_name();
}

24.2 How to set thread affinity

下面示例代码用于测试各个CPU的性能

  • CPU_ZERO：初始化
  • CPU_SET：添加与某个CPU的亲和性，可以多次设置不同的CPU
  • CPU_ISSET：判断是否与某个CPU存在亲和性
  • pthread_setaffinity_np：设置某个线程的CPU亲和性
  • pthread_getaffinity_np：获取某个线程的CPU亲和性
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
#include <pthread.h>

#include <iostream>

int main(int argc, char* argv[]) {
    pthread_t thread = pthread_self();

    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(1, &cpuset);
    CPU_SET(2, &cpuset);
    CPU_SET(3, &cpuset);
    CPU_SET(4, &cpuset);

    // Bind to core 1,2,3,4
    if (pthread_setaffinity_np(thread, sizeof(cpu_set_t), &cpuset) != 0) {
        return 1;
    }

    if (pthread_getaffinity_np(thread, sizeof(cpu_set_t), &cpuset) != 0) {
        return 1;
    }
    for (int i = 0; i < CPU_SETSIZE; i++) {
        if (CPU_ISSET(i, &cpuset)) {
            std::cout << "core " << i << " is set" << std::endl;
        }
    }

    return 0;
}

25 tuple

  1. std::tuple

  2. std::apply：触发方法调用，其中，参数被分装在一个tuple中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include <iostream>
    #include <tuple>
    #include <utility>

    int add(int a, int b) {
        return a + b;
    }

    int main() {
        std::cout << std::apply(add, std::make_tuple(1, 2)) << std::endl;
        std::cout << std::apply(add, std::make_pair(1, 2)) << std::endl;
        return 0;
    }

  3. std::tie

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

    #include <string>
    #include <tuple>

    std::pair<int32_t, std::string> createPair() {
        return std::pair<int32_t, std::string>(1, "Hello, World!");
    }

    std::tuple<int32_t, std::string, float> createTuple() {
        return std::tuple<int32_t, std::string, float>(2, "Hi, World!", 3.14f);
    }

    int main() {
        int32_t num;
        std::string str;

        std::tie(num, std::ignore) = createPair();
        std::tie(num, str, std::ignore) = createTuple();
        return 0;
    }

26 type_traits

Standard library header <type_traits>

26.1 Helper Class

  1. std::integral_constant
  2. std::bool_constant
  3. std::true_type
  4. std::false_type

26.2 Primary type categories

  1. std::is_void
  2. std::is_null_pointer
  3. std::is_integral
  4. std::is_array
  5. std::is_pointer
  6. …

26.3 Composite type categories

  1. std::is_fundamental
  2. std::is_arithmetic
  3. std::is_scalar
  4. std::is_reference
  5. std::is_member_pointer
  6. …

26.4 Type properties

  1. std::is_const
  2. std::is_volatile
  3. std::is_final
  4. std::is_empty
  5. std::is_abstract
  6. …

26.5 Supported operations

  1. std::is_constructible
  2. std::is_copy_constructible
  3. std::is_assignable
  4. std::is_copy_assignable
  5. std::is_destructible
  6. …

26.6 Property queries

  1. std::alignment_of
  2. std::rank
  3. std::extent

26.7 Type relationships

  1. std::is_same
  2. std::is_base_of
  3. …

26.8 Const-volatility specifiers

  1. std::remove_cv
  2. std::remove_const
  3. std::remove_volatile
  4. std::add_cv
  5. std::add_const
  6. std::add_volatile

26.9 References

  1. std::remove_reference
  2. std::add_lvalue_reference
  3. std::add_rvalue_reference

26.10 Pointers

  1. std::remove_pointer
  2. std::add_pointer

26.11 Sign modifiers

  1. std::make_signed
  2. std::make_unsigned

26.12 Arrays

  1. std::remove_extent
  2. std::remove_all_extents

26.13 Miscellaneous transformations

  1. std::enable_if
  2. std::conditional
  3. std::underlying_type：提取enum所继承的具体的int类型
  4. std::void_t
  5. std::decay：Applies reference-remove, array-to-pointer, and function-to-pointer implicit conversions to the type T 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include <type_traits>

    template <typename T, typename U>
    constexpr bool is_decay_equ = std::is_same_v<std::decay_t<T>, U>;

    int main() {
        static_assert(is_decay_equ<int&, int>);
        static_assert(is_decay_equ<int&&, int>);
        static_assert(is_decay_equ<const int&, int>);
        static_assert(is_decay_equ<int[2], int*>);
        static_assert(is_decay_equ<int[2][3], int(*)[3]>);
        static_assert(is_decay_equ<void(int, int), void (*)(int, int)>);
        return 0;
    }

26.14 Alias

using template，用于简化上述模板。例如std::enable_if_t等价于typename enable_if<b,T>::type

  1. std::enable_if_t
  2. std::conditional_t
  3. std::remove_reference_t
  4. std::result_of_t
  5. std::invoke_result_t
  6. …

26.15 std::move

标准库的实现如下：

1
2
3
4
template<typename _Tp>
  constexpr typename std::remove_reference<_Tp>::type&&
  move(_Tp&& __t) noexcept
  { return static_cast<typename std::remove_reference<_Tp>::type&&>(__t); }

本质上，就是做了一次类型转换，返回的一定是个右值

对于非引用类型的形参，传参时使用std::move，会调用移动构造函数来创建实参，示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

class Foo {
public:
    Foo() { std::cout << "Default ctor" << std::endl; }
    Foo(const Foo&) { std::cout << "Copy ctor" << std::endl; }
    Foo(Foo&&) { std::cout << "Move ctor" << std::endl; }
};

void test_foo(Foo foo) {
    std::cout << "test_foo" << std::endl;
}

int main() {
    Foo foo;
    test_foo(std::move(foo));
}

26.16 std::forward

std::forward主要用于实现模板的完美转发：因为对于一个变量而言，无论该变量的类型是左值引用还是右值引用，变量本身都是左值，如果直接将变量传递到下一个方法中，那么一定是按照左值来匹配重载函数的，而std::forward就是为了解决这个问题。请看下面这个例子：

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
#include <iostream>

std::string func(int& value) {
    return "left reference version";
}

std::string func(int&& value) {
    return "right reference version";
}

template <typename T>
std::string dispatch_without_forward(T&& t) {
    return func(t);
}

template <typename T>
std::string dispatch_with_forward(T&& t) {
    return func(std::forward<T>(t));
}

#define TEST(expr) std::cout << #expr << " -> " << expr << std::endl;

int main() {
    int value = 0;
    int& value_l_ref = value;
    auto get_r_value = []() { return 2; };

    TEST(dispatch_without_forward(value));
    TEST(dispatch_without_forward(value_l_ref));
    TEST(dispatch_without_forward(get_r_value()));
    TEST(dispatch_without_forward(1));
    std::cout << std::endl;

    TEST(dispatch_with_forward(value));
    TEST(dispatch_with_forward(value_l_ref));
    TEST(dispatch_with_forward(get_r_value()));
    TEST(dispatch_with_forward(1));
    std::cout << std::endl;

    TEST(func(std::forward<int>(value)));
    TEST(func(std::forward<int&>(value)));
    TEST(func(std::forward<int&&>(value)));
    std::cout << std::endl;

    TEST(func(std::forward<int>(value_l_ref)));
    TEST(func(std::forward<int&>(value_l_ref)));
    TEST(func(std::forward<int&&>(value_l_ref)));
    std::cout << std::endl;

    TEST(func(std::forward<int>(get_r_value())));
    TEST(func(std::forward<int&&>(get_r_value())));
    std::cout << std::endl;

    TEST(func(std::forward<int>(1)));
    TEST(func(std::forward<int&&>(1)));

    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
dispatch_without_forward(value) -> left reference version
dispatch_without_forward(value_l_ref) -> left reference version
dispatch_without_forward(get_r_value()) -> left reference version
dispatch_without_forward(1) -> left reference version

dispatch_with_forward(value) -> left reference version
dispatch_with_forward(value_l_ref) -> left reference version
dispatch_with_forward(get_r_value()) -> right reference version
dispatch_with_forward(1) -> right reference version

func(std::forward<int>(value)) -> right reference version
func(std::forward<int&>(value)) -> left reference version
func(std::forward<int&&>(value)) -> right reference version

func(std::forward<int>(value_l_ref)) -> right reference version
func(std::forward<int&>(value_l_ref)) -> left reference version
func(std::forward<int&&>(value_l_ref)) -> right reference version

func(std::forward<int>(get_r_value())) -> right reference version
func(std::forward<int&&>(get_r_value())) -> right reference version

func(std::forward<int>(1)) -> right reference version
func(std::forward<int&&>(1)) -> right reference version

在使用std::forward时，模板实参都是需要显式指定的，而不是推断出来的

std::forward标准库的实现如下：

  • 如果模板实参是左值、左值引用或右值引用，那么匹配第一个方法
    • 左值：_Tp&&得到的是个右值（很奇怪吧，因为一般都不是这么用的）
    • 左值引用：_Tp&&得到的是个左值引用（完美转发会用到）
    • 右值应用：_Tp&&得到的是个右值引用（完美转发会用到）
  • 如果模板实参是左值或右值，那么匹配的是第二个方法
    • 右值：_Tp&&得到的是个右值
1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type& __t) noexcept
  { return static_cast<_Tp&&>(__t); }

template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
  {
    static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
                  " substituting _Tp is an lvalue reference type");
    return static_cast<_Tp&&>(__t);
  }

26.16.1 forwarding reference

当且仅当T是函数模板的模板类型形参时，T&&才能称为forwarding reference，而其他任何形式，都不是forwarding reference。例如如下示例代码：

  • std::vector<T>&&就不是forwarding reference，而只是一个r-value reference
  • C(T&& t)中的T&&也不是forwarding reference，因为类型T在实例化C时，已经可以确定了，无需推导
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 <type_traits>
#include <vector>

class S {};

template <typename T>
void g(const T& t);
template <typename T>
void g(T&& t);

template <typename T>
void gt(T&& t) {
    g(std::move(t)); // Noncompliant : std::move applied to a forwarding reference
}

void use_g() {
    S s;
    g(s);
    g(std::forward<S>(s)); // Noncompliant : S isn't a forwarding reference.
}

template <typename T>
void foo(std::vector<T>&& t) {
    std::forward<T>(t); // Noncompliant : std::vector<T>&& isn't a forwarding reference.
}

template <typename T>
struct C {
    // In class template argument deduction, template parameter of a class template is never a forwarding reference.
    C(T&& t) {
        g(std::forward<T>(t)); // Noncompliant : T&& isn't a forwarding reference. It is an r-value reference.
    }
};

上述程序正确的写法是：

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
#include <type_traits>
#include <vector>

class S {};

template <typename T>
void g(const T& t);
template <typename T>
void g(T&& t);

template <typename T>
void gt(T&& t) {
    g(std::forward(t));
}

void use_g() {
    S s;
    g(s);
    g(std::move(s));
}

template <typename T>
void foo(std::vector<T>&& t) {
    std::move(t);
}

template <typename T>
struct C {
    C(T&& t) { g(std::move(t)); }
};

27 unordered_map

28 unordered_set

Both equal and hash functions should be marked with const

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
#include <functional>
#include <iostream>
#include <unordered_set>

struct Item {
    int32_t value1;
    int32_t value2;

    bool operator==(const Item& other) const { return value1 == other.value1 && value2 == other.value2; }

    struct Eq {
        auto operator()(const Item& i1, const Item& i2) const {
            return i1.value1 == i2.value2 && i1.value2 == i2.value2;
        }
    };

    struct Hash {
        auto operator()(const Item& i) const { return std::hash<int32_t>()(i.value1) ^ std::hash<int32_t>()(i.value2); }
    };
};

std::ostream& operator<<(std::ostream& os, const Item& item) {
    os << "(" << item.value1 << ", " << item.value2 << ")";
    return os;
}

int main() {
    {
        // Use member function operator== as equal function
        std::unordered_set<Item, Item::Hash> visited;

        auto add = [](auto& visited, const Item& item) {
            if (auto it = visited.insert(item); it.second) {
                std::cout << "add " << item << " successfully" << std::endl;
            } else {
                std::cout << item << " already exists" << std::endl;
            }
        };

        add(visited, {.value1 = 1, .value2 = 1});
        add(visited, {.value1 = 1, .value2 = 2});
        add(visited, {.value1 = 2, .value2 = 2});
        add(visited, {.value1 = 3, .value2 = 3});
        add(visited, {.value1 = 1, .value2 = 1});
    }

    {
        // Use type Item::Eq as equal function
        std::unordered_set<Item, Item::Hash, Item::Eq> visited;

        auto add = [](auto& visited, const Item& item) {
            if (auto it = visited.insert(item); it.second) {
                std::cout << "add " << item << " successfully" << std::endl;
            } else {
                std::cout << item << " already exists" << std::endl;
            }
        };

        add(visited, {.value1 = 1, .value2 = 1});
        add(visited, {.value1 = 1, .value2 = 2});
        add(visited, {.value1 = 2, .value2 = 2});
        add(visited, {.value1 = 3, .value2 = 3});
        add(visited, {.value1 = 1, .value2 = 1});
    }

    return 0;
}

29 utility

  1. std::exchange：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <iostream>
    #include <utility>
    #include <vector>

    int main() {
        std::vector<int32_t> nums{1, 2, 3, 4, 5};
        bool visit_first = false;
        for (size_t i = 0; i < nums.size(); ++i) {
            if (auto previous = std::exchange(visit_first, true)) {
                std::cout << ", ";
            }
            std::cout << nums[i];
        }
        return 0;
    }

  2. std::pair：本质上，它是std::tuple的一个特例

  3. std::declval：用来配合decltype进行类型推导，其实现原理如下：

    • __declval是一个用于返回指定类型的方法（只有定义无实现，因为只用于类型推导）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /// @cond undocumented
    template <typename _Tp, typename _Up = _Tp&&>
    _Up __declval(int);

    template <typename _Tp>
    _Tp __declval(long);
    /// @endcond

    template <typename _Tp>
    auto declval() noexcept -> decltype(__declval<_Tp>(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
    #include <iostream>
    #include <type_traits>
    #include <utility>

    struct Default {
        int foo() const { return 1; }
    };

    struct NonDefault {
        NonDefault(const NonDefault&) {}
        int foo() const { return 1; }
    };

    NonDefault get_non_default();

    int main() {
        decltype(Default().foo()) n1 = 1;
        // decltype(NonDefault().foo()) n2 = n1;               // will not compile
        decltype(std::declval<NonDefault>().foo()) n2 = 2;
        decltype(get_non_default().foo()) n3 = 3;
        std::cout << "n1 = " << n1 << std::endl;
        std::cout << "n2 = " << n2 << std::endl;
        std::cout << "n3 = " << n3 << std::endl;
        return 0;
    }

29.1 How to return pair containing reference type

示例如下：

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
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

class Thing {
public:
    std::pair<const std::vector<int>&, int> get_data_1() { return std::make_pair(_data, _data.size()); }
    std::pair<const std::vector<int>&, int> get_data_2() { return std::make_pair(std::ref(_data), _data.size()); }
    std::pair<const std::vector<int>&, int> get_data_3() {
        return std::pair<const std::vector<int>&, int>(_data, _data.size());
    }

private:
    std::vector<int> _data{1, 2, 3, 4, 5};
};

int main() {
    Thing t;

    auto printer = [](auto& pair) {
        std::ranges::copy(pair.first, std::ostream_iterator<int>(std::cout, ", "));
        std::cout << std::endl;
    };

    auto pair1 = t.get_data_1();
    // printer(pair1); // crash

    auto pair2 = t.get_data_2();
    printer(pair2);

    auto pair3 = t.get_data_3();
    printer(pair3);
    return 0;
}

  • 首先，我们先看一下std::make_pair的源码，如下：

    • __decay_and_strip：对于std::reference_wrapper，会除去std::reference_wrapper的封装，并返回引用类型；对于其他类型，则返回非引用类型
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    template<typename _T1, typename _T2>
    constexpr pair<typename __decay_and_strip<_T1>::__type,
                    typename __decay_and_strip<_T2>::__type>
    make_pair(_T1&& __x, _T2&& __y)
    {
        typedef typename __decay_and_strip<_T1>::__type __ds_type1;
        typedef typename __decay_and_strip<_T2>::__type __ds_type2;
        typedef pair<__ds_type1, __ds_type2> 	      __pair_type;
        return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
    }

  • get_data_1：错误方式。因为std::make_pair会创建类型为std::pair<std::vector<int>, int>的对象，然后再转型成std::pair<const std::vector<int>&, int>，于是引用会错误初始化（绑定到了临时对象），导致后续错误

  • get_data_2：正确方式。由于std::ref（返回类型是std::reference_wrapper）的存在，std::make_pair会创建类型为std::pair<const std::vector<int>&, int>的对象，此时引用会正确初始化

  • get_data_3：正确方式，不用std::make_pair，引用会正确初始化

30 variant

  1. std::visit
  2. std::variant：类型安全的union。只允许以正确的类型进行访问
    • std::get<{type}>：通过指定类型访问
    • std::get<{index}>：通过指定序号访问
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <variant>

int main() {
    std::variant<int, double> v;
    v = 1;
    std::cout << std::get<int>(v) << std::endl;
    v = 1.2;
    std::cout << std::get<1>(v) << std::endl;
    return 0;
}

30.1 Dynamic Binding

std::variant结合std::visit可以实现动态分派，示例代码如下：

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 <iostream>
#include <type_traits>
#include <variant>

void visit(std::variant<int, double>& v) {
    auto visitor = [](auto& item) {
        using type = std::remove_reference_t<decltype(item)>;
        if constexpr (std::is_integral_v<type>) {
            std::cout << "is integral" << std::endl;
        } else if constexpr (std::is_floating_point_v<type>) {
            std::cout << "is floating_point" << std::endl;
        }
    };
    std::visit(visitor, v);
}

int main() {
    std::variant<int, double> v;
    v = 1;
    visit(v);
    v = 1.2;
    visit(v);
    return 0;
}

大致实现原理如下：

  • 赋值时，会维护std::variant::index属性
  • 每个Visitor,variant对会生成一个vtable，里面记录了所有的函数指针，并按照std::variant各个类型声明的顺序排序
  • 在用std::visit进行访问时，会用std::variant::index找到vtable中的函数指针，并进行调用

31 Containers

  1. <vector>：其内部就是一个数组。当进行扩容缩容时，会进行数据的拷贝或移动，因此要求对应的类型至少拥有拷贝构造函数和移动构造函数中的一个。例如，std::vector<std::atomic_bool>是无法调用push_back或者emplace_back来增加元素的
  2. <array>
  3. <list>
  4. <queue>
  5. <deque>：通过二级数组实现，第一级数组用于存放数据，第二级数组用于存放第一级数组的信息（首地址等）。当需要扩容时，会增加一个新的一级数组，而原有数据是不需要移动的
  6. <map>
  7. <unordered_map>
  8. <set>
  9. <unordered_set>

31.1 Tips

  1. std::map或者std::set用下标访问后，即便访问前元素不存在，也会插入一个默认值。因此下标访问是非const的
  2. 容器在扩容时，调用的是元素的拷贝构造函数
  3. std::vector<T> v(n)会生成n个对应元素的默认值，而不是起到预留n个元素的空间的作用
  4. 不要将end方法返回的迭代器传入erase方法

32 SIMD

Header files for x86 SIMD intrinsics

  1. <mmintrin.h>：MMX
  2. <xmmintrin.h>：SSE
  3. <emmintrin.h>：SSE2
  4. <pmmintrin.h>：SSE3
  5. <tmmintrin.h>：SSSE3
  6. <smmintrin.h>：SSE4.1
  7. <nmmintrin.h>：SSE4.2
  8. <ammintrin.h>：SSE4A
  9. <wmmintrin.h>：AES
  10. <immintrin.h>：AVX, AVX2, FMA
    • 一般用这个即可，包含上述其他的头文件

注意，gcc、clang默认禁止使用向量化相关的类型以及操作，在使用上述头文件时，需要指定对应的编译参数：

  • -mmmx
  • -msse
  • -msse2
  • -msse3
  • -mssse3
  • -msse4
  • -msse4a
  • -msse4.1
  • -msse4.2
  • -mavx
  • -mavx2
  • -mavx512f
  • -mavx512pf, supports prefetching for gather/scatter, mentioned by Interleaved Multi-Vectorizing
  • -mavx512er
  • -mavx512cd
  • -mavx512vl
  • -mavx512bw
  • -mavx512dq
  • -mavx512ifma
  • -mavx512vbmi
  • …

33 C Standard Library

由于C++是C的超集，C的标准库也被添加到std命名空间中了，但是头文件有所区别：xxx.h -> cxxx。其中，xxx.h是原始的C标准库头文件，其符号不在任何命名空间中；cxxx是对应的C++版本的头文件，其符号在std命名空间中

  1. cstddef
    • size_t
  2. cstdint
    • int8_t/int16_t/int32_t/int64_t
  3. cerrno：系统调用以及一些库函数的错误码都会写入到errno这个全局变量中
  4. cstdio
    • std::tmpnam：慎用，原因如下：
      • The tmpnam() function generates a different string each time it is called, up to TMP_MAX times. If it is called more than TMP_MAX times, the behavior is implementation defined.
    • std::printf
  5. cstring
    • std::memset：用<num> * sizeof(<type>)来获取长度
    • std::memcpy：用<num> * sizeof(<type>)来获取长度
  6. cstdlib
    • 内存分配相关
      • malloc/free：C语言中的函数，在C++中也可以使用。malloc函数分配指定大小的内存，free函数释放该内存
      • calloc：分配指定数量的连续内存空间，并将其初始化为0
      • realloc：重新调整已经分配的内存空间的大小
      • aligned_alloc：分配指定大小的内存，并确保其对齐到特定的字节边界
      • posix_memalign：分配指定大小的内存，并确保其对齐到指定的字节边界
      • memalign：分配指定大小的内存，并确保其对齐到特定的字节边界
      • valloc：分配指定大小的内存，并确保其对齐到页的大小
      • pvalloc：分配指定大小的内存，并确保其对齐到页的大小
    • std::atexit：注册程序退出时的钩子方法
    • std::system：用于执行命令
    • std::mkstemp：创建临时文件，传入一个文件名模板，其最后留个字符为XXXXXX，这部分会替换为随机字符
    • std::atoi
    • std::atol
    • std::atoll
  7. cctype
    • std::isblank：仅对空格和水平制表符返回 true
    • std::isspace：空格、表单换行符、换行符、回车符、水平制表符和垂直制表符都返回true

33.1 csignal

各种信号都定义在signum.h这个头文件中

下面的示例代码用于捕获OOM并输出当时的进程状态信息

  • 化级别用O0，否则v.reserve会被优化掉
  • ulimit -v 1000000：设置进程最大内存
  • ./main <size>：不断增大size，可以发现VmPeak和VmSize不断增大。继续增大size，当触发OOM时，VmPeak和VmSize这两个值都很小，不会包含那个造成OOM的对象的内存
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
#include <csignal>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>

void display_self_status() {
    std::ifstream in("/proc/self/status");
    constexpr size_t BUFFER_SIZE = 512;
    char buf[BUFFER_SIZE];

    while (!in.eof()) {
        in.getline(buf, BUFFER_SIZE);
        std::cout << buf << std::endl;
    }

    in.close();
}

void func(int sig) {
    std::cout << "Cath a signal, sig=" << sig << std::endl;
    display_self_status();
    exit(sig);
}

int main(int argc, char* argv[]) {
    for (int sig = SIGHUP; sig <= SIGSYS; sig++) {
        signal(sig, func);
    }

    display_self_status();

    // trigger OOM
    std::vector<int64_t> v;
    v.reserve(std::atoi(argv[1]));

    display_self_status();

    return 0;
}

33.2 Execute Command

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdlib>
#include <fstream>
#include <iostream>

int main() {
    char file_name[] = "/tmp/fileXXXXXX";
    mkstemp(file_name);
    std::cout << "tmp_file=" << file_name << std::endl;
    std::system(("ls -l > " + std::string(file_name)).c_str());
    std::cout << std::ifstream(file_name).rdbuf();
    return 0;
}

34 Frequently-Used Compoments for Interview

Data Structure:

  • std::vector
  • std::list
    • splice
  • std::map
  • std::set
  • std::stack
  • std::queue
  • std::priority_queue

Algorithm:

  • std::sort
  • std::lower_bound,std::upper_bound : binary search.
  • std::find
  • std::remove_if: return the iterator pointing at the first elements to be removed.
  • std::erase_if: remove the specific elements.
  • std::set_intersection、std::set_union、std::set_difference

Function Objects:

  • std::hash
  • std::less/std::less_equals/std::greater/std::greater_equal
  • std::equal_to

I/O:

  • std::ifstream、std::ofstream
  • std::getline
  • std::get_time、std::put_time