删除指向c++列表的指针非常非常慢。为什么?

I am trying to get rid of an STL list fast. So I have declared a pointer to that list. I do the all manipulations and then I delete the pointer to free up the RAM. But the process of deletion the pointer to the list is slow and as slow as when I do list.clear(). So it is very slow. Why does that happen? How can I delete the allocated RAM fast? When I am dealing with vector and deque the deletion is fast. Below is a program which demonstrates that.

我正试图快速摆脱STL列表。所以我已经声明了一个指向该列表的指针。我执行所有操作，然后删除指针来释放内存。但是删除指针到列表的过程是缓慢的，和我做列表时一样慢。clear()。所以速度很慢。为什么会这样呢?如何快速删除已分配的RAM ?当我处理向量的时候，删除的速度很快。下面是一个演示的程序。

//============//
// STL delete //
//============//

#include <iostream>     
#include <algorithm>    
#include <vector>       
#include <list>
#include <deque>
#include <cmath>
#include <iomanip>
#include <ctime>

using std::cout;
using std::cin;
using std::endl;
using std::list;
using std::vector;
using std::deque;
using std::fixed;
using std::setprecision;
using std::showpoint;
using std::sort;

// the main program

int main() 
{
  // variables and parameters

  const long int I_MAX = static_cast<long int>(pow(10.0, 7.5));
  const long int K_MAX = static_cast<long int>(pow(10.0, 6.0));
  long int i;
  long int k;
  clock_t t1;
  clock_t t2;
  double tall;

  // set the output

  cout << fixed;
  cout << setprecision(5);
  cout << showpoint;

  // main bench loop

  for (k = 0; k < K_MAX; k++)
  {
    list<double>   * listA  = new list<double>   [1];
    vector<double> * vecA   = new vector<double> [1];
    deque<double>  * deqA   = new deque<double>  [1];

    cout << endl;
    cout << "------------------------------->>> " << k << endl;
    cout << endl;

    // build the vector

    t1 = clock();

    cout << "  1 --> build the vector ..." << endl;

    for (i = 0; i < I_MAX; i++)
    { vecA->push_back(static_cast<double>(cos(i))); }

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << "  2 --> done with the vector --> " << tall << endl;

    // build the list

    t1 = clock();

    cout << "  3 --> build the list ..." << endl;

    for (i = 0; i < I_MAX; i++)
    { listA->push_back(static_cast<double>(cos(i))); }

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << "  4 --> done with the list   --> " << tall << endl;

    // build the deque

    t1 = clock();

    cout << "  5 --> build the deque ..." << endl;

    for (i = 0; i < I_MAX; i++)
    { deqA->push_back(static_cast<double>(cos(i))); }

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << "  6 --> done with the deque  --> " << tall << endl;

    // sort the vector

    t1 = clock();

    cout << "  7 --> sort the vector ..." << endl;

    sort(vecA->begin(), vecA->end());

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << "  8 --> done with the vector --> " << tall << endl;

    // sort the list

    t1 = clock();

    cout << "  9 --> sort the list ..." << endl;

    listA->sort();

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << " 10 --> done with the list   --> " << tall << endl;

    // sort the deque

    t1 = clock();

    cout << " 11 --> sort the deque ..." << endl;

    sort(deqA->begin(), deqA->end());

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << " 12 --> done with the deque  --> " << tall << endl;

    // delete the vector

    t1 = clock();

    cout << " 13 --> delete the vector ..." << endl;

    delete [] vecA;

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << " 14 --> done with the vector --> " << tall << endl;

    // delete the list

    t1 = clock();

    cout << " 15 --> delete the list ..." << endl;

    delete [] listA;

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << " 16 --> done with the list   --> " << tall << endl;

    t1 = clock();

    // delete the deque

    cout << " 17 --> delete the deque ..." << endl;

    delete [] deqA;

    t2 = clock();

    tall = (t2-t1)/static_cast<double>(CLOCKS_PER_SEC);

    cout << " 18 --> done with the deque  --> " << tall << endl;
  }

  int sentinel;
  cin >> sentinel; 

  return 0;
}

2 个解决方案

#1

Every element in the list has its own node, meaning an extra allocation which has to be freed.

列表中的每个元素都有自己的节点，这意味着需要释放额外的分配。

If you want to get rid of it all really fast and use members with trivial destructors (no call needed), use a custom allocator for the list, which is optimized for that.
BTW: Allocating the container on the heap is a pessimisation.

如果您想要快速地删除它，并且使用那些具有简单的析构函数的成员(不需要调用)，请使用自定义的分配器来进行列表，这是优化的。BTW:在堆上分配容器是一个悲观的方法。

Anyway, depending on your use-case another container like std::vector might make sense instead.

无论如何，根据您的用例，另一个容器如std::vector可能是有意义的。

#2

The problem is not so much deleting the list, as understanding how a list is represented as a chain of heap-allocated nodes.

问题不在于删除列表，而是理解列表是如何表示为一个由堆分配的节点组成的链。

So basically when you deleted the list, it also has to delete the ~30M nodes as well, which will absolutely be a noticeably slow operation.

因此，当你删除列表时，它也必须删除~30M节点，这绝对是一个明显的慢操作。

Generally speaking a list is not a great container for small builtin types anyway due to the node overhead possibly taking more space than the data themselves.

一般来说，对于小的构建类型来说，列表并不是一个大容器，因为节点开销可能比数据本身占用更多的空间。

Can you give us more information about the real problem you're trying to solve?

你能给我们更多的关于你想解决的问题的信息吗?