The number of matches in two sequences with STL

Question

OK, here is another question about "How to do it better in STL?" series.

We have two ranges denoted by first1, last1 and first2. We want to find the number of different s from [0, last1-first1] in such a way that*(first1 + i) == *(first2 + i)

For instance:

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

For these two ranges, the answer is 4.

Is there a good STL way? I mean it is preferable without any manuals, etc. Thank!

Answer 1

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

UPDATE

Conrad noted in the comments below that this depends on a slightly vile implicit conversion from boolto int. Although this is completely legal, this can be avoided:

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 , .

Holding my nose, as this saves the state as a static member. You can avoid the "write back to source" that @Johannes raised using equal, rather than transform, but the state of using staticis still confused here (in my code).

#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;
};