C++，自己独特的指针排序向量实现
如何为指针的排序向量编写自己的 std::unique 实现，以便：
a）避免内存泄漏（稳定），
b）对于大型数据集尽快快速。
最简单的变体是比较具有索引 [i]、[i-1] 的 2 个相邻项，然后调用 item[i] 的析构函数并从向量中删除，看起来非常慢。
我可以询问该问题的可能解决方案吗？示例代码会很有帮助:-)。谢谢。
我尝试编写自己的具有以下功能的实现。这里有两个索引。第一个索引表示向量中的最后一个唯一元素，第二个索引是公共索引。
我正在逐个元素处理数组并交换元素，以便非唯一元素保留在向量的末尾。在我看来，这种一次性删除 k 个元素的方法比重复删除一个元素更快...
然后删除位于第一个索引右侧的所有元素...
这不是作业，这是一个严肃的问题。我需要从点云（1e9points）中删除重复的元素...
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 following 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)...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
与其滚动自己实现独特的算法，为什么不考虑使用 增强指针容器？这些容器旨在存储指向对象的指针而不是对象本身，并自动封装处理所有资源回收所需的逻辑。使用这些容器之一，您可以轻松地使用标准的独特算法。
如果您确实想推出自己的独特算法版本，我认为您有两个指针的想法是正确的，一个用于读取，一个用于写入。该算法的高级草图的工作原理如下：从索引零开始读取和写入指针。然后，重复应用此步骤：
当写指针指向所有唯一值之后的第一个值时，该算法终止。它不会丢失任何指针，因为元素仅被重新排序，而不被破坏。因此，完成后，您可以从写入指针迭代到数组末尾，释放找到的每个指针。这在 O(n) 时间内运行，这是渐近最优的。
希望这有帮助！
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:
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!