1

我试图在 std::string 的 2 个向量之间找到常用词。我想将它们放入按长度排序的排序列表中，然后按字母顺序对每个长度的单词进行排序。我需要使用 stl 函数和仿函数。

我的想法：使用 for_each 遍历第一个向量，对于每个单词，使用仿函数将其与另一个向量进行比较（如果常见，则附加到仿函数中的列表）。那么结果列表中将只有常用词。这是我卡住的地方，我知道如何按字母顺序排序，但是如何按长度对它们进行排序，然后按字母顺序对相同长度的块进行排序？我环顾了stl，但没有找到我需要的东西。或者，我只是想错了。有任何想法吗？

例子：

vec1: "and", "thus", "it", "has", "a", "beginning", "and", "end"

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);

wherefunny_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

Your solution is O(n^2). This means if the length of the vectors is n, you're doing n*n operations: going over one vector, and for each element, going over the other vector to look for it.

If you can sort the vectors (using the sort function. No need for fancy sort like you mentioned), the time is O(n). using set_intersection. Even if you can't sort them - copy them into new vectors and sort those new vectors. It's sill much faster than what you're proposing.

于 2013-07-26T05:21:31.263 回答
1

To sort by length, then lexically, you need to define a comparison function (or functor) to do that:

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());

Note that since you're defining the sort criteria, you need to specify the same criteria both when sorting and when doing the intersection.

于 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 回答
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 回答