c++ - 如何使用 boost 库中的 integer_sort？

Question

我使用来自 boost/range/algorithm.hpp 的 boost::sort() 但真的......很慢而且我只是在使用无符号整数类型，所以我想“也许使用来自 boost/sort 的 integer_sort()/spreadsort/integer_sort.hpp 我可以 boost 速度”问题是 std::sort(v.begin(), v.end()) 在 ~54 秒内运行，而 boost:sort(v) 在~54 秒内运行(同时)

但我写了类似基数排序的东西，大约需要 28 秒，但我认为 integer_sort 可以比我的代码更优化，但我不知道如何使用 integer_sort。

#include <vector>
#include <boost/range/algorithm.hpp>
#include <boost/sort/spreadsort/integer_sort.hpp> // I WANT USE THIS
#include "myLib.hpp"

using namespace std;

int main(void)
{
  vector <unsigned> v(20);

  for (unsigned i = 0; i < v.size(); i++)
    v[i] = rand() % 1000;

  imprime(v); // THIS PRINTS THE VECTOR
  boost::sort(v); // THIS SORT THE VECTOR
  imprime(v);
  integer_sort(v.begin(), v.end()); // THIS DOES'T WORK

  return 0;
}

如果我尝试使用 integer_sort(v.begin(), v.end());我明白了

sort.cpp: In function ‘int main()’:
sort.cpp:23:34: error: ‘integer_sort’ was not declared in this scope
   integer_sort(v.begin(), v.end());
                                  ^
sort.cpp:23:34: note: suggested alternatives:
In file included from sort.cpp:5:0:
/usr/include/boost/sort/spreadsort/integer_sort.hpp:173:15: note:   ‘boost::sort::spreadsort::integer_sort’
   inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
               ^~~~~~~~~~~~
In file included from /usr/include/boost/sort/spreadsort/integer_sort.hpp:26:0,
                 from sort.cpp:5:
/usr/include/boost/sort/spreadsort/detail/integer_sort.hpp:482:5: note:   ‘boost::sort::spreadsort::detail::integer_sort’
     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
     ^~~~~~~~~~~~

我知道这与 (v.begin(), v.end()) RandomAccessIter first 有关 <- 当我尝试 std::sort(v) <- 这是不正确的。但我不明白错误信息。不要像 std::sort 那样说 candidate expects 3 arguments, 1 provided。

那么如何使用 integer_sort() 呢？

Boost Doc说:

integer_sort、float_sort 和 string_sort 都有 3 个主要版本: 基本版本，它采用第一个迭代器和最后一个迭代器，就像 std::sort:

integer_sort(array.begin(), array.end());
float_sort(array.begin(), array.end());
string_sort(array.begin(), array.end());

Answer 1

您在调用 integer_sort 时缺少 namespace 限定。

integer_sort 位于 boost::sort::spreadsort 命名空间中(参见 the documentation)。所以你的电话应该是这样的:

boost::sort::spreadsort::integer_sort(v.begin(), v.end());

另请注意，如果您尝试在同一程序中使用 boost::sort 和 Boost.Sort 库，您将会遇到问题，因为 boost::sort 函数模板与 Boost.Sort 命名空间冲突(参见 the bug report)。

boost::sort 只是 std::sort 的包装器，因此预计两者具有相同的性能。

如果数据量太小，

boost::sort::spreadsort::integer_sort 将使用 std::sort(低于 boost::sort: :spreadsort::detail::min_sort_size)，因此对于小数据大小，预计它们也具有几乎相同的性能(高达 integer_sort 检查是否使用 std::sort 或不)。