インデックス付きの秩序のあるマップを作成する

Question

私はここ数日間、ここを巡って同様のサイトを見てきましたが、解決に時間を費やして助言を求めています。

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

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

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

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

Answer 1

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

独自のロールを検討する前に、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