• c++ 高效使用vector(面试)

    文章目录

    我们在 vector 中存入 TestStruct 结构的数据，并使用FillVector()来填充 vector。它们的定义如下。我们会使用 Stopwatch（用于计时）。这个工具由 Kjell 创建，在 https://github.com/KjellKod/Stopwatch 可以找到。

    // Test struct to be inserted/removed from vector
struct BigTestStruct
{
  int iValue = 1;
  float fValue;
  long lValue;
  double dValue;
  char cNameArr[10];
  int iValArr[100];
};
// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
  for (int i = 0; i < 10000; i++)
  {
    BigTestStruct bt;
    testVector.push_back(bt);
  }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    马上开始在 C++ 11 中优化 vector 用法的介绍

    1.善用Reserve提前分配足够的空间

    提前分配足够的空间以避免不必要的重新分配和复制周期

    程序员喜欢使用 vector，因为他们只需要往向容器中添加元素，而不用事先操心容器大小的问题。但是，如果由一个容量为 0 的 vector 开始，往里面添加元素会花费大量的运行性能。如果你之前就知道 vector 需要保存多少元素，就应该提前为其分配足够的空间。

    这里有一个简单的示例，往 vector 里添加 1 万个测试结构的实例——先进行不预分配空间的测试再进行有预分配的测试。

    vector<BigTestStruct> testVector1;
vector<BigTestStruct> testVector2;
sw.Restart();
FillVector(testVector1);
cout << "Time to Fill Vector Without Reservation:" << sw.ElapsedUs() << endl;
sw.Restart();
testVector2.reserve(10000);
FillVector(testVector2);
cout << "Time to Fill Vector With Reservation:" << sw.ElapsedUs() << endl;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在我的计算机中，未预分配空间的情况用了 5145 us，而预分配了空间的情况下只用了 1279us，性能提高了 75.14%！！！

    对于vector和 string，在需要更多空间的时候，会做与 realloc 等效的事情。这种类似 realloc 的操作有4个步骤：

    • (1)分配一个新的内存块，其容量是容器当前容量的数倍。多数实现中，vector 和 string 容量的提升因子在 1.5 和 2 之间。
    • (2)从容器原来占用的内存中将元素拷贝到新分配的内存中。
    • (3)释放原有内存中的对象。
    • (4)释放原有内存。

    有了所有这些操作：分配、回收、拷贝和释放，如果说这些步骤（对于性能）极其昂贵，你一点都不应该感到惊讶。当然，你肯定不希望频繁的进行这样的操作。如果这还没有打动你，那么想想每次进行这些步骤的时候，vector 和 string 中所有的迭代器、指针和引用都会失效。这意味着一个简单的插入操作，对于其它使用了当前 vector 或 string 中的迭代器、指针或引用的数据结构，都有可能引起对它们进行更新。”

    2. 使用 shrink_to_fit() 释放 vector 占用的内存， – clear() 或 erase() 不会释放内存

    与大家所想的相反，使用 erase() 或 clear() 从 vector 中删除元素并不会释放分配给 vector 的内存。做个简单的实验就可以证明这一点。我们往一个 vector 中添加 100 个元素，然后在这个 vector 上调用 clear() 和 erase()。然后我们可以让 capacity() 函数告诉我们为这个容器分配的内存可以存入多少元素。

    FillVector(testVector1);
size_t capacity = testVector1.capacity();
cout << "Capacity Before Erasing Elements:" << capacity << endl;
  
testVector1.erase(testVector1.begin(), testVector1.begin() + 3); //
capacity = testVector1.capacity();
cout << "Capacity After Erasing 3 elements Elements:" << capacity << endl;
testVector1.clear();
capacity = testVector1.capacity();
cout << "Capacity After clearing all emements:" << capacity << endl;
testVector1.shrink_to_fit();
capacity = testVector1.capacity();
cout << "Capacity After shrinking the Vector:" << capacity << endl;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    下面是输出：

    Capacity Before Erasing Elements:12138
Capacity After Erasing 3 elements Elements:12138
Capacity After clearing all emements:12138
Capacity After shrinking the Vector:0

    • 1
    • 2
    • 3
    • 4

    从上面的输出可以看到，erase() 或 clear() 不会减少 vector 占用的内存。如果在代码中到达某一点，不再需要 vector 时候，请使用std::vector::shrink_to_fit()方法释放掉它占用的内存。std::vector::shrink_to_fit(): 作用减少容器的容量以适应真实存放数据的大小并销毁超出容量的所有元素

    请注意，shrink_to_fit() 可能没有被所有编译器供应商完全支持。这种情况下，可以使用“Swap 惯用法”来清空 vector，代码如下

    container<T>( c ).swap( c ); // shrink-to-fit 惯用法，用于清空存储空间
container<T>().swap( c );    // 用于清空所有内容和存储空间的惯用法 

    • 1
    • 2

    3 在填充或者拷贝到 vector 的时候，应该使用赋值而不是 insert() 或push_back()

    从一个 vector 取出元素来填充另一个 vector 的时候，常有三种方法 – 把旧的 vector 赋值给新的 vector，使用基于迭代器的 std::vector::insert() 或者使用基于循环的 std::vector::push_back()。这些方法都展示在下面：

    vector<BigTestStruct> sourceVector, destinationVector;
FillVector(sourceVector);
// Assign sourceVector to destination vector
sw.Restart();
destinationVector = sourceVector;
cout << "Assigning Vector :" << sw.ElapsedUs() << endl;
//Using std::vector::insert()
vector<BigTestStruct> sourceVector1, destinationVector1;
FillVector(sourceVector1);
sw.Restart();
destinationVector1.insert(destinationVector1.end(),
  sourceVector1.begin(),
  sourceVector1.end());
cout << "Using insert() :" << sw.ElapsedUs() << endl;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    这是它们的性能：

赋值: 589.54 us

insert(): 1321.27 us

push_back(): 5354.70 us

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    我们看到 vector 赋值比 insert() 快了 55.38%，比 push_back() 快了 89%

    为什么会这样???
    赋值非常有效率，因为它知道要拷贝的 vector 有多大，然后只需要通过内存管理一次性拷贝 vector 内部的缓存。

    所以，想高效填充 vector，首先应尝试使用 assignment，然后再考虑基于迭代器的 insert()，最后考虑 push_back。当然，如果你需要从其它类型的容器拷贝元素到 vector 中，赋值的方式不可行。这种情况下，只好考虑基于迭代器的 insert()。

    4 遍历 std::vector 元素的时候，避免使用 std::vector::at() 函数

    遍历 vector 有如下三种方法：

    • (1) 使用迭代器

    • (2)使用 std::vector::at() 成员函数

    • (3)使用下标 –[ ]运算符

    下面展示了每种用法:

    //Using an iterator
vector<BigTestStruct> testVectorSum;
FillVector(testVectorSum);
sw.Restart();
int sum = 0;
for (auto it = testVectorSum.begin(); it != testVectorSum.end(); ++it)
{
  sum = sum + it->iValue;
}
cout << "Using Iterator:" << sw.ElapsedUs() << endl;
  
//Using the at() member function
sw.Restart();
sum = 0;
for (unsigned i = 0; i < testVectorSum.size(); ++i)
{
  sum = sum + testVectorSum.at(i).iValue;
}
cout << "Using at() :" << sw.ElapsedUs() << endl;
  
// Using the subscript notation
sw.Restart();
sum = 0;
for (unsigned i = 0; i < testVectorSum.size(); ++i)
{
  sum = sum + testVectorSum[i].iValue;
}
cout << "Using subscripting:" << sw.ElapsedUs() << endl;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    输出是：

    Using Iterator:0
Using at() :3.73
Using subscripting:0

    • 1
    • 2
    • 3

    显而易见，用std::vector::at()函数访问 vector 元素是最慢的一个。

    5 尽量避免在 vector 前部插入元素

    任何在 vector 前部部做的插入操作其复杂度都是 O(n) 的。在前部插入数据十分低效，因为 vector 中的每个元素项都必须为新的项腾出空间而被复制。如果在 vector 前部连续插入多次，那可能需要重新评估你的总体架构。

    做个有趣的尝试，下面是在 std::vector 前部做插入和在 std::list 前部部做插入的对比：

    vector<BigTestStruct> sourceVector3, pushFrontTestVector;
FillVector(sourceVector3);
list<BigTestStruct> pushFrontTestList;
//Push 100k elements in front of the new vector -- this is horrible code !!! 
sw.Restart();
for (unsigned i = 1; i < sourceVector3.size(); ++i)
{
  pushFrontTestVector.insert(pushFrontTestVector.begin(), sourceVector3[i]);
}
cout << "Pushing in front of Vector :" << sw.ElapsedUs() << endl;
// push in front of a list
sw.Restart();
for (unsigned i = 0; i < sourceVector3.size(); ++i)
{
  pushFrontTestList.push_front(sourceVector3[i]);
}
cout << "Pushing in front of list :" << sw.ElapsedUs() << endl;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    如果我运行这个测试10，其中使用一个包含100个元素的vector，那么输出结果如下：

    Average of Pushing in front of Vector :11999.4
Average of Pushing in front of list :20.36

    • 1
    • 2

    在 list 前部部插入操作比在 vector 前部部快大约58836%。不用感到奇怪，因为在 list 前部做元素插入的算法，其复杂度为 O(1)。显然，vector 包含元素越多，这个性能测试的结果会越差。

    6 在向 vector 插入元素的时候使用 emplace_back() 而不是 push_back()

    几乎赶上 C++11 潮流的每个人都明确地认同“安置”这种往 STL 容器里插入元素的方法。理论上来说，“安置”更有效率。然而所有实践都表明，有时候性能差异甚至可以忽略不计。

    思考下面的代码：

    vector<BigTestStruct> sourceVector4, pushBackTestVector, emplaceBackTestVector;
FillVector(sourceVector4);
//Test push back performance
sw.Restart();
for (unsigned i = 0; i < sourceVector4.size(); ++i)
{
  pushBackTestVector.push_back(sourceVector4[i]);
}
cout << "Using push_back :" << sw.ElapsedUs() << endl;
//Test emplace_back()
sw.Restart();
for (unsigned i = 0; i < sourceVector4.size(); ++i)
{
  emplaceBackTestVector.emplace_back(sourceVector4[i]);
}
cout << "Using emplace_back :" << sw.ElapsedUs() << endl;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    如果运行100次，会得到这样的输出：

    Average Using push_back :5431.58
Average Using emplace_back :5254.64

    • 1
    • 2

    可以清楚的看到，“安置”函数比插入函数性能更好 – 但只有 177 微秒的差距。在所有情况下，他们大致是相当的。

    仅在以下情况下，Emplacement 函数可能会更快：

    • 要添加的值是在 vector 中构造的，而不是赋值的。
    • 传递的参数类型与 vector 中保存的类型不同。例如，如果一个向量包含 std :: string，但我们传递一个字符串值到该 vector。

    即使上述两个条件都不成立，如本例所示的，你也不要因为在插入时使用 emplacement 而掉以轻心。
    更多关于 emplacement vs. insertion 的详细信息，请查看 Scott Meyer 的“Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14“一书中的条目＃42。

    7 释放vector

    在某个时间点后再也不会用到vector了，可以释放它所占用的空间及其成员所占用的空间

    int main() {
     std::vector<int> randy;
    for (int i = 0; i < 20; i++) {
        randy.push_back(i);
    }
    
    std::cout << "randy size: " << randy.size() << " capacity: " << randy.capacity()
              << std::endl;

    randy.clear();
    std::cout << "after clear, randy size: " << randy.size() << " capacity: " << randy.capacity()
              << std::endl;

    std::vector<int>().swap(randy);
    std::cout << "swap with empty vector, randy size: " << randy.size() << " capacity: " << randy.capacity()
              << std::endl;

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    运行结果：

    randy size: 20 capacity: 32
after clear, randy size: 0 capacity: 32
swap with empty vector, randy size: 0 capacity: 0

    • 1
    • 2
    • 3

    真正释放内存是在vector的析构函数里进行的，所以一旦超出vector的作用域，首先它所保存的所有对象会被析构，然后会调用allocator中的deallocate函数回收对象本身的内存。

    上述释放内存代码 std::vector().swap(randy);可以替换为以下形式:

    {
     std::vector<int> randy;
    for (int i = 0; i < 20; i++) {
        randy.push_back(i);
    }
} // 离开作用域，randy会调用自己的析构函数释放内存

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    如果vector内存的是指针，需要先释放每个指针所指内存，再释放vector

      std::vector<Randy *> sanjie(20, new Randy());

    for (size_t i = 0; i < 20; i++) {
      delete sanjie[i];
      sanjie[i] = nullptr;
    }
    randy.clear();
    std::vector<Randy *>().swap(sanjie);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    参考资料

    (1) 高效使用vector
    (2) 6 个技巧，提升 C++11 的 vector 性能

  • 相关阅读:
    Wing Loss 论文阅读笔记
    【探索Linux】—— 强大的命令行工具 P.11（基础IO，文件操作）
    PHP —— 用 ThinkPHP5.0 实现微信小程序登陆
    Spring-依赖注入
    48 路径总和 III
    公共功能测试用例
    Linux- 僵尸进程（Zombie Process）
    927. 三等分-按1划分 -力扣双百代码
    Web3风口吹到出版业 Paragraph如何打造全新的内容自营模式？
    useRef 无法挂载子组件信息，.curret为null
  • 原文地址：https://blog.csdn.net/weixin_38346042/article/details/133863414