Comment trouver un objet avec des valeurs de champs spécifiques dans un ensemble std :: set?

Question

J'appelle une méthode qui renvoie std::set<T> const& où T est un type de classe. Ce que j'essaie de réaliser est de vérifier si l'ensemble contient un objet de type T avec des valeurs de champs spécifiques pour une assertion dans un test automatisé. Cette vérification devrait être faite pour plusieurs objets.

Voici un exemple simple: Que le type T soit Car donc un exemple set contient un tas de voitures. Maintenant, je veux trouver une voiture avec une couleur spécifique et un certain nombre de portes et une vitesse maximale spécifique dans cet ensemble. Si que la voiture est trouvée, la première assertion est vraie et la voiture suivante avec d'autres valeurs de champ doit être trouvée. Je ne suis pas autorisé à modifier l'implémentation de T. L'utilisation de Boost serait OK.

Comment le feriez-vous?

Answer 1

Cela dépend de la mise en œuvre de T. Restons avec votre exemple d'une classe Car. Supposons que la classe ressemble à ceci:

class Car { 
public: 
    Car(std::string color, unsigned int number_of_doors, 
     unsigned int top_speed); 
    // getters for all these attributes 
    // implementation of operator< as required for std::set 
}; 

Le operator< devrait commander les instances de Car basées sur tous les attributs afin de faire la recherche de tous les attributs possibles. Sinon, vous obtiendrez des résultats incorrects.

Donc, fondamentalement, vous pouvez construire une instance de voiture en utilisant seulement ces attributs. Dans ce cas, vous pouvez utiliser std::set::find et de fournir, vous êtes à la recherche d'une instance temporaire de Car avec les attributs:

car_set.find(Car("green", 4, 120)); 

Si vous souhaitez rechercher une instance de Car spécifiant qu'un sous-ensemble de ses attributs, comme tous les voitures vertes, vous pouvez utiliser std::find_if avec un prédicat personnalisé:

struct find_by_color { 
    find_by_color(const std::string & color) : color(color) {} 
    bool operator()(const Car & car) { 
     return car.color == color; 
    } 
private: 
    std::string color; 
}; 

// in your code 

std::set<Car>::iterator result = std::find_if(cars.begin(), cars.end(), 
               find_by_color("green")); 
if(result != cars.end()) { 
    // we found something 
} 
else { 
    // no match 
} 

Notez que la seconde solution a une complexité linéaire, car il ne peut pas compter sur une commande qui peuvent exister ou non pour le prédicat que vous utilisez. La première solution présente cependant une complexité logarithmique, car elle peut bénéficier de l'ordre d'un std::set. Si, comme suggéré par @Betas commenter votre question, vous voulez composer les prédicats à l'exécution, vous devrez écrire quelques classes auxiliaires pour composer différents prédicats.

Answer 2

Vous pouvez essayer opérateur majeur < (const T & a, const T & b) d'imposer un ordre sur ces attributs, donc std :: set: trouver (const T & x) retourne le premier pas moins de x .

Ej:

bool operator<(const Car& a, const Car& b) 
{ 
    return a.color<b.color || (a.color==b.color && a.doors<b.doors) || (a.color==b.color && a.doors==b.doors && a.top_speed<b.top_speed); 
} 

std::set<Car> cars; 
Car x; 
cars.find(x); 

Answer 3

Face à ces problèmes, je maintiens habituellement:

• A std::deque ou std::vector des voitures
• Pour chaque propriété que vous voulez regarder contre, un std::multiset de pointeurs vers les voitures, triés par la valeur de la propriété.

Je cache soigneusement ces conteneurs dans une classe qui me permet d'insérer des voitures. L'interface d'interrogation peut varier, mais généralement, vous bénéficiez de multiset::equal_range, std::sort et std::set_intersection.

Si vous voulez une Volvo rouge quelle que soit ... voiture, vous

1. extrait par equal_range toutes les voitures rouges, vous donnant une paire de iterator
2. extrait par equal_range toutes les voitures Volvo, vous donnant une iterator paire
3. ...
4. Trier toutes ces gammes par un prédicat commun, par exemple par adresse de pointeur
5. Appliquer à plusieurs reprises dans un set_intersectionstd::deque.

Une autre façon est de stocker les voitures dans un deque, les énumérer et de choisir celle qui répond à toutes vos propriétés, en utilisant std::find.Cela peut cependant avoir une plus grande complexité (cela dépend du nombre de voitures rouges que vous possédez).

Answer 4

std :: set vous permet de fournir votre propre fonction de comparaison, comme dans

template < class Key, class Compare = less<Key>, 
     class Allocator = allocator<Key> > class set; 

comparer Seules les valeurs que vous aimez et il va agir comme si les objets avec ces valeurs sont =. Notez que vous aurez probablement besoin d'un multiset pour cela.

Ce serait le moyen de le faire si vous vous souciez vraiment des performances de journalisation.

Answer 5

Vous voulez std::find_if, avec un objet de fonction sous-jacente qui vérifie les propriétés qui vous intéressent Il pourrait ressembler à ceci:.

struct FindCar { 
    FindCar(Colour colour, int doors, double top_speed) : 
     colour(colour), doors(doors), top_speed(top_speed) {} 

    bool operator()(Car const & car) const { 
     return car.colour == colour 
      && car.doors == doors 
      && car.top_speed == top_speed; 
    } 

    Colour colour; 
    int doors; 
    double top_speed; 
}; 

std::set<Car> const & cars = get_a_set_of_cars(); 
std::set<Car>::const_iterator my_car = 
    std::find_if(cars.begin(), cars.end(), FindCar(Red, 5, 113)); 

Dans C++ 0x, vous pouvez remplacer le " FindCar "avec un lambda pour rendre le code un peu plus court.