创建顺序索引的有序映射

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），如果发现你在地图中做了一个lookup，无论如何都是O（log N）。

我们想要将索引用于实际而不是指针，因此您的地图对应该是

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;