1

2

假设我使用了过滤器，它将从这些字符串的前 3 位数字中生成 substr（例如，我刚刚完成了这个函数）。结果我需要得到那个交叉点：

现在我的代码看起来像：

QSharedPointer<QStringList> Intersection_Op::compute(QSharedPointer<QStringList> leftList,
                                                     QSharedPointer<QStringList> rightList,
                                                     QPair<int, int> filters)
{
    if (!leftList or !rightList)
        return QSharedPointer<QStringList>( nullptr );
    
    std::sort( leftList->begin(), leftList->end() );
    std::sort( rightList->begin(), rightList->end() );

    // std::string getCheckBody( const QString* str, QPair<int, int> filters )
    
    auto leftStdList = new std::list<QString>( leftList );
    auto rightStdList = new std::list<QString>( rightList );
    auto result = QSharedPointer<QStringList>( new QStringList() );

    std::set_intersection(leftStdList->begin(), leftStdList->end(),
                          rightStdList->begin(), rightStdList->end(), std::back_inserter( *result ),
                              [=] (const QString& one, const QString& two) -> bool {
         auto o = getCheckBody( one, filters );
         auto t = getCheckBody( two, filters );

         // got this condition from another thread here
         return  ( o.size() == t.size() )
                 ? (o < t)
                 : ( o.size() < t.size() );
    });

    delete leftStdList;
    delete rightStdList;
    
    return result;
}

现在我得到了这个结果：

111111
222333

首先，忽略第一个列表中具有相同数据的其他值，其次，忽略第二个列表。第二个可以通过使用切换列表复制此功能来解决。但是我怎样才能将我需要的所有值包含在一个列表中（至少）？

我之前从未在算法中使用过比较函数，特别是对于字符串比较，我怀疑我为此使用了错误的条件。也许我使用了错误的方法（std::set_intersection）？

关于数据大小，通常是 ~100k 字符串列表，所以我真的在寻找如何优化这个任务。

你能帮我找到解决办法吗？任何人都可以为这项任务提供一些建议吗？

谢谢

标签： c++algorithmqtc++11std

std::set_intersection是错误的方法。

如果m在[first1, last1)和n中找到某个元素[first2, last2)，则第一个std::min(m, n)元素将从第一个范围复制到目标范围。

你有两次“111...”，一次在另一个，“222...”一次。

你需要类似的东西

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt my_intersection(InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,
                         OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
        auto range1 = std::equal_range(first1, last1, *first2, comp);
        auto range2 = std::equal_range(first2, last2, *first1, comp);

        d_first = std::copy(range1.first, range1.second, d_first);
        d_first = std::copy(range2.first, range2.second, d_first);

        first1 = range1.second;
        first2 = range2.second;
    }
    return d_first;
}

请注意，您需要按比较函数对输入进行排序。如果<给您的 lambda 提供不同的顺序，则您的代码格式不正确，例如，如果您想按后缀而不是前缀进行比较。

c++ - Qt C++11字符串通过子字符串比较列出交集

问题描述

1

2

解决方案

推荐阅读