C++, own implementation of unique for sorted vector of pointers [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 11 years ago.

How to write the own implementation of std::unique for sorted vector of pointer so as:

a) avoid memory leaks (stable),

b) as soon as possible fast for large datasets.

The simplest variant comparing 2 adjacent items having indices[i], [i-1] followed by calling the destructor for item[i] and erasing from vector looks very slow.

Could I ask for possible solutions of the problem? Sample code would be helpful :-). Thanks.

I tried to write my own implementaion with the f开发者_高级运维ollowing functionality. Tehere are two indices. The first one represents the last unique element in vector and the second index is a common index.

I am processing array element by element and swapping the elements so as the non unique elements remains at the end of the vector. This approach erasing at once k-elements is, in my opininon, faster than repeated deletion of one element...

Then delete all elements located on the right of the first index...

It is not a homework, it is an serious question. I need to remove duplicate elements from the point cloud (1e9points)...

---

Rather than rolling your own implementation of the unique algorithm, why not instead consider using one of the Boost pointer containers? These containers are designed to store pointers to objects instead of objects themselves and automatically encapsulates the logic necessary to handle all the resource reclamation. Using one of those containers, you could easily just use the standard unique algorithm.

If you do want to roll your own version of the unique algorithm, I think that you are right on the money with the idea to have two pointers, one for reading and one for writing. The high-level sketch of the algorithm works like this: start both the read and write pointers at index zero. Then, repeatedly apply this step:

1. Look at the value pointed at by the read pointer and create a new temporary pointer to point to it.
2. Advance the read pointer forward.
3. While the element under the read pointer is the same as the remembered value, advance the read pointer forward.
4. (At this point, the element under the read pointer is the first value not equal to the current value.)
5. Swap the element under the write pointer with the value pointed at by the temporary pointer to the unique element.
6. Advance the write pointer forward.

This algorithm terminates with the write pointer pointing to the first value past all of the unique values. It does not lose any pointers, since elements are only reordered, not destroyed. Consequently, when you're done you can iterate from the write pointer to the end of the array, freeing each pointer you find. This runs in O(n) time, which is asymptotically optimal.

Hope this helps!