vector

vector 的功能是长度可变的数组，他里面的数据存储在堆上。vector 是一个模板类，第一个模板参数是数组里元素的类型。

Functions

构造函数和 size

// ...
// vector 可以在构造时指定初始长度
// vector<int> a(4);
explicit vector(size_t n);
// 要创建 4 个 233 组成的数组就可以写：
// vector<int> a(4, 233);
// 等价于
// vector<int> a = {233, 233, 233, 233};
explicit vector(size_t n, int const &val);

// 通过 a.size() 获得数组的长度
size_t size() const noexcept;


// 利用初始化列表（C++11 新特性）在构造时就初始化其中元素的值
// vector<int> a = {6, 1, 7, 4}; 
// or
// vector<int> a{6, 1, 7, 4};
vector(initializer_list<int> list);


// 访问 vector 里的元素  还可以写入
int &operator[](size_t i) noexcept;
int const &operator[](size_t i) const noexcept;


// 为了防止不小心越界，可以用 a.at(i) 替代 a[i]
// at 函数会检测索引 i 是否越界
int &at(size_t i);
int const &at(size_t i) const;

// ...

explicit vector(size_t n); 显式构造函数会调用元素的默认构造函数，数字类型会初始化为 0，string 会初始化为空字符串，指针类型会初始化为 nullptr。

std::execution::par

capacity() 函数查询已经分配内存的大小，即最大容量；

1	`size_t capacity() const noexcept;`

size() 返回的其实是已经存储了数据的数组长度。size 范围内的数据都是初始化的。

size 到 capacity 之间的内存是没有初始化的。

另外，使用 reserve() 函数预留一定的容量，这样之后就不会出现容量不足而需要动态扩容影响性能了（前提是保证容量一定足够）。此外，还要注意 reserve 时也会移动元素。

1	`size_t reserve(size_t n);`

reserve() 只是申请内存，不做初始化。

resize

除了可以在构造函数中指定数组的大小，还可以之后再通过 resize 函数设置大小。

// vector<int> a(4);
// 等价于：
// vector<int> a;
// a.resize(4);
void resize(size_t n);
void resize(size_t n, int const &val);

调用 resize(n) 的时候，不足部分，会用 0 填充元素，原有元素会保持不变。

// vector<int> a = {1, 2};
// a.resize(4);
// 等价于：
// vector<int> a = {1, 2, 0, 0};

// vector<int> a = {1, 2, 3, 4, 5, 6};
// a.resize(4);
// 等价于：
// vector<int> a = {1, 2, 3, 4};

当 resize 的目标长度大于原有的容量（capacity）时，就需要重新分配一段更大的连续内存，并把原数组长度的部分移动过去，多出来的部分则用 0 来填充。导致元素的地址会有所改。

shrink_to_fit

当 resize 到一个更小的大小上时，多余的容量不会释放，而是继续保留。

shrink_to_fit 释放掉多余的容量，只保留刚好为 size() 大小的容量。

shrink_to_fit 会重新分配一段更小内存，他同样是会把元素移动到新内存中的，因此迭代器和指针也会失效。

1	`size_t shrink_to_fit();`

clear

clear 函数可以清空该数组，也就相当于把长度设为零，变成空数组。

容量(capacity)还是摆在那里，clear 仅仅只是把数组大小(size)标记为 0 而已。

要真正释放掉内存，可以在 clear 之后再调用 shrink_to_fit，这样才会让容量也变成 0（这时 vector 的 data 会返回 nullptr）。

// a.clear();
// 等价于：
// a.resize(0);   或   a = {};
void clear() noexcept;

push_back

// vector<int> a = {1, 2};
// a.push_back(3);
// 等价于：
// vector<int> a = {1, 2, 3};
void push_back(int const &val);
void push_back(int &&val);  // C++11 新增

pop_back 函数则是和 push_back 相反。

要注意的是 pop_back 函数的返回类型是 void，也就是没有返回值，如果需要获取删除的值，可以在 pop_back() 之前先通过 back() 获取末尾元素的值，实现 pop 效果。

data

data() 会返回指向数组中首个元素的指针，也就是等价于 &a[0]。由于 vector 是连续存储的数组，因此只要得到了首地址，下一个元素的地址只需指针 +1 即可。

1 2	`int data() noexcept; int const data() const noexcept;`

data() 指针是对 vector 的一种引用，实际对象生命周期仍由 vector 类本身管理。

用他来获取一个 C 语言原始指针 int *，很方便用于调用 C 语言的函数和 API 等，同时还能享受到 vector 容器 RAII 的安全性。

如果用 new/delete 或者 malloc/free 就很容易出现忘记释放内存的情况，造成内存泄露。而 vector 会在离开作用域时，自动调用解构函数，释放内存，就不必手动释放了，更安全。

如果需要在一个语句块外仍然保持 data() 对数组的弱引用有效，可以把语句块内的 vector 对象移动到外面的一个 vector 对象上。vector 在移动时指针不会失效：

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

vector<int> holder;

int main() {
    int *p;
    {
        vector<int> a = {1, 2, 3};
        p = a.data();
        cout << p[0] << endl;
        cout << p[0] << endl;
        holder = std::move(a);  // 延续生命周期
    }
    cout << p[0] << endl;
    return 0;
}

insert

insert 函数，他的第一个参数是要插入的位置（用迭代器表示），第二个参数则是要插入的值。

insert 在容量不足时，同样会造成重新分配以求扩容，会移动其中所有元素，这时所有之前保存的迭代器都会失效。

insert 函数，重复插入多个相同的值。或者直接插入一个初始化列表。或者另一个容器的起止迭代器。

a.insert(插入位置, 重复多少次, 插入的值);
a.insert(插入位置, {插入值1, 插入值2, ...});
a.insert(插入位置, b.begin(), b.end());
// 对于 C 语言的数据结构使用全局的 std::begin(), std::end() 函数
a.insert(插入位置, std::begin(c), std::end(c));

emplace

1	`iterator emplace (const_iterator pos, args...);`

args... 表示与新插入元素的构造函数相对应的多个参数。

emplace() 每次只能插入一个元素，而不是多个。

emplace() 高效之处在于，直接在容器申请内存之上进行构造。而 insert() 是先构造好对象，在拷贝或者移动到容器的内存中。

assign

和 insert 不同的是，他会把旧有的数组完全覆盖掉，变成一个新的数组。

a.assign(beg, end) 基本和 a = vector<int>(beg, end) 等价，唯一的区别是后者会重新分配内存，而前者会保留原来的容量不会释放掉。

template <class It>  // 这里 It 可以是其他容器的迭代器类型
void assign(It beg, It end);
// 把 vector 批量填满一个特定的值
void assign(size_t n, int const &val);
// 接受一个初始化列表作为参数
void assign(initializer_list<int> val);

a.assign({x, y, ...}) 和 a = {x, y, ...} 完全等价，都会保留原来的容量。而和 a = vector<int>{x, y, ...} 就不等价，这个会重新分配内存。

erase

erase 的复杂度最坏情况是删除第一个元素 O(n)。如果删的是最后一个元素则复杂度为 O(1)。因为 erase 会移动 pos 之后的那些元素，保持连续数据分配。

1
2
3

iterator erase(const_iterator pos);
// 批量删除一个区间
iterator erase(const_iterator beg, const_iterator end);

Iterator

为什么会有iterator设计的需要？

为不同容器提供一个更一般化的操作接口

假设需要一个print函数，要打印容器中字符元素。简单实现是：

void print(vector<char> const &a) {
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << endl;
    }
}

void print(string const &a) {
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << endl;
    }
}

...

vector 和 string 的底层都是连续的稠密数组，改用首地址指针和数组长度做参数。

这样 print 在无需知道容器具体类型的情况下，只用最简单的接口（首地址指针）就完成了遍历和打印的操作。

void print(char const *a, size_t n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << endl;
    }
}

int main() {
    vector<char> a = {'h', 'j', 'k', 'l'};
    print(a.data(), a.size());
    string b = {'h', 'j', 'k', 'l'};
    print(b.data(), b.size());
    return 0;
}

通过给指针加减运算，选择其中一部分连续的元素来打印。

再改变一些，改用首地址指针和尾地址指针。用指针作为迭代变量。

尾地址指针实际上是指向末尾元素再往后后一个元素的指针。

数组长度为 0 就是 begptr == endptr 的情况；endptr - begptr 来算出数组的长度；判断是否继续循环的条件为 ptr != endptr 。

template <class Ptr>
void print(Ptr begptr, Ptr endptr) {
    for (Ptr ptr = begptr; ptr != endptr; ++ptr) {
        auto value = *ptr;
        cout << value << endl;
    }
}

int main() {
    vector<char> a = {'h', 'j', 'k', 'l'};
    char const *abegptr = a.data();
    char const *aendptr = a.data() + a.size();
    print(abegptr, aendptr);
    
    vector<int> b = {1, 2, 3, 4};
    int const *bbegptr = b.data();
    int const *bendptr = b.data() + b.size();
    print(bbegptr, bendptr);
    return 0;
}

通过操作符重载，适配不同内存布局的容器类型

上述首指针和尾指针的组合方法，的确能胜任 vector 这种连续数组，但是对于 list 这种不连续的内存的容器就没辙了。

list<char>::iterator 是一个特殊定义过的类型，其具有 != 和 ++ 以及 * 这些运算符的重载。把 ++ 对应到链表的 curr = curr->next 上。

用起来就像普通的指针，但内部却通过运算符重载适配不同容器的特殊类，就是迭代器(iterator)，迭代器是 STL 中容器和算法之间的桥梁。

template <class Ptr>
void print(Ptr begptr, Ptr endptr) {
    for (Ptr ptr = begptr; ptr != endptr; ptr++) {
        auto value = *ptr;
        cout << value << endl;
    }
}

int main() {
    list<char> a = {'h', 'j', 'k', 'l'};
    list<char>::iterator begptr = a.begin();
    list<char>::iterator endptr = a.end();
    print(begptr, endptr);
    return 0;
}

++

++p 会返回自增后的值 p + 1，这和 p += 1 完全一样，同样因为返回的是一个左值引用。

p++ 会返回自增前的值 p，返回的是一个右值。后置自增需要先保存旧的迭代器，然后自增自己，再返回旧迭代器，可能会比较低效。

struct Iterator {
    Node* curr;
	
    // 无参++ 前置++
    Iterator& operator++() {
        curr = curr->next;
        return *this;
    }
	// 带参++ 后置++
    Iterator operator++(int) {
        Iterator tmp = *this;
        this->operator++();
        return tmp;
    }

    T& operator*() const { return curr->value; }

    bool operator!=(Iterator const& that) const {
    	return curr != that.curr; 
    }
};

同名函数只能通过参数列表类型来区分，这个 int 类型参数没有任何实际意义，只是为了区分不同的重载。

编译器会在 p++ 的时候自动改成调用 p.operator++(0)。

set

set会自动给其中的元素从小到大排序，set<T, CompT> CompT定义排序函数
set会去重
红黑树储存，不支持随机访问
高效的按值查找

Iterator

	提供的运算符重载	具有此迭代器的容器	对应的 C++20 concept
输入迭代器	*（可读取），!=，==，++（一次性）	istream_iterator	input_iterator
输出迭代器	*（可写入），!=，==，++（一次性）	back_insert_iterator	output_iterator
前向迭代器	*，!=，==，++	forward_list	forward_iterator
双向迭代器	*，!=，==，++，--	set，map，list	bidirectional_iterator
随机访问迭代器	*，!=，==，++，--，+，-，+=，-=，[]	vector，array，deque	random_access_iterator
迭代器外包装	和他所包装的迭代器保持一致	reverse_iterator	和所包装的迭代器一致

前向迭代器＞双向迭代器＞随机访问迭代器。

这意味着如果一个STL模板函数（比如std::find）要求迭代器是前向迭代器即可，那么也可以给他随机访问迭代器，因为前向迭代器是随机访问迭代器的子集。

set 不支持随机访问，没有提供 + 和 += 的重载。

std::next

set 的 + 3 访问，通过std::next实现：

1
2
3

set<int> a = {1, 2, 3};
set<int>::iterator a_it = a.begin();
a_it = std::next(a_it, 3);  // set[3]

std::advance 会就地自增：

1	`std::advance(a_it, 3); // 相当于+=`

next 和 advance 同样支持负数。

与 next 对应的有 std::prev ，向前访问。

此外 std::distance 可求出两个迭代器之间的距离。

Funtions

insert

1	`pair<iterator, bool> insert(int val);`

insert 函数的返回值是一个 pair 类型，也就是说他同时返回了两个值。其中第一个返回值指向插入/现有元素的迭代器；第二个返回值是 bool 类型，指示了插入是否成功。

pair 作为返回值，可以直接：

1 2	`... return {first, second};`

C++ 17 可以使用结构化绑定拆解 pair

auto [ok, it] = b_set.insert(3);
// 等价于
auto tmp = b_set.insert(3);
auto ok = tmp.first;
auto it = tmp.second;

find

1 2	`iterator find(int const &val) const; size_t count(int const &val) const;`

set.find(x) != set.end() 判断集合 set 中是否存在元素 x。相比 set.count(x) != 0 会高效一些。

erase

1 2	`size_t erase(int const &val); iterator erase(iterator first, iterator last);`

erase 返回一个整数，表示被他删除元素的个数。使用上比如：set.erase(std::prev(set.end())) 会删除集合中最大的元素。

erase 还支持输入两个迭代器作为参数。删除前开后闭区间 [beg, end) 内的元素。

关于区间，set.lower_bound(x) 找第一个大于等于 x 的元素。set.upper_bound(x) 找第一个大于 x 的元素。

1 2	`// 删除 [3, 6] 区间内的元素 a_set.erase(a_set.lower_bound(3), a_set.upper_bound(6));`

操作	实现方法
增	a.insert(x)
删	a.erase(x) 或者 a.erase(a.find(x))
改	一旦插入就无法修改，只能先删再增
查	a.find(x) != a.end() 或者 a.count(x)

容器转换

template <class ForwardIt>
explicit vector(ForwardIt beg, ForwardIt end);

template <class ForwardIt>
explicit set(ForwardIt beg, ForwardIt end);

vector 的构造函数可以接受任何前向迭代器。不一定是 vector 自己的迭代器哦，任何前向迭代器！而 set 是双向迭代器，覆盖了前向迭代器，满足要求。

反过来，可以把 vector 转成 set。set(b.begin(), b.end()) 。

所以可以实现简单的vector排序功能：

1
2
3

vector<int> arr = {4,3,1,5};
set<int> tmp(arr.begin(), arr.end());
arr.assign(tmp.begin(), tmp.end());  // assign 利用现有分配内存

clear

1
2
3

a_set.clear();
a_set = {};
a_set.erase(a_set.begin(), a_set.end());

emplace

1
2
3

pair<iterator,bool> emplace (Args&&... args);

iterator emplace_hint (const_iterator position, Args&&... args);

只需要传入构建新元素所需的数据即可，该方法可以自行利用这些数据构建出要添加的元素。

emplace_hint 方法需要额外传入一个迭代器，用来指明新元素添加到 set 容器的具体位置（新元素会添加到该迭代器指向元素的前面）。

相比具有同样功能的 insert() 方法，完成同样的任务，emplace() 和 emplace_hint() 的效率会更高。

multiset

multiset 是 set 不去重版本。使用类似。

支持等值区间查询。equal_range 返回的等值区间。

1	`pair<iterator, iterator> equal_range(int const &val) const;`

不同 set 成员函数

函数	含义	set	multiset	unordered_set
insert(x)	插入一个元素 x	√	√	√
erase(x)	删除所有等于 x 的元素	√	√	√
count(x)	有多少个等于 x 的元素	√，0或1	√	√，0或1
find(x)	指向第一个等于 x 的元素	√	√	√
lower_bound(x)	指向第一个大于等于 x 的元素	√	√	×
upper_bound(x)	指向第一个大于 x 的元素	√	√	×
equal_range(x)	所有等于 x 的元素所组成的区间	√	√	√

和 vector 的横向比较：

类型	去重	有序	查找	插入
vector	×	×	O(n)	O(1) ~ O(n)
set	√	√	O(logn)	O(logn)
multiset	×	√	O(logn)	O(logn)
unordered_set	√	×	O(1)	O(1)
unordered_multiset	×	×	O(1)	O(1)

类型	lower/upper_bound	equal_range	find
vector	√，O(logn)	√，O(logn)	√，O(n)
set	√，O(logn)	√，O(logn)	√，O(logn)
multiset	√，O(logn)	√，O(logn)	√，O(logn)
unordered_set	×	√，O(1)	√，O(1)
unordered_multiset	×	√，O(1)	√，O(1)

unordered_set 的性能在数据量足够大（＞1000）时，平均查找时间比 set 短，但不保证稳定。set在数据量小时更高效。

Notes C++

C++ STL

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

optimizing software in cpp 上一篇

More Effective Cpp 下一篇

STL Tips

vector

Functions

构造函数和 size

resize

shrink_to_fit

clear

push_back

data

insert

emplace

assign

erase

Iterator

为不同容器提供一个更一般化的操作接口

通过操作符重载，适配不同内存布局的容器类型

++

set

Iterator

std::next

Funtions

insert

find

erase

容器转换

clear

emplace

multiset

不同 set 成员函数