Is it possible to apply std::sort on std::unique?

Question

Suppose I have a dynamic array that I want to sort, I could do

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

but for performance critical code, the initialization overhead is unacceptable, more details at https://stackoverflow.com/a/7269088/3667089

I could also do

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

but having to manage memory ourselves is bound to memory leak in large codebases.

So it seems that the most feasible approach is

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

No initialization overhead nor need to worry about memory management, but this returns a long compilation error. Could someone let me know what I am doing wrong?

I am on Ubuntu 14.04, GCC as compiler.

EDIT: Change the code so the data is not already sorted

Answer 1

std::sort still needs iterators, and unique_ptr is not an iterator. However, it does hold onto something that can be used as one: its pointer:

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

or

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

or

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

---

But what you really want is a vector allocator that default-initializes instead of value-initializes. That's where the performance difference is coming from - using std::vector with the default allocator will zero-initialize all your ints first and then assign them some value, whereas your other options do not have this extra zero-initialization step.

Check out Casey's implementation of such a thing and then just do:

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());

A different approach which is simpler in the sense that you don't have to deal with allocators (though more annoying on the code-wise) is to introduce a wrapper for int for which value-initialization does not do anything:

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... 

Note that simply using reserve() and push_back() is insufficient - that's still quite a bit more work that needs to be done than simply assigning by index after default-initialization, and if you're latency sensitive enough to have asked this question, that can be significant.

Answer 2

Reading the link from the question, it seems you'd be happy using a vector if it didn't call an unnecessary constructor for every element. There are techniques to eliminate this overhead.

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