从std::vector中删除重复元素，但从前面开始?

Question

如何从矢量中删除重复元素，但从前面开始?

2 3 4 5 2 5将变成3 4 2 5

1 5 3 1会变成5 3 1

我希望解决方案易于阅读，如果它也有良好的性能，那就太好了。

Answer 1

如果容器支持双向迭代器，那么从容器的哪一侧删除重复元素并不重要，因为可以使用反向迭代器。

这是一个示范程序。

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <algorithm> 

template <typename ForwardIterator> 
ForwardIterator remove_duplicates( ForwardIterator first, ForwardIterator last ) 
{ 
for ( ; first != last; ++first ) 
{ 
last = std::remove( std::next( first ), last, *first ); 
} 

return last; 
} 

int main() 
{ 
std::vector<int> v = { 1, 2, 3, 4, 5, 4, 3, 2, 1 }; 

for ( const auto &item : v ) std::cout << item << ' '; 
std::cout << 'n'; 

v.erase( remove_duplicates( std::begin( v ), std::end( v ) ), std::end( v ) ); 

for ( const auto &item : v ) std::cout << item << ' '; 
std::cout << 'n'; 

std::cout << 'n'; 

v.assign( { 1, 2, 3, 4, 5, 4, 3, 2, 1 } ); 

for ( const auto &item : v ) std::cout << item << ' '; 
std::cout << 'n'; 

v.erase( std::begin( v ), remove_duplicates( std::rbegin( v ), std::rend( v ) ).base() ); 

for ( const auto &item : v ) std::cout << item << ' '; 
std::cout << 'n'; 
} 

程序输出为

1 2 3 4 5 4 3 2 1 
1 2 3 4 5 
1 2 3 4 5 4 3 2 1 
5 4 3 2 1 

Answer 2

一个渐近有效算法(N log N):

• 创建一个迭代器范围，每个迭代器都指向原始容器
• 使用稳定排序对迭代器进行排序。使用间接通过迭代器的比较函数。
• 使用反向迭代器和类似的自定义比较函数删除连续重复(std::unique)。
• std::remove_if从vector容器中移除迭代器不在辅助容器中的元素。

这比O(N*N)的解决方案要复杂一些。下面是一个示例实现。我不能保证它是正确的。

template<class It, class Sentinel>
auto remove_duplicates(It first, Sentinel last)
{
std::vector<It> iterators;
auto iterator_generator = [it = first]() mutable {
return it++;
};
std::generate_n(
std::back_inserter(iterators),
last - first,
iterator_generator);
auto iterator_compare = [](const auto& l, const auto& r) {
return *l < *r;
};

std::stable_sort(
iterators.begin(),
iterators.end(),
iterator_compare);
auto iterator_eq = [](const auto& l, const auto& r) {
return *l == *r;
};
auto last_unique = std::unique(
iterators.begin(),
iterators.end(),
iterator_eq);
iterators.erase(last_unique, iterators.end());
auto keep_generator = [it = first]() mutable {
return it++;
};
std::vector<bool> remove(last - first, true);
for(auto it : iterators) {
auto index = it - first;
remove[index] = false;
}

auto remove_predicate = [index = 0, remove = std::move(remove)](const auto& el) mutable {
return remove[index++];
};
return std::remove_if(first, last, std::move(remove_predicate));
}
// usage with reverse iterators
v.erase(
v.rend().base(),
remove_duplicates(v.rbegin(), v.rend()).base());