1

除非我遗漏了什么或误解了机制（很可能）这个向量中不应该存在“1”重复吗？

chunks.erase( std::unique ( chunks.begin(), chunks.end(), 
                           []( std::string &s1, std::string &s2 ){ 
                              return ( s1.compare(s2) == 0 ? true : false );}), 
                           chunks.end() );

在执行上述操作之前：

1       l:1
1+      l:2
1+1     l:3
1+1=    l:4
+       l:1
+1      l:2
+1=     l:3
1       l:1
1=      l:2
=       l:1

执行上述代码后：

1       l:1
1+      l:2
1+1     l:3
1+1=    l:4
+       l:1
+1      l:2
+1=     l:3
1       l:1
1=      l:2
=       l:1

我尝试过不使用谓词（假设将删除相同的 std::strings）。出于某种原因，“那些”被识别为相同？我查看了它们的长度（假设空格被卡在前缀或后缀中），但它们的长度相同。

我错过了什么吗？

4

4 回答 4

13

你（可能）误解了一些东西。

std::unique仅删除连续的重复项，因此如果您希望删除所有重复项，应用的先决条件std::unique是使用相同的谓词对您的范围进行排序。

于 2013-03-14T15:55:07.010 回答
4

std::unique假设非唯一元素是相邻的，就像（例如）chunks排序时那样。这允许std::unique具有 O(n) 复杂度。

如果你想保持一个特定的顺序vector并删除重复项，那就是 O(n 2 ) 复杂性的问题。您可以使用此处提供的逻辑来执行此操作。

// Create a new vector without the duplicates
std::vector<string> unique_chunks;
for (std::vector<string>::iterator x = chunks.begin(); x != chunks.end();) {
  if ( unique_chunks.find(*x) != unique_chunks.end() ) {
    unique_chunks.push_back( *x );
  }
}

// Make chunks hold this new vector (allowing the old vector to be destroyed)
std::swap( chunks, unique_chunks );

不，你不需要那个谓词。

于 2013-03-14T15:55:36.927 回答
3

如其他答案中所述，unique删除连续的重复块，如果您需要删除重复项并及时保留其余元素的顺序（第一次出现的顺序，此处），O(N log N)您可以执行以下操作：

template<typename T>
bool bySecond(const pair<T, int>& a, const pair<T, int>& b) {
    return a.second < b.second;
}

template<typename T>
bool firstEqual(const pair<T, int>& a, const pair<T, int>& b) {
    return a.first == b.first;
}

template<typename it>
it yourUnique(it begin, it end){
    typedef typename std::iterator_traits<it>::value_type value_t;
    vector<pair<value_t, int>> v;
    for(it c = begin; c != end; ++c){
        v.push_back(make_pair(*c, v.size())); // second is start index;
    }
    sort(v.begin(), v.end()); // sort by value then by index
    v.erase(unique(v.begin(), v.end(), firstEqual<value_t>), v.end());
    sort(v.begin(), v.end(), bySecond<value_t>); // restore order.
    it c = begin;

    for(const auto& x: v){
       *(c++) = x.first;
    }
    return it;
}

没有实现拥有自己的谓词的可能性。这是可能的，但一个缺点是您必须提供less-than功能，而不是equality一个，这在某些情况下可能是不可能的。

于 2013-03-14T16:33:17.137 回答
1

该std::unique算法假定输入范围是有序的，并通过比较两个连续值来删除重复项。为了能够使用该算法，您需要首先对输入进行排序。

于 2013-03-14T15:55:52.603 回答