网站的设计分析,南京网络营销课程培训,沈阳做网站直播的公司,在地区做网站怎么赚钱文章目录 基本原理1. 数据存储结构2. 内存管理机制3. 迭代器实现原理4. 元素访问原理5. 插入和删除元素原理 常见用法1. 概述2. 包含头文件3. 定义和初始化4. 常用成员函数5. 迭代器6. 内存管理与性能特点7. 应用场景 基本原理
以下是关于 std::vector 的基本原理讲解#xf… 文章目录 基本原理1. 数据存储结构2. 内存管理机制3. 迭代器实现原理4. 元素访问原理5. 插入和删除元素原理 常见用法1. 概述2. 包含头文件3. 定义和初始化4. 常用成员函数5. 迭代器6. 内存管理与性能特点7. 应用场景 基本原理
以下是关于 std::vector 的基本原理讲解
1. 数据存储结构
std::vector 在内部通常是使用一段连续的内存空间来存储元素这一点和普通的C风格数组类似。这种连续存储的方式使得它能够实现快速的随机访问因为可以通过简单的指针运算基于元素类型的大小来定位到任意位置的元素例如对于一个存储 int 类型元素的 vector如果知道首地址要访问索引为 n 的元素在内存中就是首地址加上 n * sizeof(int) 的偏移量。
2. 内存管理机制 初始内存分配 当创建一个 vector 时它并不会立即分配很大的内存空间通常会分配一个较小的初始容量不同的标准库实现可能初始容量不同有些可能是0有些可能是一个较小的固定值比如4或者8等。例如定义 std::vectorint myVec; 时它可能刚开始并没有分配实际可存储元素的内存块只是进行了一些必要的内部状态初始化。 扩容机制 随着不断向 vector 中添加元素通过 push_back 等操作当元素个数达到当前容量上限时vector 就需要进行扩容操作以容纳更多元素。扩容过程一般涉及以下几个步骤 新内存分配它会按照一定的策略分配一块更大的连续内存空间常见的扩容倍数是1.5倍或者2倍左右具体倍数由不同的STL实现决定。例如当前 vector 的容量是4已经存储了4个元素当再调用 push_back 添加第5个元素时如果按照2倍扩容策略就会另外开辟一块能容纳8个元素的新内存空间。元素复制或移动接着把原来内存空间中存储的所有元素复制或者移动如果元素类型支持移动语义在C11及以后通常优先采用移动以提高效率到新分配的内存空间中。这一步涉及对每个元素的操作如果元素类型的拷贝构造函数或者移动构造函数开销较大那么扩容操作的整体开销也会相应增大。释放旧内存在成功将元素迁移到新内存空间后会释放原来的那块内存空间以避免内存泄漏。 缩容机制可选 有些 vector 的实现提供了手动缩容或者在特定条件下自动缩容的机制不过不是所有标准库都保证有自动缩容功能。比如当调用 vector 的 clear 函数清空所有元素后部分实现可能会自动释放多余的内存空间将容量减小也可以通过类似 shrink_to_fit 这样的函数如果标准库支持来显式要求 vector 释放多余内存使其容量尽量接近当前元素个数不过这个函数只是一个建议性的操作具体是否能真正缩容以及缩容到何种程度还是依赖具体的实现。
3. 迭代器实现原理
vector 的迭代器本质上是一种类似指针的对象它重载了一些必要的运算符如 *解引用、前置和后置自增、--前置和后置自减、!不等比较等使其能够像指针一样遍历 vector 中的元素。 普通迭代器begin、end 等返回的迭代器 其内部通常就是直接持有指向 vector 中元素所在内存位置的指针。例如begin 函数返回的迭代器指向 vector 的第一个元素所在内存地址end 函数返回的迭代器指向最后一个元素后面的内存位置形成左闭右开区间用于遍历等操作符合STL的通用约定。当对迭代器进行自增操作时就是按照元素类型的大小在内存中向后移动指针到下一个元素的位置自减操作则相反向前移动指针。 反向迭代器rbegin、rend 等返回的迭代器 反向迭代器的实现相对复杂一些它一般会对普通迭代器进行适配内部通过一些机制来实现从后往前遍历的效果。实际上它可以看作是对普通迭代器的一种“包装”在自增、自减等操作的语义上进行了反转使其能够从 vector 的末尾元素开始向开头方向依次访问元素。
4. 元素访问原理 下标访问operator[] 这个操作符重载的实现就是基于 vector 内部元素连续存储的特性通过简单的指针算术运算来实现快速访问。它接收一个索引值作为参数在内部会将这个索引值与元素类型的大小相乘例如对于 int 类型就是乘以 sizeof(int)然后加上首元素的地址也就是 vector 内部管理的那块连续内存空间的起始地址最后返回这个计算得到的内存地址对应的元素的引用不过它不会进行边界检查所以如果使用不当访问越界就会导致未定义行为。 at 函数访问 at 函数和 operator[] 类似也是用于访问元素但它内部会首先进行边界检查判断传入的索引值是否在合法的范围即大于等于0且小于 vector 的大小内如果越界则会抛出 std::out_of_range 类型的异常避免了因越界访问带来的潜在错误隐患相对更加安全。
5. 插入和删除元素原理 末尾插入push_back 在末尾添加元素时如果当前 vector 还有剩余空间即元素个数小于容量那么直接在已有内存空间的末尾位置构造新元素即可这个过程相对简单高效但如果已经满容量需要扩容就会触发上述的扩容流程后再添加元素。 中间或开头插入insert 当要在 vector 的中间或者开头位置插入元素时需要先将插入位置及之后的所有元素依次向后移动为新插入的元素腾出空间然后再在腾出的位置构造新元素。元素移动的过程同样涉及到对每个元素的拷贝或移动操作所以在元素个数较多的 vector 中进行这类插入操作相对来说效率较低时间复杂度是线性的 O(n)其中 n 是 vector 的元素个数。 删除元素pop_back、erase 等 pop_back 操作相对简单只是销毁 vector 末尾的元素调用其析构函数如果有的话然后将元素个数减1即可而 erase 操作在删除指定位置的元素时需要将该位置后面的所有元素依次向前移动来填补删除元素后留下的空位同样涉及到多个元素的拷贝或移动效率方面也会受 vector 元素个数影响在中间或开头位置删除元素时间复杂度为 O(n)。
总之std::vector 通过巧妙的内存管理、迭代器设计以及对各种操作的底层实现为开发者提供了一个方便、灵活且功能强大的动态数组容器在了解其基本原理后能更好地掌握它的使用场景、性能特点以及避免一些因不当使用而可能出现的问题。 以下是对C STL标准模板库中vector的详细讲解
常见用法
1. 概述
vector是C STL中非常常用的一个容器类它提供了动态大小的数组功能能够自动管理所存储元素的内存分配与释放并且支持快速的随机访问。简单来说你可以把它看作是一种可以根据需要自动扩容和缩容的数组使用起来比普通的C风格数组更加方便、安全和灵活广泛应用于各种需要存储和操作一组同类型元素的场景中。
2. 包含头文件
要使用vector容器需要在代码中包含vector头文件例如
#include vector3. 定义和初始化
基本定义 定义一个vector对象的语法形式通常为 std::vector元素类型 变量名;这里的“元素类型”可以是C中的各种基本数据类型如int、double、char等也可以是自定义的结构体、类等类型。例如定义一个存储整数的vector
std::vectorint myVector;初始化方式 默认初始化像上面那样定义后vector会被默认初始化为空即其中不包含任何元素其大小通过size()成员函数获取为0。指定初始大小和初始值可以在定义时指定vector的初始大小以及每个元素的初始值语法为 std::vector元素类型 变量名(元素个数, 初始值);。例如创建一个包含5个初始值都为0的整数的vector
std::vectorint anotherVector(5, 0);此时anotherVector的大小为5并且每个元素的值都是0。 - 使用初始化列表初始化利用花括号{}包裹元素来初始化vector这种方式在C11及以后的版本中更加常用和方便。例如
std::vectorint initListVector {1, 2, 3};这个vector包含了3个元素分别是1、2和3。 - 从其他vector复制或移动初始化可以通过已有的vector对象来初始化一个新的vector实现复制或移动语义如果适用。例如
std::vectorint sourceVector {1, 2, 3};
// 复制初始化
std::vectorint copiedVector(sourceVector);
// 移动初始化假设C11及以上利用std::move函数实现移动语义
std::vectorint movedVector(std::move(sourceVector));复制初始化会创建一个新的vector其元素与源vector完全相同而移动初始化则是将源vector的资源如内存空间等转移给新的vector源vector在移动后通常处于一种有效但已转移资源的特殊状态比如大小变为0等。
4. 常用成员函数
添加和删除元素相关函数 push_back()用于在vector的末尾添加一个元素。例如
std::vectorint numbers;
numbers.push_back(5); // 在末尾添加整数5
numbers.push_back(10); // 再添加整数10此时numbers包含两个元素分别是5和10- **pop_back()**与push_back()相反它用于删除vector末尾的一个元素。例如std::vectorint nums {1, 2, 3};
nums.pop_back(); // 删除末尾的元素3此时nums包含元素1和2- **insert()**可以在指定位置插入一个或多个元素。它有多种重载形式常见的一种是 iterator insert(iterator position, const T value);其中position是指向插入位置的迭代器可以通过begin()、end()等函数获取迭代器来指定位置value是要插入的元素值。例如std::vectorint vec {1, 3};
auto it vec.begin() 1; // 指向索引为1的位置也就是元素3所在位置
vec.insert(it, 2); // 在索引为1的位置插入元素2此时vec变为{1, 2, 3}还可以一次插入多个相同元素比如 iterator insert(iterator position, size_type n, const T value); 形式可以在指定位置插入n个相同的value元素。 - erase()用于删除指定位置的一个或多个元素同样有多种重载形式。例如删除单个元素可以这样用iterator erase(iterator position);删除一段元素区间可以用 iterator erase(iterator first, iterator last);其中first和last分别是要删除区间的起始和结束迭代器左闭右开区间。例如
std::vectorint v {1, 2, 3, 4};
auto it v.begin() 1; // 指向元素2
v.erase(it); // 删除元素2此时v变为{1, 3, 4}删除一段元素示例
std::vectorint ve {1, 2, 3, 4, 5};
auto start ve.begin() 1; // 指向元素2
auto end ve.begin() 3; // 指向元素4后面的位置左闭右开区间概念
ve.erase(start, end); // 删除元素2和3此时ve变为{1, 4, 5}访问元素相关函数 at()用于安全地访问vector中的元素它会进行边界检查如果访问越界会抛出 std::out_of_range 异常。语法为 reference at(size_type n);其中n是要访问元素的索引从0开始计数。例如
std::vectorint values {10, 20, 30};
try {int element values.at(1); // 获取索引为1的元素即20std::cout element std::endl;
} catch (const std::out_of_range e) {std::cerr 访问越界: e.what() std::endl;
}- **operator[]下标运算符**也用于访问元素它与数组的下标访问方式类似但不会进行边界检查如果访问越界会导致未定义行为所以使用时要确保索引在合法范围内。例如std::vectorint data {5, 10};
int element data[0]; // 获取第一个元素5注意这里没有边界检查需谨慎使用- **front()**返回vector的第一个元素的引用可以用于获取或修改第一个元素的值。例如std::vectorint firstVector {1, 2};
int firstElement firstVector.front(); // 获取第一个元素1
firstVector.front() 10; // 将第一个元素修改为10此时firstVector变为{10, 2}- **back()**与front()相对返回vector的最后一个元素的引用同样可用于获取或修改最后一个元素的值。例如std::vectorint lastVector {3, 4};
int lastElement lastVector.back(); // 获取最后一个元素4
lastVector.back() 40; // 将最后一个元素修改为40此时lastVector变为{3, 40}获取容器信息相关函数 size()返回vector中当前元素的个数返回值类型是 std::vector元素类型::size_type通常是无符号整数类型。例如
std::vectorint sizeVector {1, 2, 3};
std::vectorint::size_type elementCount sizeVector.size(); // 获取元素个数这里elementCount的值为3- **capacity()**返回vector当前已经分配的内存空间能够容纳的元素个数也就是它的容量。一般来说随着不断向vector中添加元素当元素个数接近容量时vector会自动进行扩容操作来分配更多的内存空间。例如std::vectorint capVector;
std::cout 初始容量: capVector.capacity() std::endl; // 初始容量可能为0或者一个较小的值取决于实现
capVector.push_back(1);
capVector.push_back(2);
std::cout 添加元素后的容量: capVector.capacity() std::endl; // 容量可能已经自动扩容了- **empty()**判断vector是否为空如果为空即元素个数为0则返回true否则返回false。例如std::vectorint emptyVector;
if (emptyVector.empty()) {std::cout 该vector为空 std::endl;
}
std::vectorint nonEmptyVector {1};
if (!nonEmptyVector.empty()) {std::cout 该vector不为空 std::endl;
}其他常用函数 clear()用于清空vector中的所有元素将其大小变为0但不会释放已分配的内存空间容量可能不会改变除非后续有添加或删除元素等操作触发了内存重新分配。例如
std::vectorint clearVector {1, 2, 3};
clearVector.clear();
if (clearVector.empty()) {std::cout 已清空vector现在为空 std::endl;
}- **resize()**可以改变vector的大小如果新大小大于当前大小会根据元素类型的默认构造函数对于内置类型可能会进行未定义初始化对于类类型会调用默认构造函数或者指定的初始值来填充新增的元素如果新大小小于当前大小则会删除多余的元素。例如std::vectorint resizeVector(3, 1); // 初始化为{1, 1, 1}
resizeVector.resize(5, 0); // 扩大为{1, 1, 1, 0, 0}新增元素初始化为0
resizeVector.resize(2); // 缩小为{1, 1}删除后面的元素5. 迭代器
vector支持迭代器来遍历容器中的元素迭代器就像是指向容器中元素的指针可以通过它来依次访问每个元素。常用的迭代器相关操作有
begin()和end()begin()返回指向vector第一个元素的迭代器end()返回指向vector最后一个元素后面位置的迭代器形成一个左闭右开的区间概念用于循环遍历等操作符合STL的通用设计模式。例如使用迭代器遍历vector的常见方式如下
std::vectorint iterVector {1, 2, 3};
for (auto it iterVector.begin(); it! iterVector.end(); it) {std::cout *it ; // 输出每个元素*it用于解引用迭代器获取元素值
}
// 输出: 1 2 3rbegin()和rend()这两个函数分别返回反向迭代器用于从后往前遍历vectorrbegin()指向最后一个元素rend()指向第一个元素前面的位置同样是左闭右开区间概念。例如
std::vectorint reverseIterVector {4, 5, 6};
for (auto rit reverseIterVector.rbegin(); rit! reverseIterVector.rend(); rit) {std::cout *rit ; // 从后往前输出元素这里输出: 6 5 4
}6. 内存管理与性能特点
内存自动管理vector会自动处理内存的分配和释放当添加元素导致当前分配的内存空间不足时它会自动进行扩容操作通常是按照一定的倍数不同的STL实现可能有不同的扩容策略常见的是1.5倍或2倍等分配新的更大的内存空间然后将原有元素复制或移动到新空间中并释放原来的内存。这种自动管理机制方便了开发者但也可能在频繁扩容时带来一定的性能开销尤其是元素类型的拷贝或移动成本较高时。随机访问性能好由于vector内部元素在内存中是连续存储的类似于普通的数组所以它支持快速的随机访问通过下标运算符或者迭代器解引用访问元素的时间复杂度为常数时间 O(1)。插入和删除元素的性能特点在vector末尾添加或删除元素通过push_back()、pop_back()的操作通常比较高效时间复杂度接近常数时间平均情况不考虑偶尔的扩容操作带来的影响但在中间或者开头位置插入或删除元素通过insert()、erase()可能相对较慢因为需要移动插入或删除位置后面的所有元素时间复杂度为线性时间 O(n)其中n是vector中元素的个数。
7. 应用场景
存储一组同类型的数据比如存储游戏中的玩家分数列表、学生的成绩数组等方便进行数据的添加、删除、修改以及遍历统计等操作。作为函数参数传递数组在函数间传递数组时如果数组大小不确定或者可能会变化使用vector作为参数传递要比传递普通C风格数组更加方便、安全避免了传递数组长度等额外参数以及数组越界等风险。例如
void processVector(const std::vectorint vec) {// 在这里可以安全地遍历vec等操作不用担心越界问题for (int element : vec) {std::cout element ;}
}
int main() {std::vectorint data {1, 2, 3};processVector(data);return 0;
}配合其他STL算法使用vector可以很好地与STL中的各种算法如排序算法std::sort、查找算法std::find等配合使用实现更复杂的数据处理功能。例如
#include algorithm
std::vectorint numbers {5, 3, 1, 4, 2};
std::sort(numbers.begin(), numbers.end()); // 对vector中的元素进行排序总之vector是C STL中一个功能强大、使用方便的容器掌握它的各种特性和使用方法对于高效地进行C编程非常有帮助能够满足很多常见的动态数组相关的编程需求。
