C++:std::vector 与 std::list 的性能-6ren

C++:std::vector 与 std::list 的性能

转载作者：太空宇宙更新时间：2023-11-04 12:53:07

25

4

<分区>

我有以下代码来分析各种 N 的 std::vector 性能与 std::list 的对比。

void vectorPerf(size_t n)
{
   std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
   std::vector<size_t> cache;
   for (size_t i = 0; i < n; i++) {
      cache.push_back(i);
   }
   std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();

   auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();

   std::cout << duration << " us." << "\n";

   return;
}

void listPerf(size_t n)
{
   std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
   std::list<size_t> cache;
   for (size_t i = 0; i < n; i++) {
      cache.push_back(i);
   }
   std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();

   auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();

   std::cout << duration << " us." << "\n";

   return;
}

int main(int argc, char** argv)
{

   if (argc != 2) {
      return -1;
   }
   std::stringstream ss(argv[1]);
   size_t n;
   ss >> n;
   vectorPerf(n);
   std::cout << "\n";
   listPerf(n);
   std::cout << "\n";
}

对于同一组 N 的多次运行，我得到的结果与以下数字的顺序一致:

N       std::vector  std::list
1000    46           116
2000    85           217
5000    196          575
10000   420          1215
100000  3188         10497
1000000 34489        114330

我想知道的是，为什么 std::list 的性能一直比 std::vector 差。对于 std::vector，我预计性能会分摊 O(N)，因为支持 std::vector 的内部对象需要不时调整大小。因为我所做的只是将一个元素插入到列表的末尾，所以我希望 std::list 为 O(1)。所以这表明 std::list 会比 std::vector 做得更好，但事实似乎恰恰相反。

如果有人能阐明发生这种情况的原因，我将不胜感激。我正在 MacOS 10.12.6 上使用 g++ 在 2015 MBP 上进行编译。

谢谢。

编辑:我现在明白 std::vector::push_back() 是分期 O(1) 的。然而，我不清楚的是为什么 std::list::push_back() 的性能始终比 std::vector::push_back() 差？

25

4

0

文章推荐： html - CSS 页面转换和动画

文章推荐： C++:在不裁剪的情况下调整图像的 HSL

c++ - 为什么 `std::common_type_t` 等于 `std::ostream` 而不是 `std::ostream &` ？
我正在开发一个小型图书馆，我需要做的一件事是让访问者访问一些数据并返回结果。在一些较旧的 C++ 代码中，访问者需要声明一个 typedef return_type .例如，boost::stati
c++ - std::map 麻烦
我正在尝试使用std:map类型的键和值制作std::any Visual Studio 2017 std::map m("lastname", "Ivanov"); std::cout (m["la
C++ std::map> 。如何循环设定值？
我已经在 C++ 的 map 中声明了一个集合为 std::map> .如何循环访问或打印设定值？最佳答案如果你知道如何迭代 std::map或 std::set单独地，您应该可以毫无问题地组合迭
C++ 循环 std::vector>
如何循环？我已经试过了: //----- code std::vector >::iterator it; for ( it = users.begin(); it != users.end();
c++ - std::unique_lock 还是 std::lock_guard？
我有两个用例。 A.我想同步访问两个线程的队列。 B.我想同步两个线程对队列的访问并使用条件变量，因为其中一个线程将等待另一个线程将内容存储到队列中。对于用例 A，我看到了使用 std::lock_
c++ - std::trivially_copyable_v 和 std::is_pod_v 之间有什么区别(std::is_standard_layout && std::is_trivial_v)
我正在查看这两种类型特征的文档，但不确定有什么区别。我不是语言律师，但据我所知，它们都适用于“memcpy-able”类型。它们可以互换使用吗？最佳答案不，这些术语不能互换使用。这两个术语都表示
c++ - 为什么我可以有一个 std::vector 而不是 std::vector？
我有以下测试代码，其中有一个参数 fS，它是 ofstream 的容器: #include #include #include #include int
c++ - std::unordered_map
这是这个问题的延续 c++ function ptr in unorderer_map, compile time error 我试图使用 std::function 而不是函数指针，并且只有当函数是

c++ - 将 std::any_of、std::all_of、std::none_of 等与 std::map 一起使用
std::unordered_map str_bool_map = { {"a", true}, {"b", false}, {"c", true} }; 我们可以在此映射上使
c++ - 使用 std::find 检查 std::vector> 中的项目
我有以下对象 std::vector> vectorList; 然后我添加到这个使用 std::vector vec_tmp; vec_tmp.push_back(strDRG); vec_tmp.p
c++ - 为什么 std::initializer_list 不支持 std::get<>、std::tuple_size 和 std::tuple_element
为什么 std::initializer_list不支持std::get<> , std::tuple_size和 std::tuple_element ？在constexpr中用得很多现在的表达式，
c++ - std::tuple 和 std::tuple 是否被 std::vector 视为同一类型？
我有一个像这样定义的变量 auto drum = std::make_tuple ( std::make_tuple ( 0.3f , Ex
c++ :将 std::map 转换为 std::map
假设我有一个私有(private)std::map在我的类(class)里std::map 。我怎样才能将其转换为std::map返回给用户？我想要下面的原型(prototype) const std
c++ :将 std::map 转换为 std::map
假设我有一个私有(private)std::map在我的类(class)里std::map 。我怎样才能将其转换为std::map返回给用户？我想要下面的原型(prototype) const std
c++ - 在带有 std::ref 的 std::thread 中使用地址清理调用 std::invoke(std::forward(...)) 时的奇怪行为
问题我正在尝试将 lambda 闭包传递给 std::thread，它使用任意封闭参数调用任意封闭函数。 template std::thread timed_thread(Function&& f
c++ - 具有模板模板参数的模板定义，可以专门化为类，例如，std::vector 或 std::map
我想创建一个模板类，可以容纳容器和容器的任意组合。例如，std::vector或 std::map ，例如。我尝试了很多组合，但我必须承认模板的复杂性让我不知所措。我编译的关闭是这样的: templ
c++ - 将 std::vector> 分配给另一个 std::vector>
我有一个 std::vector>我将其分配给相同类型的第二个 vector 。我收到这个编译器错误: /opt/gcc-8.2.0/include/c++/8.2.0/bits/stl_algob
c++ - 将 std::vector> 移动到 std::vector>
有时候，我们有一个工厂可以生成一个 std::unique_ptr vector ，后来我们想在类/线程/你命名的之间共享这些指针。因此，最好改用 std::shared_ptr 。当然有一种方法可以
c++ - 为什么 std::sort 假定 std::vector< std::vector> 默认为 std::vector，从而产生错误的结果？
这个问题在这里已经有了答案: Sorting a vector of custom objects (14 个答案) 关闭 6 年前。我创建了一个 vector vector ，我想根据我定义的参
c++ - 将 std::vector> 转换为 std::vector>
我有三个类(class)成员: public: std::vector > getObjects(); std::vector > getObjects() const; privat

首页

博学

6Ren·AI

商城

C++:std::vector 与 std::list 的性能