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

Question

我在字符串列表比较方面遇到了一些问题。我需要达到良好的性能，所以我为此搜索了几种方法，现在我尝试使用 std::set_intersection 来实现。

主要问题是我需要通过子字符串比较这些，例如我有这个列表：

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 字符串列表，所以我真的在寻找如何优化这个任务。

你能帮我找到解决办法吗？谁能为这项任务提供一些建议？

谢谢

Answer 1

std::set_intersection 是错误的方法。

If some element is found m times in [first1, last1) and n times in [first2, last2), the first std::min(m, n) elements will be copied from the first range to the destination range.

你在一个中有两次“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 给出了不同的顺序，则您的代码格式错误，例如如果你想通过后缀而不是前缀进行比较。

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

Qt C++11 string lists intersection via substring comparation

c++

algorithm

qt

std

c++11

1

2