Une carte STL peut-elle être utilisée avec des clés de différentes tailles

Question

Une carte STL peut-elle être utilisée pour des clés de tailles différentes?

Je n'ai pas de code pour cela. J'essaie toujours de comprendre si cela peut être fait et d'où ma question. (Je suis le type qui peut passer trop de temps sur un problème impossible, j'espère apprendre de votre sagesse).

Je travaille sur une table de consultation qui a essentiellement deux clés. Une clé de type numérique et une clé secondaire spécifique de type.

Par exemple, la première clé de niveau est une énumération:

enum key_type { 
    E_ERROR = 0, 
    E_INT = 1, 
    E_CHAR = 2, 
    E_STR = 3, 
}; // Yes I know you don't HAVE to specify the values for the enumeration 

Et puis les touches secondaires dépendent du key_type. La clé secondaire pour un E_INT est un entier, pour un E_CHAR est un personnage, etc.

Key: E_INT 
2ndary Key Examples: 1, 2, 3, 4 

Key: E_CHAR 
2ndary Key Examples: 'a', 'b', 'c', 'd' 

Key: E_STR 
2ndary Key Examples: "abc", "xyz", "pdq", "jrr" 

Ma première réaction a été d'en faire un tableau de pointeurs de carte. La clé de premier niveau est utilisée comme index dans le tableau. Où l'index du tableau pointe sur une carte qui prend en charge le type de clé secondaire.

+--------+ 
| E_INT |------------------------------>+------------------+ 
+--------+        | MAP with INT key | 
| E_CHAR |---------------\    +------------------+ 
+--------+    \ 
| E_STR |------\   \---->+-------------------+ 
+--------+  \    | MAP with CHAR key | 
        \    +-------------------+ 
        \ 
        \------>+------------------+ 
          | MAP with STR key | 
          +------------------+ 

Je sais je peux obtenir ce qui précède pour travailler, mais je pensais que je pouvais combiner les deux clés et une carte unique, avec un algorithme sur mesure sort() pour traiter les clés combinées.

Suis-je complètement fou de penser à cela? Si ce n'est pas fou, avez-vous des suggestions sur la façon de procéder avec cela?

Du haut de ma tête, je dois faire une classe héritée de la clé où la classe de base fournit une fonction virtuelle pure pour la méthode de tri, et ont hérité des cours clés pour la E_INT, E_CHAR et E_STR, qui mettent en œuvre la méthode sort() pour leur utilisation. Ensuite, j'utiliserais la classe de clé de base comme clé pour la carte.

Commentaires?

---

EDIT 8/13/2010

J'ai essayé quelques solutions posées, ainsi que mes pensées originales. Je continue à frapper des problèmes. Je suis tombé sur un autre article de stackoverflow qui a mentionné type erasure qui pourrait faire l'affaire pour mes différentes clés.

---

EDIT 8/16/2010

Ajout d'une réponse dans la section de réponse ci-dessous qui montre la solution à code I mis en œuvre.

Answer 1

std::map requiert strict weak ordering pour les clés. Si vous pouvez appliquer un ordre unique sur vos différents types de clés avec un comparateur personnalisé, cela ne devrait pas poser de problème.

Answer 2

Je pense que votre approche est correcte en termes de ce que vous feriez avec les touches personnalisées. Cela dit, si vous pouvez épargner la surcharge d'avoir N cartes par rapport à une carte avec une clé personnalisée, je dirais de le faire car c'est trivial et rapide. Vous pouvez même charger les cartes paresseux et simplement masquer l'implémentation derrière une autre classe.

EDIT: votre comparateur personnalisé devrait aussi être simple. Vous pouvez commander d'abord enum en premier, et ensuite pour les clés avec la même valeur enum (CHAR, INT, STR, etc.), vous devez ensuite comparer par la valeur. Cela garantirait la commande requise par std :: map.

Answer 3

devrez-vous un jour trier toutes les listes? Si c'est le cas, votre approche sera pénible lorsque vous essaierez d'accéder à des éléments.

Une façon stupide de le faire est de créer simplement un type d'union et d'une fonction de comparaison sur l'union:

typedef struct IntRecord { 
    key_type key; 
    int record; 
}; 

typedef struct CharRecord { 
    key_type key; 
    char record; 
}; 

typedef struct StrRecord { 
    key_type key; 
    const char * record; 
}; 

typedef struct Base { 
    key_type key; 
}; 
typedef union Record { 
    Base b; 
    IntRecord i; 
    CharRecord c; 
    StrRecord s; 
}; 

maintenant votre fonction de comparaison peut regarder la b.key de chaque enregistrement pour voir quel type devrait être utilisé.

Answer 4

Vous devrez envelopper vos deux clés dans un seul objet. Votre nouvelle classe devra également être comparable. par exemple:

struct myKey 
{ 
    int key1; 
    std::string key2; 

    bool operator<(const myKey&) const; 
}; 

Il n'y a rien d'arrêter key1 et key2 étant des pointeurs (intelligents). Une fois qu'un objet (comme myKey) est comparable via l'opérateur <, il peut être utilisé dans une carte.

Answer 5

Vous pouvez implémenter une classe pour la clé qui implémente un opérateur <, quelque chose comme ça (non testé):

struct UnionMapKey { 
    int key_type; 
    union { 
     Error *err; // maybe pointer because complex types can't be in C unions 
     int i; 
     char c; 
     string *s; // pointer because complex types can't be in C unions 
    }; 
    UnionMapKey(const string &stringContent) { key_type = E_STR; s = new string(stringContent); } 
    // other constructor overrides 
    bool operator<(const UnionMapKey &rhs) { 
     if (key_type != rhs.key_type) return key_type < rhs.key_type; 
     if (key_type == E_ERROR) return err < rhs.err; 
     // etc. 
    } 
    ~UnionMapKey() { 
     if (key_type == E_STR) delete s; 
    } 
}; 

Vous avez probablement besoin aussi un constructeur de copie, mais je pense que vous avez l'idée. Une fois que vous avez repassé les rides, cela fonctionnera bien comme une clé de la carte. Honnêtement, votre solution de tableaux de cartes est probablement beaucoup plus simple si cela fonctionne pour vous.

Answer 6

Bien qu'il y ait eu de nombreuses solutions présentées ... aucun d'entre eux est aussi élégant que:

typedef boost::variant<int,char,std::string> key_type; 

typedef std::map<key_type, value_type> map_type; 

Eh oui, voilà tout. Un boost::variant est naturellement classé d'abord par type et second (lorsque les types sont égaux) par les valeurs qu'ils portent (s'ils peuvent être comparés).

Je défie quiconque de trouver une solution plus simple;)

Answer 7

Si vous utilisez boost :: Tout en combinaison avec un opérateur de comparaison comme dans http://www.sgi.com/tech/stl/Map.html. Vous devriez être en mesure d'utiliser plusieurs types de clés, à condition que votre opérateur puisse les commander. Si vous utilisez boost :: Any, ils occuperont plus d'espace que la clé elle-même, mais le reste des solutions présentées ici imposera également un peu de surcharge.

Answer 8

La solution I Mis en œuvre

---

Le consensus était que cela pourrait se faire. J'ai en quelque sorte adapté le concept type erasure, avec les suggestions des autres ci-dessus. J'ai quelque chose qui fonctionne maintenant. La clé de la carte doit être un objet qui a un pointeur vers un objet clé polymorphe.

J'ai essayé d'utiliser uniquement l'objet de base comme type de clé, mais lorsque la carte crée sa copie de la clé, il semble qu'elle ne faisait que copier la classe de base.

Donc je suis passé naïvement à un pointeur (key_base_c *). Cependant, ceci a juste fait la comparaison de pointeur. Mon tri n'était même pas utilisé. Après la lecture des informations type erasure. J'ai adapté ma solution de pointeur en la plaçant à l'intérieur d'un objet multi_key_c qui a transmis ses appels <, == et strIdx() au pointeur key_base_c que j'ai caché à l'intérieur de celui-ci. Après avoir écrit quelques classes dérivées, j'ai vite vu que cela se prêtait à être un modèle et que ma solution se mettait rapidement en place.

Je pense qu'il peut y avoir de meilleures façons de mettre en œuvre, mais voici ce que j'ai jusqu'à présent:

#include <map> 
#include <sstream> 
#include <iostream> 
#include <utility> 



// 
// list of types to act as the primary key. The primary key dicatates the 
// format of the secondary key. 
// 
enum e_types { 
    E_ERROR = 0, 
    E_INT = 1, 
    E_CHAR = 2, 
    E_STR = 3, 
}; 





// Base class for the multi-key. 
class key_base_c { 

public: 

    key_base_c (enum e_types key_type) : 
     key1(key_type) 
     {}; 


    virtual ~key_base_c(void) {}; 


    virtual std::string strIdx (void) const { 
     std::stringstream ss_idx; 

     ss_idx << key1; 
     return (ss_idx.str()); 
    } 


    virtual bool operator< (const key_base_c &b) const { 
     return (key_base_c::operator<(&b)); 
    } 


    virtual bool operator< (const key_base_c *p) const { 
     return (key1 < p->key1); 
    } 


    virtual bool operator== (const key_base_c &b) const { 
     return (key_base_c::operator==(&b)); 
    } 


    virtual bool operator== (const key_base_c *p) const { 
     return (key1 == p->key1); 
    } 


protected: 

    e_types key1; // the primary key 

}; 





// template policy_key_c 
// 
// EVENT_TYPE_VAL - select the enumerated value to use for key1's value 
// 
// KEY2_TYPE   - select the class to use for the second key. For built 
//      in types they use their default < and == operators, 
//      If a private custom type is specified then it must 
//      have its own < and == operators specified 
// 
template <enum e_types EVENT_TYPE_VAL, 
      class   KEY2_TYPE> 
class policy_key_c : public key_base_c 
{ 
public: 

    policy_key_c (KEY2_TYPE key_value) : 
     key_base_c(EVENT_TYPE_VAL), 
     key2(key_value) 
     {}; 


    virtual ~policy_key_c(void) {}; 


    // return the index as a string. 
    virtual std::string strIdx (void) const { 
     std::stringstream ss_idx; 

     ss_idx << key_base_c::strIdx() << "." << key2; 
     return (ss_idx.str()); 
    } 


    // 
    // operator < 
    // 
    virtual bool operator< (const key_base_c &b) const { 
     return (operator<(&b)); 
    } 


    virtual bool operator< (const key_base_c *p) const { 

     // if the primary key is less then it's less, don't check 2ndary 
     if (key_base_c::operator<(p)) { 
      return (true); 
     } 


     // if not less then it's >=, check if equal, if it's not equal then it 
     // must be greater 
     if (!(key_base_c::operator==(p))) { 
      return (false); 
     } 


     // primary keys are equal, so now check the 2ndary key. Since the 
     // primary keys are equal then that means this is either a key_base_c 
     // object or its a policy_key_c object. 
     const policy_key_c *p_other = dynamic_cast<const policy_key_c*>(p); 


     // if NULL then it was a key_base_c, and has no secondary key, so it is 
     // lexigraphically smaller than us, ergo we are not smaller than it. 
     if (!p_other) { 
      return (false); 
     } 

     return (key2 < p_other->key2); 
    } 



    // 
    // operator == 
    // 
    virtual bool operator== (const key_base_c &b) const { 
     return(operator==(&b)); 
    } 


    virtual bool operator== (const key_base_c *p) const { 

     // if the primary key isn't equal, then we're not equal 
     if (!(key_base_c::operator==(p))) { 
      return (false); 
     } 


     // primary key is equal, so now check the secondary key. Since the 
     // primary keys are equal, then that means this is eitehr a key_base_c 
     // object or its a policy_key_c object. 
     const policy_key_c *p_other = dynamic_cast<const policy_key_c*>(p); 

     // if NULL then it was a key_base_c 
     if (!p_other) { 
      // why? If the LHS is a key_base_c it doesn't go any deeper than 
      // the base. Hence we don't either. 
      return (true); 
     } 

     return (key2 == p_other->key2); 
    } 


protected: 

    KEY2_TYPE key2; // The secondary key. 

}; 



class multi_key_c { 
public: 
    multi_key_c (key_base_c *p) : 
     p_key(p) 
     {}; 


    ~multi_key_c(void) {}; 


    bool operator< (const multi_key_c &mk) const { 
     return (p_key->operator<(mk.p_key)); 
    } 


    bool operator== (const multi_key_c &mk) const { 
     return (p_key->operator==(mk.p_key)); 
    } 


    std::string strIdx (void) const { 
     return (p_key->strIdx()); 
    } 

protected: 
    key_base_c *p_key; 
}; 







// DO_TEST(x, op, y) 
// x, y: can be any derived key type 
// op : The operation to do < or == 
// 
// Prints the operation being done along with the results of the operation 
// For example: 
//  DO_TEST(a, <, b) 
// will print: 
//  a < b: <results> 
// 
// where <results> are the results of the operation 'a < b' 
#define DO_TEST(x, op, y, expect)            \ 
{                    \ 
    bool retval = x op y;             \ 
    std::cout << #x " " #op " " #y ": " << retval        \ 
       << " = " << ((retval == expect) ? "pass" : "----FAIL") << "\n"; \ 
} 





template <class C> 
void 
print_them (C    **pp_c, 
      int   count, 
      std::string s_type) 
{ 
    int idx; 

    std::cout << "\n" << count << " keys for " << s_type << "\n"; 

    for (idx = 0 ; idx < count; ++idx) { 
     std::cout << " " << (*pp_c)->strIdx() << "\n"; 
     pp_c++; 
    } 
} 






int 
main (void) 
{ 
    std::cout << "\nBASE\n"; 

    key_base_c base_error(E_ERROR), base_int(E_INT), base_char(E_CHAR); 
    key_base_c base_str(E_STR); 

    key_base_c *key_base_array[] = { 
     &base_error, &base_int, &base_char, &base_str 
    }; 


    print_them(key_base_array, 
       (sizeof(key_base_array)/sizeof(key_base_array[0])), 
       "key_base_c"); 

    DO_TEST(base_error, < , base_error, false); 
    DO_TEST(base_error, < , base_int, true); 
    DO_TEST(base_int, < , base_char, true); 
    DO_TEST(base_char, < , base_str, true); 

    std::cout << "\n"; 
    DO_TEST(base_error, ==, base_error, true); 
    DO_TEST(base_int, ==, base_int, true); 
    DO_TEST(base_char, ==, base_char, true); 
    DO_TEST(base_str, ==, base_str, true); 

    std::cout << "\n"; 
    DO_TEST(base_error, ==, base_int, false); 
    DO_TEST(base_int, ==, base_char, false); 
    DO_TEST(base_char, ==, base_str, false); 




    // INT 
    // 
    typedef policy_key_c<E_INT, int> key_int_2; 

    key_int_2 i1(1), i2(2), i3(3), i4(4); 
    key_int_2 *key_int2_array[] = { 
     &i1, &i2, &i3, &i4, 
    }; 


    print_them(key_int2_array, 
       (sizeof(key_int2_array)/sizeof(key_int2_array[0])), 
       "key_int_2"); 

    DO_TEST(base_int,  < , i1,   false); 
    DO_TEST(i1,   < , base_int, false); 

    DO_TEST(i1,   < , base_char, true); 
    DO_TEST(base_char, < , i1,   false); 

    DO_TEST(i1,   ==, i1,   true); 
    DO_TEST(i1,   ==, base_int, true); 
    DO_TEST(base_int,  ==, i1,   true); 
    DO_TEST(i1,   ==, base_error, false); 
    DO_TEST(base_error, ==, i1,   false); 


    std::cout << "\n"; 
    DO_TEST(i1, < , i2, true); 
    DO_TEST(i1, < , i3, true); 
    DO_TEST(i1, < , i4, true); 



    // CHAR 
    typedef policy_key_c<E_CHAR, char> key_char_c; 


    key_char_c c1('a'), c2('b'), c3('c'), c4('d'); 
    key_char_c *key_char_array[] = { 
     &c1, &c2, &c3, &c4, 
    }; 

    print_them(key_char_array, 
       (sizeof(key_char_array)/sizeof(key_char_array[0])), 
       "key_char"); 


    DO_TEST(base_int,  < , c1,  true); 
    DO_TEST(base_int,  ==, c1,  false); 
    DO_TEST(base_char,  < , c1,  false); 
    DO_TEST(base_char,  ==, c1,  true); 
    DO_TEST(base_str,  < , c1,  false); 
    DO_TEST(base_str,  ==, c1,  false); 

    std::cout << "\n"; 
    DO_TEST(c1,   < , c1,  false); 
    DO_TEST(c1,   ==, c1,  true); 
    DO_TEST(c1,   < , c2,  true); 
    DO_TEST(c1,   ==, c2,  false); 

    std::cout << "\n"; 
    DO_TEST(c1,   ==, i1,  false); 
    DO_TEST(i1,   ==, c1,  false); 
    DO_TEST(c1,   < , i1,  false); 
    DO_TEST(i1,   < , c1,  true); 



    // STR 
    typedef policy_key_c<E_STR, std::string> key_str_c; 


    key_str_c s1("aaa"), s2("bbb"), s3("ccc"), s4("ddd"); 
    key_str_c *key_str_array[] = { 
     &s1, &s2, &s3, &s4 
    }; 

    print_them(key_str_array, 
       (sizeof(key_str_array)/sizeof(key_str_array[0])), 
       "key_str"); 

    DO_TEST(base_int,  < , s1,   true); 
    DO_TEST(base_char, < , s1,   true); 
    DO_TEST(base_str,  < , s1,   false); 
    DO_TEST(base_str,  ==, s1,   true); 
    DO_TEST(s1,   < , base_int, false); 
    DO_TEST(s1,   < , base_char, false); 
    DO_TEST(s1,   < , base_str, false); 
    DO_TEST(s1,   ==, base_str, true); 


    std::cout << "\n"; 
    DO_TEST(s1,   < , s1,  false); 
    DO_TEST(s1,   ==, s1,  true); 
    DO_TEST(s1,   < , s2,  true); 
    DO_TEST(s1,   ==, s2,  false); 



    std::cout << "\n\nNOW TESTING THE MAP\n\n"; 

    typedef std::multimap<multi_key_c, std::string> multiKeyMap; 

    multiKeyMap myMap; 


    multi_key_c k1(&i1), k2(&i2), k3(&i3), k4(&i4); 
    multi_key_c k5(&c1), k6(&c2), k7(&c3), k8(&c4); 
    multi_key_c k9(&s1), k10(&s2), k11(&s3), k12(&s4); 


    myMap.insert(std::make_pair(k1, "one")); 
    myMap.insert(std::make_pair(k2, "two")); 
    myMap.insert(std::make_pair(k3, "three")); 
    myMap.insert(std::make_pair(k4, "four")); 
    myMap.insert(std::make_pair(k1, "one.2")); 
    myMap.insert(std::make_pair(k4, "four.2")); 

    myMap.insert(std::make_pair(k5, "c1")); 
    myMap.insert(std::make_pair(k5, "c1.2")); 
    myMap.insert(std::make_pair(k6, "c2")); 
    myMap.insert(std::make_pair(k6, "c2.2")); 
    myMap.insert(std::make_pair(k7, "c3")); 
    myMap.insert(std::make_pair(k8, "c4")); 


    myMap.insert(std::make_pair(k9, "s1")); 
    myMap.insert(std::make_pair(k10, "s2")); 
    myMap.insert(std::make_pair(k11, "s3")); 
    myMap.insert(std::make_pair(k12, "s4")); 
    myMap.insert(std::make_pair(k12, "s4.2")); 
    myMap.insert(std::make_pair(k11, "s3.2")); 
    myMap.insert(std::make_pair(k10, "s2.2")); 
    myMap.insert(std::make_pair(k9, "s1.2")); 

    multiKeyMap::iterator pos; 

    for (pos = myMap.begin(); pos != myMap.end(); ++pos) { 
     std::cout << pos->first.strIdx() << " : " << pos->second 
        <<"\n"; 
    } 


    return (0); 
} 

---

sortie de c'est:

BASE 

4 keys for key_base_c 
    0 
    1 
    2 
    3 
base_error < base_error: 0 = pass 
base_error < base_int: 1 = pass 
base_int < base_char: 1 = pass 
base_char < base_str: 1 = pass 

base_error == base_error: 1 = pass 
base_int == base_int: 1 = pass 
base_char == base_char: 1 = pass 
base_str == base_str: 1 = pass 

base_error == base_int: 0 = pass 
base_int == base_char: 0 = pass 
base_char == base_str: 0 = pass 

4 keys for key_int_2 
    1.1 
    1.2 
    1.3 
    1.4 
base_int < i1: 0 = pass 
i1 < base_int: 0 = pass 
i1 < base_char: 1 = pass 
base_char < i1: 0 = pass 
i1 == i1: 1 = pass 
i1 == base_int: 1 = pass 
base_int == i1: 1 = pass 
i1 == base_error: 0 = pass 
base_error == i1: 0 = pass 

i1 < i2: 1 = pass 
i1 < i3: 1 = pass 
i1 < i4: 1 = pass 

4 keys for key_char 
    2.a 
    2.b 
    2.c 
    2.d 
base_int < c1: 1 = pass 
base_int == c1: 0 = pass 
base_char < c1: 0 = pass 
base_char == c1: 1 = pass 
base_str < c1: 0 = pass 
base_str == c1: 0 = pass 

c1 < c1: 0 = pass 
c1 == c1: 1 = pass 
c1 < c2: 1 = pass 
c1 == c2: 0 = pass 

c1 == i1: 0 = pass 
i1 == c1: 0 = pass 
c1 < i1: 0 = pass 
i1 < c1: 1 = pass 

4 keys for key_str 
    3.aaa 
    3.bbb 
    3.ccc 
    3.ddd 
base_int < s1: 1 = pass 
base_char < s1: 1 = pass 
base_str < s1: 0 = pass 
base_str == s1: 1 = pass 
s1 < base_int: 0 = pass 
s1 < base_char: 0 = pass 
s1 < base_str: 0 = pass 
s1 == base_str: 1 = pass 

s1 < s1: 0 = pass 
s1 == s1: 1 = pass 
s1 < s2: 1 = pass 
s1 == s2: 0 = pass 


NOW TESTING THE MAP 

1.1 : one 
1.1 : one.2 
1.2 : two 
1.3 : three 
1.4 : four 
1.4 : four.2 
2.a : c1 
2.a : c1.2 
2.b : c2 
2.b : c2.2 
2.c : c3 
2.d : c4 
3.aaa : s1 
3.aaa : s1.2 
3.bbb : s2 
3.bbb : s2.2 
3.ccc : s3 
3.ccc : s3.2 
3.ddd : s4 
3.ddd : s4.2