количество совпадений в двух последовательностях с STL

Question

Хорошо, вот еще один вопрос "Как это сделать лучше в STL?"series.

У нас есть два диапазона, обозначенных first1, last1 и first2.Мы хотим найти количество различных значений i из [0, last1-first1], таких что *(first1 + i) == *(first2 + i)

Например:

{a, b, c, d, d, b, c, a}
{a, a, b, c, d, c, c, a}
 ^           ^     ^  ^ 

Для этих двух диапазонов ответ равен 4.

Есть ли хороший STL способ сделать это?Я имею в виду, желательно без какого-либо руководства для, в то время как и т. Д. Спасибо!

Answer 1

std::inner_product(first1, last1, first2, 0, std::plus<T>(), std::equal_to<T>());

UPDATE

Конрад указал в комментариях ниже, что это основывается на слегка гнусном неявном преобразовании из bool в int. Хотя это абсолютно законно, этого можно избежать, таким образом:

template <typename T>
int match(const T &a, const T &b) { return (a == b) ? 1 : 0; }

std::inner_product(first1, last1, first2, 0, std::plus<T>(), match<T>);

Answer 2

Я пришел к следующему решению, вдохновленному функциями zip() функциональных языков.Он компилируется и работает нормально, но, IMHO, это, вероятно, наиболее небезопасное использование пар итераторов begin() & end(), с которыми я когда-либо сталкивался, поэтому я не рекомендую использовать его в рабочем коде как есть.

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <iostream>
#include <vector>

namespace {

        // Iterator for pairs of items at same position in two sequences.
    template<typename Lhs, typename Rhs>
    class zipper
    {
            // Keep track of position in input sequences.
        Lhs myLhs;
        Rhs myRhs;
    public:
            // Minimal assumptions on iterator types `Lhs` and `Rhs`.
        typedef std::input_iterator_tag iterator_category;
        typedef std::pair<
            typename std::iterator_traits<Lhs>::value_type,
            typename std::iterator_traits<Rhs>::value_type
        > value_type;
        typedef value_type& reference;
        typedef value_type* pointer;
        typedef std::ptrdiff_t difference_type;

        zipper ( Lhs lhs, Rhs rhs )
            : myLhs(lhs), myRhs(rhs)
        {}
        value_type operator* () const {
            return (value_type(*myLhs, *myRhs));
        }
        bool operator== ( const zipper<Lhs,Rhs>& other ) const {
            return ((myLhs == other.myLhs) && (myRhs == other.myRhs));
        }
        bool operator!= ( const zipper<Lhs,Rhs>& other ) const {
            return ((myLhs != other.myLhs) || (myRhs != other.myRhs));
        }
        zipper<Lhs,Rhs>& operator++ () {
            ++myLhs, ++myRhs; return (*this);
        }
        zipper<Lhs,Rhs> operator++ ( int ) {
            const zipper<Lhs,Rhs> old(*this);
            ++(*this); return (old);
        }
    };

       // Shorthand "a la" std::make_pair().
    template<typename Lhs, typename Rhs>
    zipper<Lhs,Rhs> make_zipper ( Lhs lhs, Rhs rhs )
    {
        return (zipper<Lhs,Rhs>(lhs, rhs));
    }

        // Check for equal items in a pair.
    template<typename T> struct equal_pair
    {
        bool operator() ( const std::pair<T,T>& x ) const
        {
            return (x.first == x.second);
        }
    };

}

int main ( int, char ** )
{
        // Test data.
    const std::string lhs("abcddbca");
    const std::string rhs("aabcdcca");

        // Count how many pairs are equal.
    const std::size_t equal_pairs = std::count_if(
        make_zipper(lhs.begin(),rhs.begin()),
        make_zipper(lhs.end()  ,rhs.end()  ), equal_pair<char>());

        // Outputs "There are 4 equal pairs.".
    std::cout
        << "There are " << equal_pairs << " equal pairs." << std::endl;
}

Answer 3

Вы можете использовать алгоритм std :: mismatch (и лямбда-функцию):

const int lista[] = { 1, 2, 3, 4, 4, 2, 3, 1 };
const int listb[] = { 1, 1, 2, 3, 4, 3, 3, 1 };
int count = 0;

std::mismatch(lista, lista+8, listb, [&count](int a, int b)->bool
{
    if (a == b) ++count;
    return true;
});

std::cout << count << '\n';

Answer 4

Вы можете использовать std :: transform в двух диапазонах с двоичным функтором с состоянием, который увеличивает счетчик при совпадении.

Держу мой нос, так как это сохраняет состояние как статический член. Вы можете избежать «обратной записи в источник», которую @Johannes поднял, используя equal вместо transform, но сохранение состояния через static все еще здесь грязно (в любом случае в моем коде).

#include <vector>
#include <algorithm>

class match {
public:
    char operator()(const char& lhs, const char& rhs)
    {
        if (lhs == rhs)
        {
            ++count;
        }
        return rhs;
    }
    static size_t count;
};

size_t match::count(0);

class matchEqual {
public:
    bool operator()(const char& lhs, const char& rhs)
    {
        if (lhs == rhs)
        {
            ++count;
        }
        return false;
    }
    static size_t count;
};

size_t matchEqual::count(0);

int main()
{

    vector<char> vec1;
    vec1.push_back('a');
    vec1.push_back('b');
    vec1.push_back('c');
    vec1.push_back('d');
    vec1.push_back('d');
    vec1.push_back('b');
    vec1.push_back('c');
    vec1.push_back('a');

    vector<char> vec2;
    vec2.push_back('a');
    vec2.push_back('a');
    vec2.push_back('b');
    vec2.push_back('c');
    vec2.push_back('d');
    vec2.push_back('c');
    vec2.push_back('c');
    vec2.push_back('a');

    transform(vec1.begin(), vec1.end(), vec2.begin(), vec2.begin(), match());

    size_t matches = match::count;

    equal(vec1.begin(), vec1.end(), vec2.begin(), matchEqual());
    matches = matchEqual::count;

    return 0;
};