1

std::string の 2 つのベクトル間で共通の単語を見つけようとしています。それらを長さでソートされたソート済みリストに入れ、次に各長さの単語をアルファベット順にソートしたいと考えています。stl 関数とファンクターを使用する必要があります。

私の考え: for_each を使用して最初のベクトルを通過し、単語ごとに、ファンクターを使用して他のベクトルと比較します (一般的な場合は、ファンクターのリストに追加します)。結果のリストには、一般的な単語のみが含まれます。アルファベット順に並べ替える方法は知っていますが、長さで並べ替えてから、同じ長さのチャンクをアルファベット順に並べ替えるにはどうすればよいですか? stl を見回しましたが、必要なものが見つかりません。または、これについて間違った方法で考えているだけです。何か案は？

例：

vec1:「および」、「したがって」、「それ」、「ある」、「a」、「始まり」、「および」、「終わり」

vec2:「そして」、「したがって」、「星」、「ある」、「始まり」、「へ」、「落ちる」、「へ」、「彼らの」、「終わり」

結果: 「そして」、「終わり」、「始まり」

4

5 に答える 5

4

vec1との並べ替えが許可されている場合はvec2、 を使用std::set_intersectionして、指定した基準に従ってベクトルを並べ替え、同じ基準で並べ替えられた共通要素を取得できます。

#include <algorithm>
#include <iterator>

std::sort(vec1.begin(), vec1.end(), funny_comp);
std::sort(vec2.begin(), vec2.end(), funny_comp);
std::list<std::string> intersection;

std::set_intersection(vec1.begin(), vec1.end(),
                      vec2.begin(), vec2.end(),
                      std::back_inserter(intersection),
                      funny_comp);

whereは文字列の長さでfunny_comp比較し、文字列の長さが同じ場合は文字列の辞書式比較を実行します。

bool funny_comp(const std::string &lhs, const std::string &rhs)
{ 
   return (lhs.size()) == rhs.size()) ? lhs < rhs
                                      : lhs.size() < rhs.size();
}

ここで動作デモを参照してください。

于 2013-07-26T05:19:28.917 に答える
1

長さで並べ替え、次に語彙的に並べ替えるには、比較関数 (またはファンクター) を定義する必要があります。

struct by_len_lex { 
   bool operator()(std::string const &a, std::string const &b) { 
       if (a.length() < b.length())
           return true;
       if (a.length() > b.length())
           return false;
       return a < b;
    }
};

// ...
std::sort(strings1.begin(), strings1.end(), by_len_lex());
std::sort(strings2.begin(), strings2.end(), by_len_lex());

// find intersection:
std::set_intersection(strings1.begin(), strings1.end(), 
                      strings2.begin(), strings2.end(),
                      std::back_inserter(results),
                      by_len_lex());

並べ替え基準を定義しているため、並べ替え時と交差を行うときの両方で同じ基準を指定する必要があることに注意してください。

于 2013-07-26T05:23:00.677 に答える
1

ベクトルがソートされている場合、 std::set_intersection() を使用して、それぞれに共通する単語を見つけることができます。std::set_intersection() はアイテム数に対して O(N) 時間です。もちろん、O(N log N) です。

于 2013-07-26T05:19:17.140 に答える
1

あなたの解はO(n^2)です。これは、ベクトルの長さが n の場合、n*n 操作を行っていることを意味します。つまり、1 つのベクトルを調べ、要素ごとに他のベクトルを調べてそれを探します。

ベクトルをソートできる場合（sort関数を使用。前述のような手の込んだソートは必要ありません）、時間はO（n）です。を使用してset_intersection。それらを並べ替えることができない場合でも、それらを新しいベクトルにコピーし、それらの新しいベクトルを並べ替えます。あなたが提案しているものよりもはるかに高速です。

于 2013-07-26T05:21:31.263 に答える
0

これは最善の解決策ではないかもしれませんが、次のようなマップを使用できます。

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int main()
{
vector <string> v1{"and", "thus", "it", "has", 
                  "a", "beginning", "and", "end"};

vector <string> v2{"and" ,"therefore", "stars", 
                   "are", "beginning", "to","fall","to",
                   "their", "end"};

map <string,int> m;

auto check=[&](const string& x) { return m.find(x) != m.end() ; } ;

for_each(v1.begin(),
         v1.end(),
         [&](const string& x){ 
                m[x] =1;
            } 
         );

for_each(v2.begin(),
         v2.end(),
         [&](const string& x){ 
            if(check(x)) 
                cout<<x<<endl;
            } 
         );

}
于 2013-07-26T06:28:39.490 に答える