2017-12-30 29 views
4

私はここ数日間、ここを巡って同様のサイトを見てきましたが、解決に時間を費やして助言を求めています。インデックス付きの秩序のあるマップを作成する

私は、C++のためにライブラリを強化することなく、索引付けされた順序付けを保持する連想型コンテナを作成することはできない、との残念な結論に達しました。

私が必要とするものは、オペレータ[key]を使用してルックアップできるマップですが、繰り返しのために要素が追加された順番にインデックスが付けられています。

今朝私は自分自身を書く必要があり、マップやペアのベクトルなどのマップを使って試してみましたが、実際には何も機能していませんでした。驚くべきことに、この言語では何も達成できません。私は正しく間違っていなければなりませんか?他の誰かがこの機能を必要とする経験を持っていますか、私が探しているものの正しい方向に向けることができるこの概念に精通していますか?

事前に感謝します。あけましておめでとう皆さん。

+0

それは言語で可能です - あなたはバッキングを使用してキーのルックアップ削除/挿入されたアイテムと 'ベクトル'は '地図を'使用して試してみました挿入順に? – hnefatl

+0

@KillzoneKidそれは驚くことではありません!それが、私がこれに関して持っていた最初の偽りの解決策でした。 – JosephJerrel

+0

あなたはboost :: multi_indexを見ましたか?私はそれがあなたが後になっていることをすることができるかどうかは分かりません。 – SoronelHaetir

答えて

0

警告:これは、非常にです。希望の動作の粗いモックアップです。これは良いコードの近くにはありませんが、すばやく、これを行う手法を実証する必要があります。

独自のロールを検討する前に、Boostのmulti_indexなどの既存のソリューションを使用する必要があります。それは、より簡単で、速く、エラーを起こしにくく、より良い設計になります。

template<typename Key, typename Val> 
class OrderedMap 
{ 
private: 
    std::vector<std::pair<Key, Val>> ordered; 
    std::map<Key, std::size_t> lookup; 

public: 
    void insert(Key k, Val v) 
    { 
     ordered.push_back(std::pair<Key, Val>(k, v)); 
     lookup.emplace(k, ordered.size() - 1); 
    } 

    Val find(Key k) 
    { 
     std::size_t index = lookup[k]; 
     return ordered[index].second; 
    } 
    // "typename" needed as the "iterator" is a dependent type 
    typename std::vector<std::pair<Key, Val>>::iterator begin() 
    { 
     return ordered.begin(); 
    } 
    typename std::vector<std::pair<Key, Val>>::iterator end() 
    { 
     return ordered.end(); 
    } 
}; 

我々が必要なのは、キーと値のインデックスとの間の関連を追跡するために挿入された要素の実際の順序を追跡し、そしてstd::map<Key, std::size_t>するstd::vector<std::pair<Key, Val>>です。次に、このクラスから必要な機能をこれらの内部バッキング/ルックアップ構造の機能に委譲することができます。

このクラスが望む動作と内部のコンテナの間で提供するインターフェイスは、好きなだけ堅牢にすることができます。ここでは、デモに必要な醜い骨を取り除きました。


See a quick demo here

OrderedMap<std::string, int> m; 
m.insert("1", 1); 
m.insert("2", 2); 
m.insert("3", 3); 

std::cout << m.find("2") << std::endl << std::endl; 

for (auto i = m.begin(); i != m.end(); i++) 
    std::cout << i->first << " " << i->second << std::endl; 
std::cout << std::endl; 

は出力が得られます。もちろん

2 

1 1 
2 2 
3 3 
+1

ポインタが簡単に無効になるため、ベクトルのインデックスへのマップが改善されました。 – juanchopanza

+0

値へのポインタではなく、値(コピー)だけが必要な場合があります。 (編集)ええ、それが決して変わらないなら、インデックスはより良いでしょう。 –

+0

ベクトルが再配置されたときにポインタが壊れます。また、キーを2回保存しています。純粋なベクトルのインデックスにマップすると、削除が問題になります。それは、賢明なものを草案することはそれほど容易ではないことを証明している。設計上の決定がいくつかあります。 – luk32

関連する問題