免费网站制作软件平台,南京网站搜索优化,做小程序的公司有哪些比较好?,wordpress文章图片全屏浏览面试题 1 #xff1a;std::vector 的底层存储机制是什么#xff1f;
std::vector 的底层存储机制是一个动态数组#xff0c;它内部通过一片连续的内存空间来存储元素。当这个连续的内存空间不足以容纳新元素时#xff0c;std::vector 会自动申请一块更大的内存空间#x…面试题 1 std::vector 的底层存储机制是什么
std::vector 的底层存储机制是一个动态数组它内部通过一片连续的内存空间来存储元素。当这个连续的内存空间不足以容纳新元素时std::vector 会自动申请一块更大的内存空间通常是当前容量的 1.5 倍或 2 倍然后将原有数据拷贝到新的内存空间并释放原来的内存空间。这个过程称为 reallocation。
std::vector 内部有三个基本的指针分别是 start、finish 和 end_of_storage。start 指向容器的首元素finish 指向尾元素的下一个位置而 end_of_storage 指向容器的最大位置。这三个指针帮助 vector 实现了许多功能如已存储元素大小、剩余空间大小、总容器空间大小等等。
需要注意的是std::vector 的扩容机制时间成本较高因此在实际使用中如果能提前确定容器空间的大小最好提前设定好容器空间的大小以避免频繁的扩容操作。同时由于扩容可能会导致原有指针、迭代器失效因此在扩容后需要特别注意指针和迭代器的有效性。
此外std::vector 还支持随机访问因此访问某一个元素的时间复杂度是 O(1)。但是由于其内部是连续的内存空间所以在插入到非尾结点位置或删除元素时需要移动的元素数量较多时间复杂度为 O(n)。这也是 std::vector和std::list 等其他容器在性能上的一个主要区别。
面试题 2 std::vector 的自增长机制是如何实现的
std::vector 的自增长机制是通过动态调整其内部存储空间的容量来实现的。当 std::vector 需要插入新元素而当前的存储空间不足以容纳时它就会触发自增长机制。
自增长机制的实现过程大致如下
1检查容量 当需要插入新元素时std::vector 会首先检查当前的容量capacity是否足够。容量是指 vector 在内存中预留的空间大小它至少应该等于 vector 的大小size也就是当前存储的元素数量。
2重新分配内存 如果容量不足std::vector 会重新分配内存空间。通常情况下它会分配一个更大的内存块通常是当前容量的1.5倍或2倍具体倍数可能因实现而异。这样做是为了减少未来插入元素时再次触发重新分配的次数。
3数据迁移 然后std::vector会将原有数据即所有已存储的元素从旧的内存空间复制到新的内存空间。这是一个相对耗时的操作因为它涉及到内存拷贝。
4释放旧内存 在数据迁移完成后std::vector会释放原来的内存空间这样旧的内存就可以被操作系统或其他数据结构重新利用了。
5更新指针 最后std::vector 会更新其内部的指针使 start 和 finish 指针指向新的内存空间中的正确位置end_of_storage 指针则指向新的内存空间的末尾。
需要注意的是std::vector 的自增长机制可能会导致一些性能问题。因为每次重新分配内存和数据迁移都是一个相对耗时的操作特别是在插入大量元素时。因此在实际应用中如果可能的话最好预先知道或估计 vector 可能需要存储的元素数量并使用 reserve() 函数提前为其分配足够的空间以减少重新分配的次数。
面试题 3 std::vector 和 std::array 有什么区别
std::vector和std::array在C中都是容器用于存储一系列相同类型的对象但它们之间存在一些关键的区别
1动态与静态
std::vector 是一个动态数组它可以根据需要动态地增加或减少大小。这意味着你可以在任何时候向 vector 中添加或删除元素而不需要预先知道它将要存储多少元素。std::array 则是一个固定大小的数组它在编译时创建并且大小是固定的。一旦定义了一个 array就不能改变它的大小。 内存分配std::vector 使用动态内存分配这意味着它会在运行时根据需要分配或释放内存。这种动态分配使得 vector 能够灵活地处理不同大小的数据集。std::array 使用静态内存分配即在编译时分配固定大小的内存。这意味着 array 的大小在编译时就已经确定并且存储在栈内存中。
2访问方式
std::vector 和 std::array 都支持随机访问可以通过下标运算符[]快速访问元素。然而由于 vector 的内存动态分配其访问速度可能会比 array 慢一些尤其是在涉及大量数据的情况下。另一方面array 由于其内存是连续和静态的访问速度通常更快。
3初始化和使用
std::vector 可以使用默认构造函数创建一个空的 vector然后使用 push_back() 等方法来添加元素。它也可以在创建时指定初始大小。std::array 在定义时必须指定其大小并且可以使用初始化列表、默认构造函数或复制构造函数来初始化。一旦定义就不能改变 array 的大小。
4适用场景
std::vector 适用于需要动态调整大小的情况例如当你不知道将要存储多少数据或者数据的大小可能会在程序执行期间改变时。std::array 适用于大小已知且不会改变的情况例如当你有一个固定大小的数据集并且希望获得更好的性能时。
5异常安全性
std::vector 在重新分配内存时可能会抛出异常特别是当内存不足时。std::array 由于其大小是固定的所以在使用期间不会抛出异常除了可能的构造函数异常。
总的来说std::vector 和 std::array 都有各自的优点和适用场景选择使用哪一个取决于你的具体需求比如是否需要动态调整大小、对性能的要求、以及是否已知数组的大小等。
面试题 4 std::vector的迭代器失效问题是什么举一个迭代器失效例子。
在 std::vector 容器中迭代器失效主要发生在以下情况 当 std::vector 容器进行扩容时即当现有容量不足以容纳新元素时std::vector 会重新分配内存空间并将原有元素复制到新的内存空间中。这个过程可能会导致原有迭代器、引用和指针失效。 当 std::vector 容器的元素被删除时指向被删除元素的迭代器也会失效。
下面是一个迭代器失效的例子
#include iostream
#include vector int main()
{std::vectorint vec { 1, 2, 3, 4, 5 };// 获取指向vector第一个元素的迭代器 std::vectorint::iterator it vec.begin();// 在迭代器指向的元素之前插入一个新元素 vec.insert(it, 0);// 此时it指向的元素已经被新插入的元素覆盖it已经失效 // 如果继续使用it可能会导致未定义的行为如程序崩溃或数据错误 // 尝试打印it指向的元素这将导致迭代器失效的错误 std::cout The element at iterator position is: *it std::endl;return 0;
}在上面代码中首先创建了一个包含 5 个元素的 std::vector。然后获取了一个指向 vector 第一个元素的迭代器it。接下来在 it 指向的元素之前插入了一个新的元素。由于这个插入操作导致 vector 扩容如果原容量不足以容纳新元素vector 重新分配了内存并将原有元素复制到新内存空间。这时原有的迭代器 it 已经失效因为它指向的内存位置现在包含了一个新插入的元素。
如果尝试使用失效的迭代器 it 来访问元素比如通过 *it 来解引用它将会导致未定义的行为。在实际应用中这可能会导致程序崩溃或者更难以追踪的数据错误。
因此在编程时必须格外注意避免在迭代器失效后继续使用它。当对 std::vector 容器进行修改操作如插入、删除、扩容等时任何指向容器中元素的迭代器、引用和指针都可能失效。在这种情况下应该重新获取迭代器或者确保在修改操作之前或之后不使用这些迭代器。
面试题 5 std::vector 和 std::list 有什么区别
std::vector 和 std::list 是 C 标准模板库 (STL) 中的两种非常重要的序列式容器它们有着显著的区别。以下是它们之间的主要区别
1底层实现与内存管理
std::vector底层使用动态数组实现元素存储在连续的内存空间中。这意味着 vector 的元素访问速度很快因为可以通过下标直接访问。然而当 vector 需要增加大小时它可能需要重新分配更大的内存块并移动所有元素这可能会导致较高的时间复杂度。std::list底层使用双向链表实现每个元素可以分布在内存中的任意位置。这意味着 list 的随机访问速度较慢因为它需要从头或尾开始遍历链表但插入和删除元素的速度很快因为只需要调整节点的指针。
2随机访问性能 std::vector支持随机访问即可以通过下标直接访问任何位置的元素时间复杂度为 O(1)。 std::list不支持随机访问访问元素需要从头或尾开始遍历时间复杂度为 O(n)。
3插入与删除操作 std::vector在任意位置插入或删除元素时可能需要移动后续的所有元素来填补空缺时间复杂度为 O(n)。 std::list插入或删除元素只需要改变节点指针时间复杂度为 O(1)。
4空间利用率与缓存效率 std::vector由于其元素是连续存储的不容易造成内存碎片空间利用率和缓存效率较高。 std::list由于其使用链表结构每个节点可能不是连续存储的容易造成内存碎片导致空间利用率和缓存效率较低。
5迭代器 std::vector迭代器是原生态的指针。 std::list迭代器是对原生态指针进行了封装。
6迭代器失效问题 std::vector在插入元素时如果导致扩容原有迭代器可能会失效。删除元素时被删除元素及其之后的迭代器也会失效。 std::list插入元素不会导致迭代器失效而删除元素只会导致当前迭代器失效其他迭代器不受影响。
7使用场景 std::vector适用于需要高效存储和随机访问的场景不关心插入效率。 std::list适用于大量插入和删除操作的场景不关心随机访问。
总结std::vector 和 std::list 的选择取决于具体需求。如果需要高效的随机访问和连续的内存存储std::vector 是更好的选择。如果需要频繁地插入和删除元素而不太关心随机访问那么 std::list 可能更适合。
面试题 6 如何在 std::vector 中插入和删除元素
在C的std::vector中插入和删除元素有多种方法下面是一些常用的方法
插入元素
1使用 insert 成员函数
insert 函数可以在指定位置插入一个或多个元素。
#include vector
#include iostreamint main()
{std::vectorint vec {1, 2, 4, 5};// 在位置2插入元素3vec.insert(vec.begin() 2, 3);// 输出vector的内容for (int num : vec) {std::cout num ;}std::cout std::endl;return 0;
}上面代码的输出为
1 2 3 4 5insert 也可以接受一个迭代器范围来插入多个元素。
std::vectorint to_insert {3, 3, 3};
vec.insert(vec.begin() 2, to_insert.begin(), to_insert.end());2使用 push_back 成员函数
push_back 在vector的末尾添加一个新元素。
vec.push_back(1);3使用 emplace 或 emplace_back 成员函数
emplace 和 emplace_back 可以在指定位置就地构造一个新元素这通常比先构造元素再插入更高效。
vec.emplace(vec.begin() 2, 3); // 在位置2就地构造并插入元素3
vec.emplace_back(7); // 在vector末尾就地构造并插入元素7删除元素
1使用 erase 成员函数
erase 可以删除一个或多个元素。
// 删除位置2的元素
vec.erase(vec.begin() 2);// 删除从位置1到位置3的元素不包括位置3
vec.erase(vec.begin() 1, vec.begin() 3);2使用 pop_back 成员函数 pop_back 删除vector的最后一个元素。
if (!vec.empty()) {vec.pop_back();
}3使用 clear 成员函数 clear 删除vector中的所有元素。
vec.clear(); // vector现在为空注意当使用 insert 或 erase 时指向被修改部分的迭代器、引用和指针可能会失效。因此在插入或删除元素后应该避免使用这些失效的迭代器、引用和指针。
此外频繁地在 std::vector 中间位置插入或删除元素可能会导致性能下降因为可能需要移动大量的元素来保持连续性。如果这种操作很频繁考虑使用 std::list 或 std::deque 等容器可能会更有效。
