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

然後次級鍵取決於key_type的。用於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()算法來處理相結合的鍵。

我對此有何想法？如果它不是堅果，你有什麼建議如何進行這個？

關閉我的頭頂，我需要一個繼承類，其中的基類提供的排序方法的純虛函數的鍵，然後繼承了重點班爲E_INT，E_CHAR和E_STR，實現他們的使用方法爲sort()。然後，我將使用基本密鑰類作爲地圖的關鍵字。

評論？

編輯2010年8月13日

我一直想一些解決方案提出，還有我原來的想法。我一直在碰到問題。我偶然發現了另外一篇提到type erasure的文章，它可能會爲我的不同密鑰做訣竅。

編輯8/16/2010

加入下，答案部分答案給出了編碼的解決方案，我實現。

來源

2010-08-11 John Rocha

std::map需要strict weak ordering的鑰匙。如果您可以使用自定義比較器對不同的鍵類型執行單一訂單，那麼它不應該是一個問題。

來源

2010-08-11 17:10:00

我認爲你的方法是正確的，你會用自定義鍵做什麼。這就是說，如果你可以騰出N個地圖與一個具有自定義鍵的地圖的開銷，我會這樣做，因爲它很簡單，而且速度很快。你甚至可以懶加載地圖，只是將實現隱藏在另一個類的後面。

編輯：您自定義的比較應該是很簡單。你能嚴格按順序先枚舉，然後用相同的枚舉值（CHAR，INT，STR等）鍵，你應該那麼就由值進行比較。這將保證std :: map所需的順序。

來源

2010-08-11 17:06:42

我想確保我正確理解你的答案。我相信你是在說如果我可以負擔多個地圖，那麼就這麼做，因爲它簡單快捷。所以這聽起來像是我對C++可以做的事情過於興奮，我試圖做太多的事情） – 2010-08-11 17:18:06

是的，這是正確的。 – 2010-08-11 19:00:41

將你曾經有排序的所有名單在一起嗎？如果是這樣，那麼當你嘗試訪問元素時，你的方法會很痛苦。

一個笨的辦法來做到這一點是簡單地創建一個聯合類型和工會的比較功能：

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看應該是什麼類型用過的。

來源

2010-08-11 17:11:41 foobar

儘可能在'union'上使用'boost :: variant'來獲得類型安全。 – 2010-08-12 07:03:17

您需要將您的兩個鍵包裝成一個對象。你的新班級也需要具有可比性。例如：

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

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

沒有什麼能夠停止key1和key2是（智能）指針。一旦一個對象（如myKey）可以通過<運算符進行比較，就可以在地圖中使用它。

來源

2010-08-11 17:15:03 doron

它不需要通過'operator <'進行比較。你可以爲你的類型專門設置'std :: less'，或者提供一個自定義比較函數。 – 2010-08-11 18:45:48

您可以實現對於實施<運營商，像這樣（未經測試）的關鍵一類：

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

你可能還需要一個拷貝構造函數，但我認爲你的想法。一旦你消除皺紋，這將作爲一個地圖的關鍵。老實說，如果它適合你，你的地圖數組解決方案可能會簡單得多。

來源

2010-08-11 17:18:32

只要有可能，就爲'類型安全提供'優先''boost :: variant'。你也有內存泄漏，因爲沒有一個正確的賦值運算符... – 2010-08-12 07:04:26

實際上，上面可能會崩潰，因爲它會逐字節複製，然後雙刪除s指針。但我確實注意到實施並不完整。 – 2010-08-12 13:05:33

雖然有過很多的解決方案呈現......他們都不是高雅的：

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

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

沒錯，這就是全部。甲boost::variant自然受到由它們攜帶（如果它們可以比）的值類型和第二（當類型是相等的）第一排序。

我挑戰任何人找到一個簡單的解決方案;）

來源

2010-08-12 07:02:03

更簡單？介紹'boost :: variant_map'！ – GManNickG 2010-08-12 07:04:47

我研究過這個，但遺憾的是這對於變體中可以存在的實體數量有限制。在我的系統上，限制是20.雖然我上面的原型對於理解問題來說非常簡單和小巧，但我們將擁有超過20個1級密鑰。 – 2010-08-13 17:47:08

哦，我的...超過20個似乎很多。你有沒有嘗試重新定義'BOOST_VARIANT_LIMIT_TYPES'？如果您重新定義此宏，您將從使用超過20個元素的可能性中受益。儘管對於如此多的元素，我會試圖走下抽象的道路，因爲我不想交織如此多的依賴關係。 – 2010-08-14 13:00:35

如果你使用boost ::任何結合就像一個http://www.sgi.com/tech/stl/Map.html比較運營商。只要操作員可以訂購，您應該可以使用多種類型的鑰匙。如果使用boost :: Any，它們將佔用比密鑰本身更多的空間，但是這裏顯示的其他解決方案也會帶來一些開銷。

來源

2010-08-13 18:10:13

我讀了關於boost ::任何在我的類型擦除讀數。儘管沒有它我能夠得到一個工作原型。感謝您的建議。 – 2010-08-14 15:14:01

的解決方案，我實現

的共識是，它可以做。我對type erasure概念進行了修改，並附上其他人的建議。我現在有一些工作。 map鍵必須是一個具有指向多態鍵對象的指針的對象。

我試過只有基礎對象作爲鍵類型，但是當映射創建它的鍵副本時，它看起來像只是複製基類。

所以我天真地切換到一個指針（key_base_c *）。然而，這只是做了指針比較。我的分類甚至沒有使用過。

閱讀完type 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

來源

2010-08-13 22:52:16

STL地圖可以用於不同尺寸的按鍵嗎

回答

相關問題