Recherche de données de champ binaire dans un conteneur multi-index Boost

Question

Je recherche la solution optimale pour extraire des objets basés sur des bits de base à partir d'un conteneur multi-index. Pour simplifier, les données sont:

enum Bit 
{ 
    b0 = 1, 
    b1 = 2, 
    b2 = 4 
}; 

struct Item 
{ 
    int field; // contains Bit values 
    int info; 
}; 

Pour autant que je sais qu'il pourrait y avoir 2 possibilités:

1. Utilisez un prédicat personnalisé dans l'appel de equal_range (Cet exemple ne fonctionne pas parce que je ne savoir comment définir le prédicat):

   struct MyTag; 
   
   using boost::multi_index_container; 
   using namespace boost::multi_index; 
   
   typedef composite_key<Item, 
       member<Item, int, &Item::field>, 
       member<Item, int, &Item::info> > CompositeKey; 
   typedef hashed_non_unique< tag<MyTag>, CompositeKey> Index1; 
   typedef boost::multi_index_container<Item, indexed_by<Index1> > Container; 
   
   struct Predicate: public Index1::pred_type 
   { 
       /// what to put here? 
   }; 
   
   void f() 
   { 
       Item item1 = { int(b0 | b1), 123}; 
       Item item2 = { int(b1 | b2), 123}; 
       Item item3 = { int(b2), 123}; 
   
       Container c; 
       c.insert(item1); 
       c.insert(item2); 
       c.insert(item3); 
   
       auto result = c.get<MyTag>().equal_range(boost::make_tuple(int(b2), 123), Index1::hash_type(), Predicate()); 
       for(auto i = result.first; i != result.second; ++i) 
       { 
        std::cout << i->field << ' '; 
        // expect item2 and item3 
       } 
   } 
   

2. Ajouter accesseurs dans l'article et les index dans le conteneur multi-index pour chaque bit de l'énumération:

   struct Item 
   { 
       int field; 
       int info; 
   
       bool isB0() const { return (field & b0) != 0; } 
       bool isB1() const { return (field & b1) != 0; } 
       bool isB2() const { return (field & b2) != 0; } 
   }; 
   
   
   struct MyTag1; 
   struct MyTag2; 
   struct MyTag3; 
   
   using boost::multi_index_container; 
   using namespace boost::multi_index; 
   
   typedef composite_key<Item, 
       const_mem_fun<Item, bool, &Item::isB0>, 
       member<Item, int, &Item::info> > CompositeKeyB0; 
   typedef composite_key<Item, 
       const_mem_fun<Item, bool, &Item::isB1>, 
       member<Item, int, &Item::info> > CompositeKeyB1; 
   typedef composite_key<Item, 
       const_mem_fun<Item, bool, &Item::isB2>, 
       member<Item, int, &Item::info> > CompositeKeyB2; 
   typedef hashed_non_unique< tag<MyTag1>, CompositeKeyB0> Index1; 
   typedef hashed_non_unique< tag<MyTag2>, CompositeKeyB1> Index2; 
   typedef hashed_non_unique< tag<MyTag3>, CompositeKeyB2> Index3; 
   typedef boost::multi_index_container<Item, indexed_by<Index1, Index2, Index3> > Container; 
   
   void f() 
   { 
       Item item1 = { int(b0 | b1), 123}; 
       Item item2 = { int(b1 | b2), 123}; 
       Item item3 = { int(b2), 123}; 
   
       Container c; 
       c.insert(item1); 
       c.insert(item2); 
       c.insert(item3); 
   
       auto result = c.get<MyTag2>().equal_range(boost::make_tuple(true, 123)); 
       for(auto i = result.first; i != result.second; ++i) 
       { 
        std::cout << i->field << ' '; 
        // expect item2 and item3 
       } 
   } 
   

Answer 1

L'option 2 est parfaitement bien, et en fait votre solution fonctionne comme prévu. Comme pour l'option 1, il n'y a aucun moyen de le faire fonctionner, peu importe comment votre classe Predicate, une explication suit: un index hashed non-unique groupes (ce qui signifie emballe ensemble) éléments selon un critère d'équivalence , qui dans votre cas a la même valeur pour les membres de données field et info. Oublions info pendant un certain temps en prétendant tous les éléments ont la même valeur pour elle et se concentrer sur field: les six classes d'équivalence (grappes d'éléments) sont alors

0, 1, 2, 3, 4, 5, 6, 7

qui sont simplement les différentes valeurs que les trois bits 0, 1 et 2 du field peuvent prendre de manière combinée (ces groupes ne semblent pas nécessairement dans l'ordre indiqué ci-dessus).Maintenant, si vous essayez de faire une equal_range qui récupère tous les éléments avec b2 ensemble ce que vous voulez pour l'opération de restituer les éléments de ces groupes représentés dans lettre gras ci-dessous:

0, 1, , , 4, 5, 6 ,

qui, en général, ne sont pas disposés ensemble , donc il n'y a aucun moyen equal_range peut renvoyer un couple d'itérateurs allant sur ceux-ci et seulement ces éléments.

Answer 2

Je pense que la façon de penser à ce sujet est:

« comment pourrais-je créer ces indices sans coup de pouce? »

Ce serait quelque chose comme ceci:

#include <unordered_map> 
#include <list> 
#include <functional> 
#include <iostream> 

enum Bit 
{ 
    b0 = 1, 
    b1 = 2, 
    b2 = 4 
}; 

struct Item 
{ 
    int field; 
    int info; 

    bool isB0() const { return (field & b0) != 0; } 
    bool isB1() const { return (field & b1) != 0; } 
    bool isB2() const { return (field & b2) != 0; } 
}; 

template<int bit> 
struct ItemHash 
{ 
    bool operator()(const Item& item) const { 
    auto accum = std::hash<int>()(item.info); 
    if ((item.field & bit) == bit) 
     accum += 1234567; 
    return accum; 
    } 
}; 

template<int bit> 
    struct ItemEqual 
    { 
    bool operator()(const Item& l, const Item& r) const 
    { 
     auto lt = std::make_tuple((l.field & bit) == bit, l.info); 
     auto rt = std::make_tuple((r.field & bit) == bit, r.info); 
     return lt == rt; 
    } 
    }; 

struct Items 
{ 
    Item& insert(Item item) 
    { 
    // store object 
    auto i = _storage.insert(_storage.end(), item); 

    // update indeces 
    _by_b0.emplace(item, *i); 
    _by_b1.emplace(item, *i); 
    _by_b2.emplace(item, *i); 

    _by_b2_and_b1.emplace(item, *i); 

    return *i; 
    }; 



    // object storage 
    std::list<Item> _storage; 

    // indexes we want to keep 
    std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b0>, ItemEqual<b0> > _by_b0; 
    std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b1>, ItemEqual<b1> > _by_b1; 
    std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b2>, ItemEqual<b2> > _by_b2; 

    // multiple bits? 
    std::unordered_map<Item, std::reference_wrapper<Item>, ItemHash<b2|b1>, ItemEqual<b2|b1> > _by_b2_and_b1; 
}; 


int main() 
{ 
    Item item1 = { int(b0 | b1), 123}; 
    Item item2 = { int(b1 | b2), 123}; 
    Item item3 = { int(b2), 123}; 

    Items c; 
    c.insert(item1); 
    c.insert(item2); 
    c.insert(item3); 

    auto result = c._by_b2.equal_range(Item { b2, 123 }); 
    for(auto i = result.first; i != result.second; ++i) 
    { 
     std::cout << i->second.get().field << ' ' << i->second.get().info << std::endl; 
     // expect item2 and item3 
    } 
} 

En regardant cela, nous aimerions commencer à se rendre compte que ces bits field sont des attributs réellement. Voulons-nous vraiment créer un index sur chaque combinaison d'attributs? Cela va-t-il vraiment être plus efficace et plus facile à maintenir qu'en stockant simplement nos Item dans un vector, et en utilisant un prédicat dans une boucle for?

par exemple:

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <tuple> 

enum Bit 
{ 
    b0 = 1, 
    b1 = 2, 
    b2 = 4 
}; 

struct Item 
{ 
    int field; 
    int info; 

    bool isB0() const { return (field & b0) != 0; } 
    bool isB1() const { return (field & b1) != 0; } 
    bool isB2() const { return (field & b2) != 0; } 
}; 

struct matches_bits_and_info { 

    constexpr matches_bits_and_info(int bits, int info) : _bits(bits), _info(info) {} 

    bool operator()(const Item& item) const { 
     return std::make_tuple((item.field & _bits) , item.info) 
     == std::tie(_bits, _info); 
    } 
    int _bits, _info; 
}; 

int main() 
{ 
    std::vector<Item> c; 
    c.push_back({b0 | b1, 123}); 
    c.push_back({b0 | b2, 123}); 
    c.push_back({b2, 123}); 

    for (auto& item : c) { 
     if (matches_bits_and_info(b2, 123)(item)) { 
      std::cout << item.field << ' ' << item.info << std::endl; 
     } 
    } 

} 

résultats attendus:

5 123 
4 123 

Pour que cela soit moins efficace que la solution multi-index contenant (ou une solution roulées à la main), l'ensemble de données devra être massive.

Answer 3

Une alternative à 1 peut être envisagé de prendre en compte que les valeurs possibles de l'organe field sont en fait pas beaucoup (8), ce qui est de ramasser un par un les field valeurs correspondant à un bit donné , voir for_each_value dans l'exemple suivant:

Live Coliru Demo

#include <algorithm> 
#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/multi_index/member.hpp> 
#include <boost/multi_index/composite_key.hpp> 

enum Bit 
{ 
    b0 = 1, 
    b1 = 2, 
    b2 = 4 
}; 

struct Item 
{ 
    int field; 
    int info; 
}; 

struct MyTag; 

using boost::multi_index_container; 
using namespace boost::multi_index; 

typedef composite_key< 
    Item, 
    member<Item, int, &Item::field>, 
    member<Item, int, &Item::info> > CompositeKey; 
typedef hashed_non_unique< tag<MyTag>, CompositeKey> Index1; 
typedef boost::multi_index_container<Item, indexed_by<Index1> > Container; 

template<typename F> 
F for_each_value(const Container& c,Bit b,int info,F f) 
{ 
    for(auto field:{0,1,2,3,4,5,6,7}){ 
    if(field&b){ 
     auto r=c.equal_range(std::make_tuple(field,info)); 
     std::for_each(r.first,r.second,f); 
    } 
    } 
    return f; 
} 

#include <iostream> 

int main() 
{ 
    Item item1 = { int(b0 | b1), 123}; 
    Item item2 = { int(b1 | b2), 123}; 
    Item item3 = { int(b2), 123}; 

    Container c; 
    c.insert(item1); 
    c.insert(item2); 
    c.insert(item3); 

    for_each_value(c,b2,123,[](const Item& i){ 
    std::cout << i.field << ' '; 
    }); 
} 

Sortie

 
4 6