从矢量中最快擦除元素或更好地使用内存（排序基数）

Question

我遇到了麻烦，我从基数排序算法创建了一个实现，但我认为我可以使用更少的内存，而且我可以！但是......我这样做是在使用后擦除向量的元素。问题：3 分钟执行 vs 17 秒。如何更快地擦除元素？或者...如何更好地利用内存。

sort.hpp

#include <iostream>

#include <vector>
#include <algorithm>

unsigned digits_counter(long long unsigned x);

void radix( std::vector<unsigned> &vec )
{
  unsigned size = vec.size();
  if(size == 0);
  else {
    unsigned int max = *max_element(vec.begin(), vec.end());
    unsigned int digits = digits_counter( max );

    // FOR EVERY 10 POWER...
    for (unsigned i = 0; i < digits; i++) {
      std::vector < std::vector <unsigned>  > base(10, std::vector <unsigned> ());

#ifdef ERASE
      // GET EVERY NUMBER IN THE VECTOR AND
      for (unsigned j = 0; j < size; j++) {
    unsigned int digit = vec[0];

    // GET THE DIGIT FROM POSITION "i" OF THE NUMBER vec[j]
    for (unsigned k = 0; k < i; k++)
      digit /= 10;
    digit %= 10;

    // AND PUSH NUMBER IN HIS BASE BUCKET
    base[ digit ].push_back( vec[0] );
    vec.erase(vec.begin());
      }

#else
      // GET EVERY NUMBER IN THE VECTOR AND
      for (unsigned j = 0; j < size; j++) {
    unsigned int digit = vec[j];

    // GET THE DIGIT FROM POSITION "i" OF THE NUMBER vec[j]
    for (unsigned k = 0; k < i; k++)
      digit /= 10;
    digit %= 10;

    // AND PUSH NUMBER IN HIS BASE BUCKET
    base[ digit ].push_back( vec[j] );
      }
      vec.erase(vec.begin(), vec.end()); 
#endif

      for (unsigned j = 0; j < 10; j++)
    for (unsigned k = 0; k < base[j].size(); k++)
      vec.push_back( base[j][k] );
    }
  }
}


void fancy_sort( std::vector <unsigned> &v ) {
  if( v.size() <= 1 )
    return;
  if( v.size() == 2 ) {
    if (v.front() >= v.back())
      std::swap(v.front(), v.back());
    return;
  }
  radix(v);
}

sort.cpp

#include <vector>

#include "sort.hpp"

using namespace std;

int main(void)
{
  vector <unsigned> vec;

  vec.resize(rand()%10000);

  for (unsigned j = 0; j < 10000; j++) {
    for (unsigned int i = 0; i < vec.size(); i++)
      vec[i] = rand() % 100;
    fancy_sort(vec);
  }


  return 0;
}

我只是在学习...这是我的 Deitel C++ 的第 2 章。所以...如果有人有更复杂的解决方案...我可以学习如何使用它，难度无关紧要。

结果不擦除：

g++ -O3 -Wall sort.cpp && time ./a.out
./a.out  2.93s user 0.00s system 98% cpu 2.964 total

擦除：

g++ -D ERASE -O3 -Wall sort.cpp && time ./a.out
./a.out  134.64s user 0.06s system 99% cpu 2:15.20 total

Answer 1

std::vector 不是用来拆掉零件的。这是你必须接受的事实。您在速度和内存使用之间的权衡是一个经典问题。对于 vector，任何移除（除了它的末尾）都是昂贵且浪费的。这是因为每次删除元素时，程序要么必须在内部重新分配数组，要么必须移动所有元素以填充空白。如果你继续使用矢量，这是一个你永远无法克服的终极限制。

您的问题的向量：速度快但内存使用量大。

另一个（可能）最佳极端（内存方面）是 std::list, which has absolutely no problem with removing anything anywhere. On the other hand, accessing elements is only possible by iterating over the whole list to the element, because it's basically a doubly-linked list，您不能通过编号访问元素。

针对您的问题的列表：最佳内存使用率，但速度较慢，因为访问列表元素很慢。

最后，中间立场是 std::deque. They offer a middle grounds between vectors and lists. They're not contiguous in memory, but items can be found by their numbers. Removing elements from the middle doesn't necessarily cause the same destruction in vectors. Read this 以了解更多信息。

双端队列解决您的问题： 中间立场，取决于问题，内存和访问速度可能都很快。

如果记忆是您最关心的问题，那么一定要选择列表。这是最快的。如果您想要最通用的解决方案，请使用双端队列。也不要忽视将整个数组复制到另一个容器的可能性，对其进行排序，然后再复制回来。根据数组的大小，这可能会有所帮助。

从矢量中最快擦除元素或更好地使用内存（排序基数）

Fastest erase element from vector or better use of memory (sorting radix)

c++

radix-sort

stdvector