Можно ли использовать карту STL с ключами разных размеров?

Question

Можно ли использовать карту STL для ключей разных размеров?

У меня нет кода для этого. Я все еще пытаюсь понять, можно ли это сделать, и, следовательно, мой вопрос. (Я из тех, кто может потратить слишком много времени на невозможную проблему. Я надеюсь извлечь уроки из твоей мудрости).

Я работаю над таблицей поиска, которая по сути имеет два ключа. Ключ числового типа и вторичный ключ конкретного типа.

Например, ключ первого уровня - это перечисление:

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

И тогда вторичные ключи зависят от типа ключа. Вторичный ключ для E_INT - это целое число, для E_CHAR - это символ и т. Д.

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"

Моей первой реакцией было сделать массив указателей на карту. Ключ первого уровня используется в качестве индекса в массиве. Где индекс массива указывает на карту, которая поддерживает тип вторичного ключа.

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

Я знаю Я могу заставить работать вышеперечисленное, но я подумал, что смогу объединить два ключа и получить одну карту с помощью специального алгоритма sort() для работы с комбинированными ключами.

Я полностью схожу с ума от мысли об этом? Если это не сумасшествие, есть ли у вас какие-либо предложения о том, как продолжить это?

Вдоль головы мне нужно сделать унаследованный класс для ключа, где базовый класс предоставляет чисто виртуальную функцию для метода sort, а затем унаследовать классы ключей для E_INT, E_CHAR и E_STR, которые реализуют метод sort() для их использования. Тогда я бы использовал базовый класс ключей в качестве ключа для карты.

Комментарии

---

РЕДАКТИРОВАТЬ 8/13/2010

Я пробовал некоторые изложенные решения, а также свои оригинальные мысли. Я продолжаю сталкиваться с проблемами. Я наткнулся на другую статью в стеке потока, в которой упоминалось стирание типа , которая могла бы помочь моим разным ключам.

---

РЕДАКТИРОВАТЬ 8/16/2010

Добавлен ответ в разделе ответов ниже, в котором показано кодовое решение, которое я реализовал.

Answer 1

std::map требует строгий слабый порядок для ключей. Если вы можете применить единый порядок для разных типов ключей с помощью пользовательского компаратора, тогда это не должно быть проблемой.

Answer 2

Несмотря на то, что было представлено много решений ... ни одно из них не настолько элегантно, как:

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

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

Да, вот и все.boost::variant естественно упорядочивается сначала по типу, а затем (когда типы равны) по значениям, которые они несут (если их можно сравнивать).

Я призываю любого найти более простое решение;)

Answer 3

Я думаю, что ваш подход правильный с точки зрения того, что вы будете делать с пользовательскими ключами.

Тем не менее, если вы можете сэкономить накладные расходы на наличие N карт вместо одной карты с пользовательским ключом, я бы сказал, сделайте это, поскольку это тривиально и быстро.Вы можете даже лениво загружать карты и просто скрывать реализацию за другим классом.

EDIT : ваш собственный компаратор также должен быть простым.Сначала вы можете строго упорядочить по enum, а затем для ключей с тем же значением enum (CHAR, INT, STR и т. Д.), А затем просто сравнить по значению.Это гарантирует порядок, требуемый std :: map.

Answer 4

Если вы используете boost :: Any в сочетании с оператором сравнения, как в http://www.sgi.com/tech/stl/Map.html. Вы должны иметь возможность использовать несколько типов в качестве ключа, если ваш оператор может их заказать. Если вы используете boost :: Any, они будут занимать больше места, чем сам ключ, но остальные решения, показанные здесь, также будут накладывать некоторые накладные расходы.

Answer 5

Вам нужно будет обернуть два ключа в один объект. Ваш новый класс также должен быть сопоставимым. например:

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

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

Ничто не мешает key1 и key2 быть (умными) указателями. Когда объект (например, myKey) сопоставим с помощью оператора <, его можно использовать на карте. </p>

Answer 6

Решение, которое я реализовал

---

Консенсус состоял в том, что это можно сделать. Я как бы адаптировался к концепции стирание типа вместе с предложениями других выше. У меня есть кое-что, что работает сейчас. Ключ карты должен быть объектом, имеющим указатель на объект полиморфного ключа.

Я пытался использовать только базовый объект в качестве типа ключа, но когда карта создает свою копию ключа, это выглядело так, как будто это просто копирование базового класса.

Поэтому я наивно переключился на указатель (key_base_c *). Однако, это тогда просто сделало сравнение указателей. Моя сортировка даже не использовалась.

После прочтения информации erasure . Я адаптировал свое решение для указателя, поместив его внутри объекта multi_key_c, который перенаправлял свои вызовы <, == и strIdx() на указатель key_base_c, который я спрятал внутри него.

После написания пары производных классов я быстро понял, что это само по себе является шаблоном, и мое решение быстро встало на свои места.

Я подозреваю, что могут быть более эффективные способы реализовать это, но вот что у меня есть:

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

---

Выходные данные:

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

Answer 7

Вы можете реализовать класс для ключа, который реализует оператор <, что-то вроде этого (не проверено):

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

Возможно, вам также нужен конструктор копирования, но я думаю, вы поняли идею,Как только вы сгладите морщины, это будет хорошо работать в качестве ключа карты.Хотя, если честно, ваше решение с массивом карт, вероятно, будет намного проще, если оно будет работать на вас.

Answer 8

вам когда-нибудь придется сортировать все списки вместе? Если это так, то при попытке доступа к элементам вам будет больно.

Один глупый способ сделать это - просто создать тип объединения и функцию сравнения для объединения:

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

теперь ваша функция сравнения может просмотреть b.key каждой записи, чтобы увидеть, какой тип следует использовать.