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::uniquechunks（一例として）ソートされた場合のように、一意でない要素が隣接していると想定します。これにより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;
}

独自の述語を持つ可能性は実装されていません。可能ですが、1つの欠点は、less-than機能を提供する必要があることです。機能を提供する必要がありequality、場合によっては不可能なこともあります。

于 2013-03-14T16:33:17.137 に答える
1

std::uniqueアルゴリズムは、入力範囲が適切であると想定し、2つの連続する値を比較することによって重複を削除します。アルゴリズムを使用できるようにするには、最初に入力を並べ替える必要があります。

于 2013-03-14T15:55:52.603 に答える