创建索引有序映射

Question

过去几天我在这里和类似的网站环顾四周，并花了很多时间试图找到解决方案，并希望寻求建议。

我得出了令人失望的结论，即如果不进入C ++的boost库，就没有办法创建一个保留索引排序的关联容器。

更清楚，更具体地说，我需要的是一个可以使用operator [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::vector<std::pair<Key, Val>>来跟踪插入的元素的实际顺序，以及一个std::map<Key, std::size_t>来跟踪键和值索引之间的关联。然后我们可以将我们想要的功能从这个类委托给这些内部支持/查找结构的功能。

这个类在所需行为和内部容器之间提供的接口可以随心所欲地运行 - 在这里，我只是充实了演示所需的丑陋骨骼。

---

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