0. 项目准备
容器用来存放元素，表面看是容器“管着”元素，但是，元素某些方面的特性，也会反过来影响容器的发挥。比如，一个元素是否能默认构造。
- 代码：
#include <iostream>
#include <vector>
// 没有显式提供默认构造函数，但可以默认构造的结构体
struct PointCStyle { int x, y; }
void testPointCStyleConstruct()
{
// OK:
PointCStyle p1;
PointCStyle p2 { 1 , 2 }
// fail:
// PointCStyle p3(); // 不推荐！
// PointCStyle p3(1, 2);
}
// 有显式默认构造函数的结构体
struct Point
{
int x, y;
Point() : x(0), y(0) {}; //包括 Point() = default;
Point(int x, int y) : x(x), y(y) {}
};
void testPointConstruct()
{
// OK:
Point p1;
// Point p2(); // 不推荐！有警告
Point p3 {1, 2};
Point p4 (1, 2);
}
// 明确禁止默认构造的结构体
struct PointWithoutDefaultConstructor
{
int x, y;
PointWithoutDefaultConstructor(int x, int y)
: x(x), y(y) {};
};
void testPointWithoutDefaultConstructor()
{
// fail:
//PointWithoutDefaultConstructor p1;
// OK
PointWithoutDefaultConstructor p2 {1, 2};
PointWithoutDefaultConstructor p3 (1, 2);
}
int main()
{}
1. 内存结构
std::vector 存储元素最主要的内存结构特点，就是 “连续存储”。所有元素按顺序整齐连续地存放。
vector 连续存储元素带来的最大好处是：可以对元素进行高效的 “随机访问”。
这里的 “随机”不是指随机数中的随机，而是指想要访问第N个元素，无需先访问第 N-1 个元素的意思。更简单一点的理解，就是只需要通过简单的算术计算，就能得到第 N 个元素的内存地址，从而直接访问该元素。
连续存储当然也有坏处——
首先，相比 “见缝插针”式的，可以将元素多处存放的容器，连续的内存比较珍贵，不容易找到。
其次，连续存储的内存结构，非常不利于插入操作。比如，现有五个元素，程序想在第一和第二个之间插入一个新元素，将造成现有的，二到五的元素，需要全部向后挪移一个位置——前提还得后面还有空闲内存，否则，只能另找一块足够大的内存，新老元素全部搬过去。
“大搬家”通常带来糟糕的性能，如何缓解？答：每当需要申请内存时，就多申请一些，称为 “预留” 或 “预分配”。
- 测试代码：
// 观察 观察 size 和 capacity 的关系
void testSizeAndCapacity(int n)
{
std::vector<int> v;
for (int i=0; i<n; ++i)
{
v.push_back(n);
}
if (v.empty())
{
std::cout << "empty!\n";
}
std::cout << "size:" << std::setw(2) << v.size()
<< ", capacity:" << std::setw(2) << v.capacity() << std::endl;
}
void testSizeAndCapacity()
{
for (int i=0; i<=32; ++i)
{
testSizeAndCapacity(i);
}
}
2. 构造 vector
- 默认构造：vector<int> v1； // 空的容器（通常预留空间也是0）
- 列表构造：vector<int> v2 {1, 2, 3}; // 含 1、2、3 三个元素
- 指个元素个数：vector<int> v3 (2); // 含2个默认整数（都是0）
- 指个元素个数及样本元素：vector<int> v3 (2, 9);// 含2个9
其中的3，要求元素本身必须能默认构造，如果元素是 PointWithoutDefaultConstructor ，则该方法无法通过编译。
- 测试代码：
void testConstruct()
{
// 默认构造
{
std::vector<int> v1;
std::vector<PointCStyle> v2;
std::vector<Point> v3;
std::vector<PointWithoutDefaultConstructor> v4;
}
// 初始化列表构造：
{
std::vector<int> v1 {8}; // 包含一个元素，值为 8
std::vector<int> v2 {1, 2, 4, 5, 6, 7};
std::vector<PointCStyle> v3 { {1, 2}, {10, 20} };
std::vector<Point> v4 { {-1, -2}, {10, -20}, { 9, 120 } };
std::vector<PointWithoutDefaultConstructor> v5 { {1, 2} };
}
// 带参构造
{
std::vector<int> v1 (8); // 包含八个 0
std::vector<int> v2 (8, 99); //包含八个 99
std::vector<Point> v3 (2);
// std::vector<PointWithoutDefaultConstructor> v4(1); // 失败
// 使用样板对象：
std::vector<PointWithoutDefaultConstructor> v4(1, PointWithoutDefaultConstructor(1, 2));
}
}
3. 随机访问
使用 [下标] 和 at (下标），都可以直接访问到由下标指定的元素（下标从0开始）。二者都是随机访问，主要区别在于：
- 使用 [] 访问不会检查下标的合法性，一旦下标过大（或为负数），程序将进入UB（未定义影响）的状态。
- 使用 at (下标) 则会检查下标的合法性，发现非法，抛出 std::out_of_range 异常。
- 测试代码：
#include <exception>
// 测试随机访问
void testRandomeAccess()
{
std::vector<int> v(6);
for (int i=0; i<6; ++i)
{
v[i] = i;
if (i > 0)
{
v[i] += v[i-1];
}
}
try
{
std::cout << v[5] << std::endl;
// std::cout << v[6] << std::endl; // UB！！！
std::cout << v.at(6) << std::endl;
}
catch(std::out_of_range const& e)
{
std::cerr << e.what() << std::endl;
}
}
4. 迭代器
迭代器的行为非常像指针（但比指针不容易出错），用于间接访问到容器内存的元素。迭代器类型通常定义在容器类型（模板）内部。
以 std::vector<T> 为例，在该类型（class）的内部，定义有如下四种迭代器类型：
- std::vector<T>::iterator // （正向）迭代器
- std::vector<T>::const_iterator // （正向）常量迭代器
- std::vector<T>::reverse_iterator // 逆向迭代器
- std::vector<T>::const_reverse_iterator // 常量逆向迭代器
对应的，std::vector<T>有四组方法，用于获取以上 1~4 类型的迭代器对象：
- begin() / end();
- cbegin() / cend();
- rbegin() / rend();
- crbegin() / crend();
其中，所有的 xbegin() 都用于取得指向（特定方向上）的第一个元素位置的迭代器，而所有 xend() 用于取对应方向上的最后一个元素之后的位置上的迭代器。
注意：“最后一个元素之后”的位置，显然，end() 位置已经越界，不可真实访问。
二者所表达的范围区间，在数学上可书写为 [ begin, end )，表示包含 begin, 但不包含 end 。称为 一段 “半开区间（half-open interval）”。
- 测试代码：
// 测试迭代器访问
void testIterator()
{
std::vector<int> vi { 10, 20 , 30 , 40};
// 显式使用迭代器
for (std::vector<int>::iterator it = vi.begin(); it != vi.end(); ++it)
{
*it += 5; // 写操作
}
for (auto it = vi.cbegin(); it != vi.cend(); ++it)
{
// *it += 1; // it 是 const_iterator
std::cout << *it << ", ";
}
std::cout << std::endl;
for (auto it = vi.crbegin(); it != vi.crend(); ++it)
{
std::cout << *it << ", ";
}
std::cout << std::endl;
// 隐式（间接使用到迭代器，本质是语法糖）
for (auto& v : vi) // 引用，可读可写
{
v += 6;
}
for (auto v : vi) // 复制，可读可写
{
v = 0;
}
for (auto const& v : vi) // 引用，只读
{
std::cout << v << ", ";
}
std::cout << std::endl;
}
5. 添加元素
分为在现有元素的后面（常称为“尾部”）追加新元素，和在现有元素之间（包括头部）插入新元素。前者效率较高（因为有机会用上预备内存）。
在 C++11 之后，具体接入方法，又分为普通插入和“就地插入”（也称“置入”）。二者的区别，仅对复合结构（class、sturct等）类型的元素有意义。
- 普通插入：先构造出一个元素对象，然后复制一份给 vector 容器；
- 就地插入：将构造元素对象的参数，传给 vector 容器，借助这些参数，容器在预备的空闲内存上构造出元素对象。
由此可见：对于简单类型元素（比如： int、float 等），就地插入没有意义；另外，如果已无预留空间，通常也无法实现就地插入。
对应到 vector 最常用的四个方法：
- push_back(新元素)
- emplace_back( 构造新元素的参数… )
- insert(新元素)
- emplace(构造新元素的参数…)
- 测试代码：
// 有显式默认构造函数的结构体
struct Point
{
int x, y;
Point() noexcept : x(0), y(0) {} //包括 Point() = default;
Point(int x, int y) noexcept : x(x), y(y) { }
Point(Point const& o) // 定制拷贝构造，显示信息
: x(o.x), y(o.y)
{
std::cout << __PRETTY_FUNCTION__ << "\n";
}
};
// 测试添加元素
void testAppendElement()
{
std::vector<Point> pv;
Point pt(90, 100);
pv.push_back(pt);
/* 强迫产生预留空间
pv.push_back(pt);
pv.push_back(pt);
pv.push_back(pt);
pv.push_back(pt);
//*/
std::cout << "----------------------\n";
pv.emplace_back(90, -9);
std::cout << "----------------------\n";
auto pos = pv.cbegin();
++pos;
pos = pv.insert(pos, Point(-999, -999));
std::cout << pv[1].x << ", " << pv[1].y << std::endl;
pv.emplace(pos, -888, -888);
std::cout << pv[1].x << ", " << pv[1].y << std::endl;
}
6. 删除元素
pop_back() 和 push_back() 对应，用于将 vector 容器中最后一个元素剔除，它的性能成本很像：① 最后一个元素的析构，② 容器的 size 减一。显然，无需归还最后一个元素原来所占用的内存，将它视为预留内存即可。
如果待删除的是前面的元素，代价又来了：设有五个元素，删除第二个，则后面的第三、第四、第五个元素，都必须向前移动一个身位。
想要删除前面的元素，相比 pop_back()，还有一个啰嗦的点：必须提供待删除位置上的迭代器。对应方法为：
iterator erase(const_iterator pos);
iterator erase(const_iterator first, iterator last);
双参数版 [first ，last) 指定一段半开区间，用于删除从 first（含） 到 last（不含）之间的所有元素。
同时请注意，二者都返回一个新的迭代器，它指向被删除元素原有位置（该位置总是有效，除非容器已空）。当你需要在一个循环中删除个别位置上的元素时，即可通过 erase() 返回的迭代器，以确保既不漏删，也不误删除。
具体可见测试代码中的示例：删除一个存放整数的 vector中，所有带 4 的元素。
- 测试代码：
// 测试删除元素
void testRemoveElement()
{
std::vector<int> vi {-404,2,4,5,14,40,88,44,16,1314};
vi.pop_back(); // 告别 1314
for (auto it = vi.cbegin(); it != vi.cend(); /* 这里空着！！ */)
{
if (isContainsFour(*it))
{
std::cout << ">" << *it << "< ";
it = vi.erase(it); // 不是 *it
}
else
{
++it;
}
}
}
7. 调整容量
- resize(newSize) ：调整元素个数，变多就默认创建，变少就从尾部删除；
- resize(newSize, 样板元素)：当元素本身无法默认构造时，可以使用本版本；
- reserve(newCap) ：仅用于调整预留空间，如指定新预留空间低于现有元素个数，不会任何实际操作；
- shrink_to_fit() ：让 capacity 缩小到和现有元素个数一致。
- 测试代码：
// 有显式默认构造函数的结构体
struct Point
{
int x, y;
Point() // 构造时输出信息
: x(0), y(0)
{ std::cout << __PRETTY_FUNCTION__ << "\n"; }
Point(int x, int y) noexcept : x(x), y(y) { }
Point(Point const& o) // 拷贝时输出信息
: x(o.x), y(o.y)
{
std::cout << __PRETTY_FUNCTION__ << "\n";
}
};
// 测试调整空间大小
void testAdjustSizeOrCapacity()
{
{
std::vector<Point> vp(1);
std::cout << "-------------\n";
vp.resize(2); // 大搬家！！
std::cout << "-------------\n";
vp.resize(1);
std::cout << "-------------\n";
}
std::cout << "==================\n";
{
std::vector<Point> vp;
vp.reserve(10);
vp.resize(1);
std::cout << "-------------\n";
vp.resize(2);
std::cout << "-------------\n";
vp.resize(1);
std::cout << "-------------\n";
std::cout << "capacity : " << vp.capacity() << "\n";
vp.shrink_to_fit();
std::cout << "capacity : " << vp.capacity() << "\n";
}
}