シーケンシャルにインデックスされた順序付けされたマップの作成

Question

次のコードは、私が作成したいと思っている非常に基本的で重要な機能を示しています。私は私が探しているものに解決策を書くために働いており、これは私が来た最も近いものです。この実装の修正または再設計を特定する上での助けがあれば、大いに感謝しています！

これはクラスです。私が探しているのは、演算子[キー]機能を実行できるだけでなく、要素が追加されるにつれて順番に反復されるマップです。私は、その値が対応するペアのベクトルに保持されている実際の値へのポインタであるルックアップ用のマップを持つことによって、これを実行しようとしています。

template <typename t> 
class IndexedMap { 
public: 
    t& operator [] (string s) { 
    bool nu = true; 

    for (auto& e : actual) // for each pair 
     if (e.first == s) // if exist 
    nu = false; 
    if (nu == true) { // if needs created 
     actual.push_back(pair <string, t>()); // create proper pair 
     actual.back().first = s; // assign key 
     // create copy in map @ same key pointing to actual value 
     lookup[s] = &actual.back().second; 
    } 
    return *lookup[s]; // return reference to value 
    } 

    typename vector <pair <string, t>>::iterator begin() { 
    return actual.begin(); 
    } 

    typename vector <pair <string, t>>::iterator end() { 
    return actual.end(); 
    } 

private: 
    vector <pair <string, t>> actual; 
    map <string, t*> lookup; 
}; 

この実装それが実行され、私は実際に私が探しています結果を見ないと、次のtest.cpp-意味で「作品」が、TEST.CPPの終了時に、私が関与するいくつかのクレイジーなエラーを取得していますfree（）への呼び出しと私はそれが起こっているか、修正する方法がわかりません。

ます。test.cpp：

int main() { 
    IndexedMap <vector <int>> test; 

    test["BILLS"]; test["GAS"]; 
    test["GROCERY"]; test["PETS"]; 
    test["TAKEOUT"]; test["OTHER"]; 

    int i = 0; 
    for (auto e : test) // check order 
    cout << e.first << endl; 
    for (auto& e : test) // assign 3 unique values to each vector 
    for (int f = 0; f < 3; ++f, ++i) 
     e.second.push_back(i); 
    for (auto e : test) { // display them 
    cout << e.first << ":" << endl; 
    for (auto f : e.second) 
     cout << f << endl; 
    } 
    vector <int> blank; // test modifying a value 
    test["GAS"] = blank; 
    for (auto e : test["GAS"]) 
    cout << e << endl; 
    cout << "hopefully empty?" << endl; 
} 

私は、これはあまりにも私が説明したりこれを書かれている方法を混乱されていません願っています。提供されるあらゆる助けに事前に感謝します。

皆さん、ありがとうございました！

Answer 1

@juanchopanzaのおかげで、この問題の解決策を見つけました。

上記の前回の実装でポインターが無効にされている場所は正確にはわかりませんが、インデックスを使用してベクトル内の適切な要素を識別し、この要素へのポインタ私は安全だ;）

t& operator [] (string s) { 
    bool nu = true; 

    for (auto& e : actual) // for each pair 
     if (e.first == s) // if exist 
     nu = false; 
    if (nu == true) { // if needs created 
     actual.push_back(pair <string, t>()); // create proper pair 
     actual.back().first = s; // assign key 
     lookup[s] = actual.size()-1; // assign proper index in map @ same key 
    } 
    return actual[lookup[s]].second; // return reference to value 
    } 

Answer 2

この行はエラー

actual.push_back(pair <string, t>()); // create proper pair 

を公開し、不幸から茎場所です。

lookup[s] = &actual.back().second; // a pointer to an element in a vector. 

ベクトルのサイズが変更されるとどうなりますか？新しい配列がベクトルに割り当てられ、古い配列のデータが新しい配列にコピーされ、古い配列の割り当てが解除されます。これはポインタを古い配列に無効にします。

解決策を少し評価して、ベクトルを繰り返してsが存在するかどうかを確認します。これはO（N）です。見つかった場合は、とにかくO（log N）のlookupをマップに追加します。

そして、我々は代わりにポインタの実際にインデックスを使用したいので、あなたのマップのペアは、当社が書き換えもしそうなら

using mappair = std::pair<std::string, int>; 

でなければなりません（未テストコード）

for (auto& e : actual) // for each pair 
    if (e.first == s) // if exist 
    nu = false; 
if (nu == true) { // if needs created 
    actual.push_back(pair <string, t>()); // create proper pair 
    actual.back().first = s; // assign key 
    // create copy in map @ same key pointing to actual value 
    lookup[s] = &actual.back().second; 
} 
return *lookup[s]; // return reference to value 

へ

auto found = lookup.insert(mappair(s, -1)); 
if (found.second) { // true if new element 
    actual.emplace_back(mappair(s,t()); 
    found->first.second = actual.size()-1; 
} 
return *found.first;