nombre de correspondances dans deux séquences avec STL

Question

OK, voici encore une autre question de la "Comment faire mieux en STL?" séries.

Nous avons deux plages, désignées par first1, last1 et first2. Nous voulons trouver le nombre de différentes années i de [0, last1-Premier1] tel que *(first1 + i) == *(first2 + i)

Par exemple:

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

Pour ces deux gammes, la réponse est 4.

Y at-il un bon moyen STL de le faire? Je veux dire de préférence sans aucun manuel pour, tandis que etc. Merci!

Answer 1

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

MISE À JOUR

Konrad a souligné dans les commentaires ci-dessous que cela repose sur une conversion implicite légèrement infâmes de bool à int. Bien que cela soit tout à fait légal, il peut être évité ainsi:

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

Vous pouvez utiliser std::transform sur les deux plages avec un foncteur binaire avec état qui incrémente un compteur sur la correspondance. Tenir mon nez, car il garde son état en tant que membre statique. Vous pouvez éviter le "retour à la source" que @Johannes a soulevé en utilisant equal plutôt que transform mais l'état par static est encore en désordre ici (dans mon code de toute façon).

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

Answer 3

Vous pouvez abuser du std :: algorithme de décalage (et la fonction lambda):

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

Je suis venu avec la solution suivante , insipired par fonctions zip() des langues fonctionnelles. Il compile et fonctionne bien, mais à mon humble avis, c'est probablement l'utilisation la plus dangereuse des paires d'itérateur que j'ai jamais rencontrées, donc je ne recommande pas de l'utiliser dans le code de production tel quel.

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