Comment écrire des opérateurs de surcharge pour les conteneurs STL et les fonctions alogrithm?

Question

Par exemple, je veux écrire des fonctions de surcharge pour set_difference qui compare le type std::set<point>

class myIter : public std::iterator<std::input_iterator_tag, int> { 
public: 
    myIter(int n) : num(n){} 
    myIter(const myIter & n) : num(n.num){} 
    int & operator *(){return num;} 
    myIter & operator ++(){++num; return *this;} 
    bool operator !=(const myIter & n){return n.num != num;} 
private: 
    int num; 
}; 

struct point 
{ 
    point(int X, int Y):x(X), y(Y){} 
    int x; 
    int y; 
} 

int main() 
{ 
    set <point> myset; 
    myset.insert(point(1, 1); 
    myset.insert(point(3, 2); 
    myset.insert(point(5, 3); 

    //find the missing elements in set for `point.x` using `set_difference` 

    std::set<int> missing; 

    std::set_difference(myIter(myset.begin()->x+1), myIter(myset.rbegin()->x), 
    myset.begin(), myset.end(), std::insert_iterator<std::set<int>>(missing, missing.begin())); 

} 

Après avoir appliqué les std::set_difference sur point.x les variables du set<int> missing doit être:

missing[0] {2} 
missing[1] {4} 

Comment puis-je savoir comment écrire les opérateurs de surcharge pour l'opération?

Answer 1

Tout d'abord, std::set<point> exige que point est moins que comparable. Vous pouvez définir operator< pour point, ou fournir un objet de fonction distincte qui fait la comparaison en tant que second paramètre de modèle std::set<point,MyCompare>.

Une fois que vous avez fait vos éléments dans l'ensemble, vous pouvez utiliser set_difference. Il est à noter que set_difference ne nécessite pas réellement d'utiliser std::set pour votre saisie --- vous pourriez simplement utiliser un vecteur et ainsi éviter d'avoir à fournir la fonction de comparaison.

Pour utiliser set_difference, vous devrez veiller à ce que les value_type s des deux gammes de iterator sont les mêmes, vous aurez donc besoin d'une autre enveloppe de iterator qui retourne juste la partie x des point valeurs pour la deuxième plage.

std::set_difference(myIter(myset.begin()->x+1), myIter(myset.rbegin()->x), 
    extractXIter(myset.begin()), extractXIter(myset.end()), 
    std::insert_iterator<std::set<int>>(missing, missing.begin())); 

Answer 2

IIUC, vous êtes après la mise en œuvre operator<() pour votre type, car il est utilisé par plusieurs types et algorithmes de la bibliothèque standard:

struct point 
{ 
    point(int X, int Y):x(X), y(Y){} 
    int x; 
    int y; 
}; 

inline bool operator<(const point& lhs, const point& rhs) 
{ 
    if(lhs.x < rhs.x) return true; 
    if(lhs.x > rhs.x) return false; 
    return lhs.y < rhs.y; 
} 

C'est une façon tout à fait naïf de juger quel point est « plus petit ». Vous pourriez vouloir améliorer l'algorithme, mais la mécanique syntaxique reste la même.

---

Notez que, une fois que vous avez défini p1 < p2, les utilisateurs de votre type habituellement attendent p1 > p2 (et p1 <= p2 etc.) pour travailler aussi bien. Comme il est trivial, il ne fait pas de mal à fournir le reste des opérateurs de comparaison:

inline bool operator> (const point& lhs, const point& rhs) {return rhs < lhs;} 
inline bool operator<=(const point& lhs, const point& rhs) {return !(lhs > rhs);} 
inline bool operator>=(const point& lhs, const point& rhs) {return !(lhs < rhs);} 
inline bool operator==(const point& lhs, const point& rhs) 
{ 
    return lhs.x < rhs.x && lhs.y == rhs.y; 
} 
inline bool operator!=(const point& lhs, const point& rhs) {return !(lhs==rhs);} 

Answer 3

(Ma deuxième tentative de la réponse.)

Ceci est plutôt une élaboration de la réponse de Anthony Williams.

Les deux itérateurs que vous avez besoin sont disponibles dans les bibliothèques Boost (votre propre myIter est une fonctionnalité qui manque peut rendre votre code uncompilable avec d'autres compilateurs).

#include <set> 
#include <algorithm> 
#include <iostream> 
#include <boost/iterator/counting_iterator.hpp> 
#include <boost/iterator/transform_iterator.hpp> 
#include <boost/mem_fn.hpp> 

struct point 
{ 
    point(int X, int Y):x(X), y(Y){} 
    int x; 
    int y; 
}; 

bool operator< (const point& a, const point& b) 
{ 
    return a.x < b.x || (a.x == b.x && a.y < b.y); 
} 

int main() 
{ 
    std::set <point> myset; 
    myset.insert(point(1, 1)); 
    myset.insert(point(3, 2)); 
    myset.insert(point(5, 3)); 

    //find the missing elements in set for `point.x` using `set_difference` 
    std::set<int> missing; 
    using namespace boost; 
    std::set_difference(
    counting_iterator<int>(myset.begin()->x+1), counting_iterator<int>(myset.rbegin()->x), 
    make_transform_iterator(myset.begin(), mem_fn(&point::x)), 
    make_transform_iterator(myset.end(), mem_fn(&point::x)), 
    std::inserter(missing, missing.begin())); 
    std::copy(missing.begin(), missing.end(), std::ostream_iterator<int>(std::cout, " ")); 
} 

Points d'intérêt:

• point a besoin d'être "moins que" comparable, si vous voulez les stocker dans un set
• boost::counting_iterator est un meilleur myIter
• boost::transform_iterator permet vous pouvez appliquer une fonction à la valeur lors de la déréférence. En combinaison avec boost::mem_fn, il obtient le membre Point::x lorsque l'itérateur est déréférencé.
• utiliser la fonction d'aide std::inserter pour obtenir les arguments de modèle déduisent
• les résultats ne doivent pas être stockés dans un set (ni ne l'entrée doivent provenir d'un set, tant que la plage est triée par rapport . au prédicat utilisé - comparer ici l'élément x