是否可以在 std::unique<T[ ]> 上应用 std::sort？

Question

假设我有一个要排序的动态数组，我可以这样做

std::vector<int> v(100);
for (int i = 0; i < 100; i++) v[i] = rand();
std::sort(v.begin(), v.end());

但是对于性能关键代码，初始化开销是不可接受的，更多细节在

我也可以

int *v = new int[100];
for (int i = 0; i < 100; i++) v[i] = rand();
std::sort(v, v + 100);

但是必须自己管理内存必然会导致大型代码库中的内存泄漏。

所以看来最可行的做法是

std::unique_ptr<int[]> v(new int[100]);
for (int i = 0; i < 100; i++) v[i] = rand();
std::sort(v, v + 100);

没有初始化开销，也不需要担心内存管理，但是这个 returns 一个很长的编译错误。有人可以让我知道我做错了什么吗？

我在 Ubuntu 14.04，GCC 作为编译器。

编辑：更改代码，使数据尚未排序

Answer 1

std::sort 仍然需要迭代器，而 unique_ptr 不是迭代器。但是，它确实保留了可以用作一个的东西：它的指针：

std::sort(v.get(), v.get() + 100);

或

std::sort(&*v, &*v + 100);

或

std::sort(&v[0], &v[0] + 100); // N.B. &v[100] invokes undefined behavior

但是您真正想要的是一个 vector 默认初始化而不是值初始化的分配器。这就是性能差异的来源 - 使用 std::vector 和默认分配器将首先对所有 int 进行零初始化，然后为它们分配一些值，而你的其他选项没有这个额外的零 -初始化步骤。

检查 Casey's 实现这样的事情，然后就这样做：

std::vector<int, default_init_allocator<int>> v(100); // not zero-initialized
for (int i = 0; i < 100; i++) v[i] = i;
std::sort(v.begin(), v.end());

一种不同的方法，在您不必处理分配器的意义上更简单（尽管在代码方面更烦人）是为 int 引入一个包装器，为其进行值初始化什么都不做：

template <class T>
struct Wrapper {
    Wrapper() { }
    T value;
};

std::vector<Wrapper<int>> v(100);              // not zero-initialized
for (int i = 0; i < 100; i++) v[i].value = i;  // but have to do this...

请注意，仅使用 reserve() 和 push_back() 是不够的 - 与在默认初始化后简单地按索引分配相比，这仍然需要做更多的工作，如果你是延迟敏感到足以问这个问题，这可能很重要。

Answer 2

阅读问题中的 link，如果 vector 没有为每个元素调用不必要的构造函数，您似乎会很高兴使用它。有一些技术可以消除这种开销。

std::vector<int> v;
v.reserve(100);
for (int i = 0; i < 100; i++) v.emplace_back(rand());
std::sort(v.begin(), v.end());

是否可以在 std::unique<T[ ]> 上应用 std::sort？

Is it possible to apply std::sort on std::unique<T[ ]>?

c++

heap-memory

unique-ptr

c++11