长沙做网站开发多少钱,vi设计什么意思,互联网创业项目app,如何做h5简历制作网站文章目录 1. vector 的概述1.1 vector 是什么#xff1f;1.2 vector 的优点1.3 vector 的缺点 2. vector 的基本使用2.1 vector 的定义2.2 基本操作2.3 示例2.4 迭代器的使用 3. vector 的内部实现原理3.1 动态数组的实现3.2 内存管理3.3 内存扩展策略3.4 元素的插入与删除3.4… 文章目录 1. vector 的概述1.1 vector 是什么1.2 vector 的优点1.3 vector 的缺点 2. vector 的基本使用2.1 vector 的定义2.2 基本操作2.3 示例2.4 迭代器的使用 3. vector 的内部实现原理3.1 动态数组的实现3.2 内存管理3.3 内存扩展策略3.4 元素的插入与删除3.4.1 尾部插入与删除3.4.2 中间或头部插入与删除 4. vector 高级功能4.1 复制与赋值4.2 移动语义与 std::move4.3 vector 的初始化列表C114.4 emplace_back() 与 push_back() 的区别4.5 shrink_to_fit() 减少容量浪费 5. vector 的常见应用场景5.1 动态数组5.2 堆栈5.3 动态队列5.4 2D 矩阵的实现 6. vector 的复杂度分析6.1 时间复杂度6.2 空间复杂度 7. vector 的常见问题和陷阱7.1 容量浪费问题7.2 迭代器失效(最需要注意的地方)7.3 元素的析构 前言 C Standard Template Library (STL) 是一个强大且灵活的库提供了许多有用的数据结构和算法其中vector 是最常用的容器之一。 vector是动态数组的封装可以在运行时自动调整大小提供了数组的效率以及更多的功能和灵活性。 在本文中我们将深入讨论 vector的特性、使用方法、底层实现及其复杂性分析。 1. vector 的概述
vector文档的链接http://www.cplusplus.com/reference/vector/vector/
1.1 vector 是什么
vector 是 C STL 中一种顺序容器sequence container其底层实现基于动态数组。与普通数组不同的是vector 可以根据需要动态扩展其大小即它能够存储任意数量的元素而不需要在创建时指定一个固定的大小。此外vector 提供了丰富的成员函数可以方便地对元素进行插入、删除、遍历、查找等操作。
1.2 vector 的优点
动态扩展vector 能够自动调整大小避免了固定大小数组带来的内存不足问题。 高效的随机访问由于 vector 底层是连续的内存块因此它可以像数组一样通过索引进行快速的随机访问。 灵活的插入和删除vector 支持高效的尾部插入和删除操作且提供了多种插入、删除方式。 STL 兼容性vector 是 STL 容器支持 STL 的算法和迭代器可以与其他 STL 容器和算法无缝结合。
1.3 vector 的缺点 头部和中间的插入、删除效率低由于 vector 使用连续的内存块因此在中间或头部插入或删除元素时需要移动大量元素时间复杂度为 O(n)。 内存浪费为了提高扩展效率vector 通常会预留比实际需要更多的内存这可能导致内存浪费。
2. vector 的基本使用
在使用 vector 时我们需要包含头文件 。下面是一些 vector 的基本使用方法和常见操作
2.1 vector 的定义
#include vectorstd::vectorint vec; // 定义一个存储整数的空vector
std::vectorint vec(10); // 定义一个包含10个元素的vector元素值默认初始化为0
std::vectorint vec(10, 5); // 定义一个包含10个元素的vector元素值为5
std::vectorint vec2 vec; // 定义一个新vector并通过拷贝构造函数初始化2.2 基本操作
push_back()在 vector 的末尾插入元素。 pop_back()删除 vector 末尾的元素。 size()返回 vector 中元素的数量。 capacity()返回 vector 当前的容量即它在不重新分配内存的情况下最多可以容纳的元素数。 clear()清空 vector 中的所有元素。 empty()判断 vector 是否为空。 resize()调整 vector 的大小。 reserve()为 vector 预留一定的容量避免频繁的重新分配内存。
2.3 示例
#include iostream
#include vectorint main() {std::vectorint vec;// 向vector中添加元素vec.push_back(1);vec.push_back(2);vec.push_back(3);// 输出vector的元素for (int i 0; i vec.size(); i) {std::cout vec[i] ;}std::cout std::endl;// 删除最后一个元素vec.pop_back();// 检查是否为空if (!vec.empty()) {std::cout The vector is not empty! std::endl;}return 0;
}2.4 迭代器的使用
迭代器是一种用于遍历 vector 元素的工具。vector 提供了多种迭代器包括 begin() 和 end()。
std::vectorint vec {1, 2, 3, 4, 5};// 使用迭代器遍历
for (std::vectorint::iterator it vec.begin(); it ! vec.end(); it) {std::cout *it ;
}
std::cout std::endl;也可以使用 C11 的范围 for 循环来遍历
for (int val : vec) {std::cout val ;
}3. vector 的内部实现原理
3.1 动态数组的实现
vector 的底层实现基于动态数组。当需要插入新元素时如果当前容量不足vector 会自动分配更大的内存块并将原来的元素拷贝到新的内存块中。这种动态扩展策略的时间复杂度较低因为 vector 的容量在每次扩展时通常是当前容量的两倍。
std::vectorint vec;
vec.push_back(1); // 第一次插入分配内存
vec.push_back(2); // 插入内存足够不需要重新分配
vec.push_back(3); // 插入内存足够不需要重新分配
// 当容量不足时vector 会重新分配内存通常是原来容量的两倍。3.2 内存管理
vector 通过 capacity 来控制当前分配的内存大小而 size 表示实际存储的元素数量。capacity 总是大于或等于 size。当 size 超过 capacity 时vector 会重新分配内存并将所有现有元素拷贝到新的内存地址。
std::vectorint vec;
vec.reserve(10); // 预先分配10个元素的内存
vec.push_back(1); // 不会触发内存重新分配
vec.push_back(2); // 不会触发内存重新分配通过使用 reserve()可以避免多次内存重新分配从而提高效率。
3.3 内存扩展策略
当 vector 的容量不足时它通常会以指数倍通常是 2 倍的方式扩展。每次扩展都会重新分配一块新的内存并将旧的元素拷贝到新的位置。这种方式虽然在内存重新分配时会有较大的开销但由于扩展的频率较低总体上这种策略是高效的。
3.4 元素的插入与删除
3.4.1 尾部插入与删除
vector 尾部的插入和删除操作是最为高效的时间复杂度为 O(1)因为它们不需要移动其他元素。使用 push_back() 和 pop_back() 可以高效地操作 vector 末尾的元素。
3.4.2 中间或头部插入与删除
在 vector 中间或头部插入和删除元素时需要将插入位置之后的所有元素向后移动这样才能为新元素腾出空间。这使得这些操作的时间复杂度为 O(n)。
vec.insert(vec.begin() 1, 10); // 在第二个位置插入10后面的元素都需要向后移动
vec.erase(vec.begin() 2); // 删除第三个元素后面的元素都需要向前移动4. vector 高级功能
4.1 复制与赋值
当一个 vector 被赋值或复制时会创建一个新对象并将所有元素进行深拷贝。这意味着修改新对象不会影响原来的 vector。
std::vectorint vec1 {1, 2, 3};
std::vectorint vec2 vec1; // 深拷贝
vec2[0] 10;
std::cout vec1[0]; // 输出1vec1不受影响4.2 移动语义与 std::move
C11 引入了移动语义允许将 vector 的资源直接转移到另一个对象而不需要进行深拷贝。这可以极大地提高性能尤其是在处理大型对象时。
std::vectorint vec1 {1, 2, 3};
std::vectorint vec2 std::move(vec1); // 使用std::movevec1的资源转移给vec2在上面的例子中std::move 将 vec1 的所有资源如内存和元素直接转移到 vec2 中而不需要进行深拷贝。这种操作后vec1 将处于“空”状态不再拥有原来的数据size() 将返回0。
4.3 vector 的初始化列表C11
C11 引入了初始化列表可以直接通过大括号初始化 vector
std::vectorint vec {1, 2, 3, 4, 5}; // 初始化列表这种方式非常方便不需要手动调用 push_back() 来插入每个元素。
4.4 emplace_back() 与 push_back() 的区别
emplace_back() 是 C11 新增的功能它允许直接在容器的末尾构造对象而无需先构造对象再拷贝到 vector。相比之下push_back() 会进行额外的拷贝操作因此在某些情况下emplace_back() 会比 push_back() 更高效。
class Person {
public:Person(const std::string name, int age) : name(name), age(age) {}
private:std::string name;int age;
};// 使用push_back
std::vectorPerson people;
people.push_back(Person(John, 30)); // 先构造Person对象然后拷贝到vector中// 使用emplace_back
people.emplace_back(Jane, 25); // 直接在vector内部构造Person对象避免拷贝使用 emplace_back() 时参数直接传递给对象的构造函数从而减少了不必要的拷贝或移动操作。
4.5 shrink_to_fit() 减少容量浪费
由于 vector 通常会预留比实际所需更多的内存空间capacity()可能会造成内存浪费。shrink_to_fit() 函数用于释放未使用的内存使得 vector 的容量等于其大小。
std::vectorint vec {1, 2, 3};
vec.reserve(10); // 预留10个元素的空间
std::cout vec.capacity(); // 输出10vec.shrink_to_fit();
std::cout vec.capacity(); // 输出3容量被调整为实际使用的大小需要注意的是shrink_to_fit() 并不保证一定会减少容量但在支持该操作的系统上可以显著减少内存占用。
5. vector 的常见应用场景
5.1 动态数组
vector 最常见的应用场景就是作为动态数组使用。当程序中需要动态调整数组大小时vector 提供了极大的方便。
std::vectorint vec;
int n;
std::cin n;
for (int i 0; i n; i) {int x;std::cin x;vec.push_back(x); // 动态添加元素
}5.2 堆栈
vector 可以模拟堆栈的功能因为它提供了高效的尾部插入push_back()和删除pop_back()操作。虽然 C STL 中已经有 stack 容器但使用 vector 实现堆栈也是完全可行的。
std::vectorint stack;
stack.push_back(1); // 入栈
stack.push_back(2);
stack.pop_back(); // 出栈5.3 动态队列
虽然 C STL 提供了 queue 容器但 vector 同样可以用来实现队列。通过在 vector 的末尾插入元素并从头部移除元素我们可以模拟队列的行为。
std::vectorint queue;
queue.push_back(1); // 入队
queue.push_back(2);
queue.erase(queue.begin()); // 出队删除第一个元素5.4 2D 矩阵的实现
vector 可以轻松实现二维或多维数组。通过将 vector 嵌套使用可以构建动态调整大小的二维数组或矩阵。
std::vectorstd::vectorint matrix(3, std::vectorint(3)); // 创建3x3的矩阵
matrix[0][0] 1;
matrix[1][1] 2;
matrix[2][2] 3;这个方法可以处理动态大小的矩阵使得二维数组的尺寸不需要在编译时确定。
6. vector 的复杂度分析
6.1 时间复杂度
随机访问由于 vector 是连续的内存块随机访问某个元素的时间复杂度为 O(1)。 尾部插入和删除尾部插入push_back()和尾部删除pop_back()的平均时间复杂度为 O(1)但在某些情况下如扩容时插入操作的复杂度可能会暂时达到 O(n)。 中间或头部插入和删除由于插入或删除会导致大量元素的移动因此这些操作的时间复杂度为 O(n)。
6.2 空间复杂度
vector 使用连续的内存块来存储元素其空间复杂度与存储的元素个数成正比即 O(n)。由于 vector 会在扩展时预留更多的内存因此有时它的实际内存使用量会超过其存储的元素量。
为了减少内存浪费可以使用 shrink_to_fit() 来回收未使用的空间。
7. vector 的常见问题和陷阱
7.1 容量浪费问题
如前所述vector 的容量通常大于其实际存储的元素数量。如果程序中频繁进行插入操作且对内存使用敏感可以使用 shrink_to_fit() 来减少浪费。
7.2 迭代器失效(最需要注意的地方)
在 vector 中进行插入或删除操作时所有指向 vector 元素的迭代器、指针或引用可能会失效。这是因为插入或删除操作可能导致 vector 重新分配内存从而改变所有元素的地址。
std::vectorint vec {1, 2, 3};
auto it vec.begin();
vec.push_back(4); // 可能导致内存重新分配
std::cout *it; // 迭代器可能失效行为未定义解决方法是在插入或删除操作后尽量避免使用之前的迭代器或指针。
7.3 元素的析构
当 vector 中的对象被删除时会调用对象的析构函数。因此如果 vector 存储的是指针类型在删除 vector 或清空元素时需要特别小心确保不会引发内存泄漏。
std::vectorint* vec;
vec.push_back(new int(10));
vec.clear(); // 仅删除了指针但没有释放内存可能导致内存泄漏解决方案是在删除元素之前手动释放内存或者使用智能指针。
