阅读更多
1 algorithm
1.1 Modifying Sequence Operations
std::copy
std::copy_if
std::copy_n
std::copy_backward
std::move
std::move_backward
std::fill
std::fill_n
std::transform
std::generate
std::generate_n
std::remove
std::remove_if
std::remove_copy
std::remove_copy_if
std::replace
std::replace_if
std::replace_copy
std::replace_copy_if
std::swap
std::swap_ranges
std::iter_swap
std::reverse
std::reverse_copy
std::rotate
std::rotate_copy
std::shift_left
std::shift_right
std::random_shuffle
std::shuffle
std::sample
std::unique
std::unique_copy
1.1.1 std::copy
1 |
|
1.1.2 std::transform
1 |
|
1.1.3 std::remove_if
用于将容器中满足条件的元素挪到最后,并返回指向这部分元素的起始迭代器,一般配合erase
一起用
1 |
|
1.2 Sorting operations
std::is_sorted
std::is_sorted_until
std::sort
std::partial_sort
std::partial_sort_copy
std::stable_sort
std::nth_element
std::merge
std::inplace_merge
1.2.1 std::sort
注意:comparator
要返回的是bool
,而非整型
1 |
|
1.2.2 std::merge
1 |
|
1.2.3 std::inplace_merge
1 |
|
1.3 Non-modifying Sequence Operations
std::all_of
std::any_of
std::none_of
std::for_each
std::for_each_n
std::count
std::count_if
std::mismatch
std::find
std::find_if
std::find_if_not
std::find_end
std::find_first_of
std::adjacent_find
std::search
std::search_n
std::max_element
:return iterator of the max elementstd::min_element
:return iterator of the min elementstd::max
std::min
1.3.1 std::for_each
1 |
|
1.4 Binary Search Operations (on sorted ranges)
std::lower_bound(first, last, value, comp)
: Searches for the first element in the partitioned range[first, last)
which is not ordered before value.std::upper_bound
: Searches for the first element in the partitioned range[first, last)
which is ordered after value.std::binary_search
std::equal_range
1.4.1 std::lower_bound & std::upper_bound
Case 1:
1 |
|
Output:
1 | 0,1,2,3,3,3,4,4,5,10,11,13, |
Case 2:
1 |
|
Output:
1 | 0,1,2,3,3,3,4,4,5,10,11,13, |
Case 3:
1 |
|
Output:
1 | (2, 1),(1, 1),(6, 2),(5, 2),(4, 2),(3, 2),(7, 3),(8, 4), |
1.5 Set Operations
std::set_intersection
std::set_union
std::set_difference
1 |
|
2 any
std::any
用于持有任意类型的对象,类似于Java中的java.lang.Object
std::any_cast
用于将any
对象转换成对应的类型。若类型错误则会抛出std::bad_any_cast
其实现方式也很直观,在堆上分配内存,用该分配的内存存储拷贝后的对象
1 |
|
3 atomic
compare_exchange_strong(T& expected_value, T new_value)
方法的第一个参数是个左值
- 当前值与期望值
expected_value
相等时,修改当前值为设定值new_value
,返回true - 当前值与期望值
expected_value
不等时,将期望值修改为当前值,返回false(这样更加方便循环,否则还得手动再读一次)
1 | std::atomic_bool flag = false; |
1 | result: 1, flag: 1, expected: 0 |
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 | -Thread 1- |
- 线程2的断言会成功,因为线程1对
n
和m
在store之前修改;线程2在load
之后,可以观察到m
的修改 - 但线程3的断言不一定会成功,因为
m
是和load/store
操作不相关的变量,线程3不一定能观察看到
4 chrono
4.1 clock
三种时钟:
steady_clock
:是单调的时钟。其绝对值无意义,只会增长,适合用于记录程序耗时。system_clock
:是系统的时钟,且系统的时钟可以修改,甚至可以网络对时。所以用系统时间计算时间差可能不准high_resolution_clock
:是当前系统能够提供的最高精度的时钟。它也是不可以修改的。相当于steady_clock
的高精度版本
1 | auto start = std::chrono::steady_clock::now(); |
4.2 time_point
1 |
|
5 filesystem
std::filesystem::copy
std::filesystem::copy_file
std::filesystem::exist
std::filesystem::file_size
std::filesystem::is_directory
std::filesystem::is_regular_file
std::filesystem::remove
std::filesystem::rename
6 fstream
6.1 std::ifstream
Case 1: Read entire content at one time.
1 |
|
Case 2: Read line.
1 |
|
Case 3: Read content separated by a specific delimiter.
1 |
|
std::ofstream
7 functional
std::less
,std::greater
,std::less_equal
,std::greater_equal
: Comparatorstd::function
:其功能类似于函数指针,在需要函数指针的地方,可以传入std::function
类型的对象(不是指针)std::bind
std::hash
: Function object, use it like thisstd::hash<int>()(5)
std::mem_fn
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
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
std::promise
std::future
9 iomanip
iomanip stands for input/output manipulators
-
std::get_time
: Refer to std::get_time for all supported time format. -
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
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;
} -
std::get_money
-
std::put_money
10 iostream
std::cout
std::cin
std::endl
std::boolalpha
std::noboolalpha
11 iterator
11.1 Stream Iterators
std::istream_iterator
std::ostream_iterator
std::istreambuf_iterator
std::ostreambuf_iterator
11.2 Operations
std::advance
std::distance
std::next
std::prev
1 |
|
1 | Number of elements in the vector: 5 |
11.3 Adaptors
std::make_reverse_iterator
std::make_move_iterator
make_const_iterator
12 limits
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 | void func(Widget*); |
在函数中保存智能指针
假如我们需要在函数中把这个智能指针保存起来,这个时候建议直接传值
1 | // 传参时发生拷贝,引用计数增加 |
这样的话,外部传过来值的时候,可以选择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 | class Demo : public std::enable_shared_from_this<Demo> { |
13.3 std::unique_ptr
release
是指让出控制权,不再管理生命周期,而不是释放。要释放的话可以用reset
方法,或者直接赋值成nullptr
1 |
|
13.4 std::weak_ptr
用于指向由std::shared_ptr
管理的对象,但不负责管理改对象的生命周期。也就是说,它指向的对象可能已经被析构了
1 |
|
13.5 Pointer Cast
std::static_pointer_cast
std::dynamic_pointer_cast
std::const_pointer_cast
std::reinterpret_pointer_cast
13.6 Reference
14 memory_resource
1 |
|
15 mutex
-
std::mutex
:不可重入的互斥量 -
std::recursive_mutex
:可重入的互斥量 -
std::lock_guard
- 直接使用
std::mutex
,如下面的例子。如果getVar
方法抛出异常了,那么就会导致m.unlock()
方法无法执行,可能会造成死锁
1
2
3
4mutex 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();
} - 直接使用
-
std::unique_lock
:比std::lock_guard
提供更多的操作,允许手动加锁解锁 -
std::condition_variable
- 需要链接
libpthread
库,否则wait
方法会立即唤醒,且编译不会报错 - 调用
wait
方法时,必须获取监视器。而调用notify
方法时,无需获取监视器 wait
方法被唤醒后,仍然处于获取监视器的状态
1
2
3
4
5std::mutex m;
std::condition_variable cv;
std::unique_lock<std::mutex> l(m);
cv.wait(l);
// wake up here, and still under lock - 需要链接
-
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
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
-
std::accumulate
1
2
3
4
5
6
7
8
9
10
11
12
13int 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;
} -
std::iota
:给指定区间以递增的方式赋值1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
std::optional
std::nullopt
1 |
|
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>
.
- 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
- 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
usesstd::vector
as its underlying container, but you can use other container types likestd::deque
. The chosen container must supportfront()
,push_back()
, andpop_back()
operations.
- This specifies the type of the underlying container used to store the elements of the queue. By default,
- Third Template Parameter -
Compare
:- This is a comparison function object that determines the order of priority of the elements. By default,
std::priority_queue
usesstd::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 usestd::greater<T>
as this parameter.
- This is a comparison function object that determines the order of priority of the elements. By default,
1 |
|
19 random
std::default_random_engine
std::uniform_int_distribution
:左闭右闭区间
20 ranges
ranges
可以看做是对于algorithm
中算法的封装,可以省去begin()
、end()
等调用,如下
1 |
|
21 stdexcept
std::logic_error
std::invalid_argument
std::domain_error
std::length_error
std::out_of_range
std::runtime_error
std::range_error
std::overflow_error
std::underflow_error
22 exception
-
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
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
4Exception thrown
g.~Foo() called during stack unwinding
Exception caught: test exception
f.~Foo() called normally -
std::current_exception
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
std::stringstream
std::istringstream
: Use this andstd::getline
to achieve the function of spliting a stringstd::ostringstream
1 |
|
23 shared_mutex
std::shared_mutex
std::shared_timed_mutex
std::shared_lock
24 string
std::string
: charstd::wstring
: wchar_tstd::u8string
: char8_tstd::u16string
: char16_tstd::u32string
: char32_tstd::to_string
std::string::npos
: This is a special value equal to the maximum value representable by the type size_type.std::getline
: getline reads characters from an input stream and places them into a string.
25 thread
std::thread::hardware_concurrency
std::this_thread
25.1 How to set thread name
pthread_setname_np/pthread_getname_np
,需要引入头文件<pthread.h>
,np
表示non-portable
,即平台相关prctl(PR_GET_NAME, name)/prctl(PR_SET_NAME, name)
,需要引入头文件<sys/prctl.h>
1 |
|
25.2 How to set thread affinity
下面示例代码用于测试各个CPU的性能
CPU_ZERO
:初始化CPU_SET
:添加与某个CPU的亲和性,可以多次设置不同的CPUCPU_ISSET
:判断是否与某个CPU存在亲和性pthread_setaffinity_np
:设置某个线程的CPU亲和性pthread_getaffinity_np
:获取某个线程的CPU亲和性
1 |
|
26 tuple
-
std::tuple
-
std::apply
:触发方法调用,其中,参数被分装在一个tuple
中1
2
3
4
5
6
7
8
9
10
11
12
13
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;
} -
std::tie
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}
27 type_traits
Standard library header <type_traits>
27.1 Helper Class
std::integral_constant
std::bool_constant
std::true_type
std::false_type
27.2 Primary type categories
std::is_void
std::is_null_pointer
std::is_integral
std::is_array
std::is_pointer
- …
27.3 Composite type categories
std::is_fundamental
std::is_arithmetic
std::is_scalar
std::is_reference
std::is_member_pointer
- …
27.4 Type properties
std::is_const
std::is_volatile
std::is_final
std::is_empty
std::is_abstract
- …
27.5 Supported operations
std::is_constructible
std::is_copy_constructible
std::is_assignable
std::is_copy_assignable
std::is_destructible
- …
27.6 Property queries
std::alignment_of
std::rank
std::extent
27.7 Type relationships
std::is_same
std::is_base_of
- …
27.8 Const-volatility specifiers
std::remove_cv
std::remove_const
std::remove_volatile
std::add_cv
std::add_const
std::add_volatile
27.9 References
std::remove_reference
std::add_lvalue_reference
std::add_rvalue_reference
27.10 Pointers
std::remove_pointer
std::add_pointer
27.11 Sign modifiers
std::make_signed
std::make_unsigned
27.12 Arrays
std::remove_extent
std::remove_all_extents
27.13 Miscellaneous transformations
std::enable_if_t
: Often used in SFINAE.std::conditional
std::underlying_type
: Get the underlying numeric type of enum type.std::void_t
: Often used in SFINAE.std::decay
: Applies reference-remove, cv-qualifiers-remove (const and volatile), 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
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;
}
27.14 Alias
using template
,用于简化上述模板。例如std::enable_if_t
等价于typename enable_if<b,T>::type
-
std::enable_if_t
-
std::conditional_t
-
std::remove_reference_t
-
std::result_of_t
-
std::invoke_result_t
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
char create_char(char) {
return 0;
}
class Foo {
public:
static int create_int(int) { return 0; }
int create_double(int) { return 0; }
};
int main() {
std::invoke_result_t<decltype(create_char), char> c1;
std::invoke_result_t<decltype(&create_char), char> c2;
std::invoke_result_t<decltype(Foo::create_int), int> i1;
std::invoke_result_t<decltype(&Foo::create_int), int> i2;
// std::invoke_result_t<decltype(Foo::create_double), Foo, int> d1;
std::invoke_result_t<decltype(&Foo::create_double), Foo, int> d2;
return 0;
} -
…
27.15 std::move
Implementation:
1 | template<typename _Tp> |
Essentially, it performs a type transformation, and the returned type is guaranteed to be an rvalue.
For non-reference type parameters, using std::move during argument passing will invoke the move constructor to create the argument. Here’s an example:
1 |
|
27.16 std::forward
std::forward
主要用于实现模板的完美转发:因为对于一个变量而言,无论该变量的类型是左值引用还是右值引用,变量本身都是左值,如果直接将变量传递到下一个方法中,那么一定是按照左值来匹配重载函数的,而std::forward
就是为了解决这个问题。请看下面这个例子:
1 |
|
输出如下:
1 | dispatch_without_forward(value) -> left reference version |
在使用std::forward
时,模板实参都是需要显式指定的,而不是推断出来的
std::forward
标准库的实现如下:
- 如果模板实参是左值、左值引用或右值引用,那么匹配第一个方法
- 左值:
_Tp&&
得到的是个右值(很奇怪吧,因为一般都不是这么用的) - 左值引用:
_Tp&&
得到的是个左值引用(完美转发会用到) - 右值应用:
_Tp&&
得到的是个右值引用(完美转发会用到)
- 左值:
- 如果模板实参是左值或右值,那么匹配的是第二个方法
- 右值:
_Tp&&
得到的是个右值
- 右值:
1 | template<typename _Tp> |
27.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 |
|
上述程序正确的写法是:
1 |
|
28 unordered_map
29 unordered_set
Both equal
and hash
functions should be marked with const
1 |
|
30 utility
-
std::exchange
:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
} -
std::pair
:本质上,它是std::tuple
的一个特例 -
std::declval
:用来配合decltype
进行类型推导,其实现原理如下:__declval
是一个用于返回指定类型的方法(只有定义无实现,因为只用于类型推导)_Tp __declval(long);
版本用于void
这种类型,因为void
没有引用类型
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
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;
} -
std::integer_sequence
-
std::make_integer_sequence
-
std::integer_sequence
-
std::make_integer_sequence
30.1 How to return pair containing reference type
示例如下:
1 |
|
-
首先,我们先看一下
std::make_pair
的源码,如下:__decay_and_strip
:对于std::reference_wrapper
,会除去std::reference_wrapper
的封装,并返回引用类型;对于其他类型,则返回非引用类型
1
2
3
4
5
6
7
8
9
10template<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
,引用会正确初始化
31 variant
std::visit
std::variant
:类型安全的union。只允许以正确的类型进行访问std::get<{type}>
:通过指定类型访问std::get<{index}>
:通过指定序号访问
1 |
|
31.1 Dynamic Binding
std::variant
结合std::visit
可以实现动态分派,示例代码如下:
1 |
|
大致实现原理如下:
- 赋值时,会维护
std::variant::index
属性 - 每个
Visitor,variant
对会生成一个vtable
,里面记录了所有的函数指针,并按照std::variant
各个类型声明的顺序排序 - 在用
std::visit
进行访问时,会用std::variant::index
找到vtable
中的函数指针,并进行调用
32 Containers
<vector>
:其内部就是一个数组。当进行扩容缩容时,会进行数据的拷贝或移动,因此要求对应的类型至少拥有拷贝构造函数和移动构造函数中的一个。例如,std::vector<std::atomic_bool>
是无法调用push_back
或者emplace_back
来增加元素的<array>
<list>
<queue>
<deque>
:通过二级数组实现,第一级数组用于存放数据,第二级数组用于存放第一级数组的信息(首地址等)。当需要扩容时,会增加一个新的一级数组,而原有数据是不需要移动的<map>
<unordered_map>
<set>
<unordered_set>
32.1 Tips
std::map
或者std::set
用下标访问后,即便访问前元素不存在,也会插入一个默认值。因此下标访问是非const
的- 容器在扩容时,调用的是元素的拷贝构造函数
std::vector<T> v(n)
会生成n
个对应元素的默认值,而不是起到预留n
个元素的空间的作用- 不要将
end
方法返回的迭代器传入erase
方法
33 SIMD
Header files for x86 SIMD intrinsics
<mmintrin.h>
:MMX<xmmintrin.h>
:SSE<emmintrin.h>
:SSE2<pmmintrin.h>
:SSE3<tmmintrin.h>
:SSSE3<smmintrin.h>
:SSE4.1<nmmintrin.h>
:SSE4.2<ammintrin.h>
:SSE4A<wmmintrin.h>
:AES<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
- …
34 C Standard Library
Since C++
is a superset of C
, the standard library of C
has also been added to the std
namespace, but the header files differ: xxx.h -> cxxx
. Among them, xxx.h
is the original C
standard library header file, and its symbols are not in any namespace; cxxx
is the corresponding C++
version of the header file, and its symbols are in the std
namespace.
cstddef
size_t
cstdint
int8_t/int16_t/int32_t/int64_t
cerrno
: The error codes for system calls and some library functions are written to the global variableerrno
.cstdio
std::tmpnam
: Use with caution for the following reasons:- 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
cstring
std::memset
: Use<num> * sizeof(<type>)
to obtain the length.std::memcpy
: Use<num> * sizeof(<type>)
to obtain the length.std::strcmp
: Compare twoconst char *
to check if they are identical.
cstdlib
- Memory Allocation Related
malloc/free
: Functions fromC
that can also be used inC++
.malloc
allocates memory of a specified size, andfree
releases the allocated memory.calloc
: Allocates a specified number of contiguous memory spaces and initializes them to 0.realloc
: Resizes previously allocated memory.aligned_alloc
: Allocates memory of a specified size and ensures it is aligned to a specific byte boundary.posix_memalign
: Allocates memory of a specified size and ensures it is aligned to a specified byte boundary.memalign
: Allocates memory of a specified size and ensures it is aligned to a specific byte boundary.valloc
: Allocates memory of a specified size and ensures it is aligned to the page size.pvalloc
: Allocates memory of a specified size and ensures it is aligned to the page size.
std::atexit
: Registers a hook method to be called upon program exit.std::system
: Used to execute commands.std::mkstemp
: Creates a temporary file, requiring a filename template where the last six characters areXXXXXX
, which will be replaced by random characters.std::atoi
std::atol
std::atoll
std::getenv
setenv
: A POSIX API, not included in the C++ standard library.
- Memory Allocation Related
cctype
std::isblank
: Returns true only for spaces and horizontal tabs.std::isspace
: Returns true for spaces, form feed, newline, carriage return, horizontal tab, and vertical tab.
- POSIX headers
fcntl.h
: Provides an interface for controlling file descriptors. It includes constants and function declarations for working with file descriptors, managing file locks, and configuring file options.unistd.h
: (Unix Standard) Provides access to the POSIX (Portable Operating System Interface) operating system API. It is available on Unix-based operating systems (like Linux and macOS) and offers a collection of system calls and library functions for various low-level operations.- General POSIX functions like
fork
,exec
,pipe
,getpid
. - File operations:
read
,write
,close
,lseek
. - Process management:
getuid
,setuid
.
- General POSIX functions like
signal.h
: Provides signal handling:signal
,sigaction
,raise
.pthread.h
: Provides thread operations:pthread_create
,pthread_join
,pthread_mutex_lock
.sys/stat.h
: Provides file status functions:stat
,fstat
,lstat
.
34.1 csignal
各种信号都定义在signum.h
这个头文件中
下面的示例代码用于捕获OOM
并输出当时的进程状态信息
- 化级别用
O0
,否则v.reserve
会被优化掉 ulimit -v 1000000
:设置进程最大内存./main <size>
:不断增大size
,可以发现VmPeak
和VmSize
不断增大。继续增大size
,当触发OOM
时,VmPeak
和VmSize
这两个值都很小,不会包含那个造成OOM
的对象的内存
1 |
|
34.2 Execute Command
1 |
|
35 Builtin Functions
6.63 Other Built-in Functions Provided by GCC
__builtin_unreachable
__builtin_prefetch
__builtin_expect
#define LIKELY(x) __builtin_expect(!!(x), 1)
#define UNLIKELY(x) __builtin_expect(!!(x), 0)
__builtin_bswap32
: Perform a byte-swap operation on a 32-bit integer. Byte-swapping reverses the byte order of a value, which is useful for handling data in systems with different endianness (e.g., converting between big-endian and little-endian formats).__builtin_offsetof(type, member)
: Calculate member’s offset.- One alternative implementation is:
#define my_offsetof(type, member) ((size_t) & (((type*)0)->member))
- One alternative implementation is:
36 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