インデックス

Question

によってマップ値にアクセスする[0]？

私はマップが内部的にソートすることを知っていると私はこれで大丈夫だよ、私はインデックスでマップ内の値を取得したいです。私は[0] MYMAPを試みたが、私はエラーを取得：

Error 1 error C2679: binary '[' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion) 

私はこのような何か行うことができます実現：

string getKeyAtIndex (int index){ 
    map<string, int>::const_iterator end = myMap.end(); 

    int counter = 0; 
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) { 
     counter++; 

     if (counter == index) 
      return it->first; 
    } 
} 

をしかし、確かに、これは非常に非効率的ですか？より良い方法がありますか？

Answer 1

あなたmapは、その位置をすることにより、キーないでインデックス付け、そのようにアクセスすることが想定されていません。 A mapイテレータはlistのように双方向であるため、使用する関数はlistの位置でアクセスするよりも効率的ではありません。あなたの機能は、std::advance(iter, index)の助けを借りてbegin()から始まります。あなたが位置によってランダムにアクセスしたい場合は、vectorまたはdequeを使用してください。

Answer 2

まあ、実際にはできません。あなたが見つけた方法は非常に不安定で、O（n）の計算上の複雑さがあります（nは最悪の場合、nはマップ内の要素の数です）。ベクターまたは配列内のアイテムへのアクセス

比較（定数計算の複雑さ、一回の操作）により、複雑性O（1）を有します。

マップが内部的には赤い黒のツリー（または実装に依存するavlツリー）として実装され、すべての挿入、削除、および参照操作がO（ログn）最悪の場合（基本2操作では対数が必要ですツリー内の要素を見つけるために）、それはかなり良いです。あなたが扱うことができ

の方法は、ベクトルとマップの両方の内部で持っているカスタムクラスを使用することです。 クラスの終わりの挿入は平均O（1）、名前による検索はO（log n）、索引による検索はO（1）になりますが、この場合は削除操作はO（n）になります。

Answer 3

前の回答（コメントを参照してください）：ちょうどmyMap.begin();

についてあなたは、本質的にペアのベクトルであるベクトルのバッキングストアを使用してランダムアクセスマップを実装する方法。あなたはもちろん、その時点で標準ライブラリマップのすべての利点を失います。

Answer 4

目的を達成するための実装固有の（移植不可能な）メソッドがありますが、移植性のあるメソッドはありません。一般に

、std::mapは通常キーでソート二分木の種類として実装されています。最初の要素の定義は、順序によって異なります。また、あなたの定義では、要素[0]はツリーの一番上のノードか一番左の葉ノードですか？

多くのバイナリツリーはリンクリストとして実装されています。ほとんどのリンクされたリストは配列のように直接アクセスすることはできません。なぜなら、要素5を見つけるためにリンクをたどらなければならないからです。これは定義によるものです。

あなたがstd::vectorとstd::mapの両方を使用して、あなたの問題を解決することができます

1. は動的メモリからオブジェクトを割り当てます。
2. std::mapにポインターをキーとともに格納します。
3. std::vectorのポインタを の位置に保存します。

std::mapは、効率的な方法でキーでオブジェクトにアクセスできます。
std::vectorは、効率的な方法でインデックスでオブジェクトにアクセスできるようにします。 ポインタを格納すると、複数のコピーを維持する必要がなく、オブジェクトの1つのインスタンスのみが使用できます。

Answer 5

コンテナのような他のマップを使用することができます。
サイズフィールドを保持すると、バイナリ検索ツリーをランダムアクセスに簡単にすることができます。ここ
は、私が今見る
STDスタイル、ランダムアクセスイテレータ...
サイズバランスの取れたツリー...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
とB +ツリー...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h