9

したがって、次のような単語のベクトルがある場合:

Vec1 = "words", "words", "are", "fun", "fun"

結果のリスト: 「楽しい」、「言葉」

どの単語が重複しているかを判断し、それらの 1 つのコピーのアルファベット順のベクトルを返そうとしています。私の問題は、どこから始めればいいのかわからないことです。それに近いのは、std::unique_copy必要なことを正確に実行しないことだけでした。具体的には、a を入力してstd::vector<std::string>いますが、a を出力していstd::list<std::string>ます。必要に応じて、ファンクターを使用できます。

誰かが少なくとも私を正しい方向に押してくれませんか? 私はすでにstlのドキュメントを読んでみましたが、今は「脳」がブロックされています。

4

6 に答える 6

7

3行で（ベクトルとリストの作成も、読みやすさのための余分な改行も数えません）：

vector<string> vec{"words", "words", "are", "fun", "fun"};
list<string> output;

sort(vec.begin(), vec.end());
set<string> uvec(vec.begin(), vec.end());
set_difference(vec.begin(), vec.end(),
               uvec.begin(), uvec.end(),
               back_inserter(output));

編集

解決策の説明:

  1. 後で使用するには、ベクトルをソートする必要がありますset_difference()。

  2. セットはuvec自動的に要素を並べ替え、重複を排除します。

  3. リストにはのoutput要素が入力されますvec - uvec。

于 2013-07-27T08:19:58.040 に答える
6
  1. 空にするstd::unordered_set<std::string>
  2. ベクトルをイテレータし、各アイテムがセットのメンバーであるかどうかを確認します
  3. すでにセットにある場合、これは重複しているため、結果リストに追加してください
  4. それ以外の場合は、セットに追加します。

各重複を結果に一度だけリストする必要があるため、結果にハッシュセット (リストではなく) を使用することもできます。

于 2013-07-27T00:32:37.300 に答える
1

その場で（追加のストレージなし）。文字列のコピーはありません (結果リストを除く)。1 ソート + 1 パス:

#include <string>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
        vector<string> vec{"words", "words", "are", "fun", "fun"};
        list<string> dup;

        sort(vec.begin(), vec.end());

        const string  empty{""};
        const string* prev_p = &empty;

        for(const string& s: vec) {
                if (*prev_p==s) dup.push_back(s);
                prev_p = &s;
        }

        for(auto& w: dup) cout << w << ' '; 
        cout << '\n';
}
于 2013-07-27T08:50:19.447 に答える
0

他の人が提案したアルゴリズムよりも優れたアルゴリズムを次に示します。

#include <algorithm>
#include <vector>

template<class It> It unique2(It const begin, It const end)
{
    It i = begin;
    if (i != end)
    {
        It j = i;
        for (++j; j != end; ++j)
        {
            if (*i != *j)
            { using std::swap; swap(*++i, *j); }
        }
        ++i;
    }
    return i;
}
int main()
{
    std::vector<std::string> v;
    v.push_back("words");
    v.push_back("words");
    v.push_back("are");
    v.push_back("fun");
    v.push_back("words");
    v.push_back("fun");
    v.push_back("fun");
    std::sort(v.begin(), v.end());
    v.erase(v.begin(), unique2(v.begin(), v.end()));
    std::sort(v.begin(), v.end());
    v.erase(unique2(v.begin(), v.end()), v.end());
}

swapストレージの補助を必要としないため、より優れていvectorます。つまり、以前のバージョンの C++ で最適に動作し、要素をコピー可能にする必要はありません。

あなたがもっと賢いなら、ベクトルを2回ソートすることも避けることができると思います。

于 2013-07-27T08:33:56.650 に答える
0

std::map を使用して出現回数をカウントし、 std::list::sort に依存して結果の単語リストをソートすることで、かなりクリーンな実装を得ることができます。例えば：

std::list<std::string> duplicateWordList(const std::vector<std::string>& words) {
    std::map<std::string, int> temp;
    std::list<std::string> ret;
    for (std::vector<std::string>::const_iterator iter = words.begin(); iter != words.end(); ++iter) {
        temp[*iter] += 1;
        // only add the word to our return list on the second copy
        // (first copy doesn't count, third and later copies have already been handled)
        if (temp[*iter] == 2) {
            ret.push_back(*iter);
        }
    }
    ret.sort();
    return ret;
}

std::map を使用すると、少し無駄に思えますが、仕事は完了します。

于 2013-07-27T00:25:00.423 に答える