c++ - 创建索引有序映射

Question

过去几天，我浏览了这里和类似的网站，花了很多时间试图找到解决方案，并想寻求建议。

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

更清楚和具体的是，我需要的是一个 map ，它可以使用 operator[key] 进行查找，但也可以在为迭代目的添加元素的顺序中建立索引。

今天早上我决定我需要自己写一个，我已经尝试了一些使用 map 的 map 和成对的 vector 等的方法。但实际上没有任何效果，并且令人惊讶地获得了我正在寻找的所有功能用这种语言不容易实现。我一定是错的吧？有没有其他人有过需要此功能或熟悉此概念的经验，可以为我指明我正在寻找的正确方向？

非常感谢!大家新年快乐。

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>跟踪键和值索引之间的关联。然后我们可以将我们想要的功能从此类委托(delegate)给这些内部支持/查找结构的功能。

此类在所需行为和内部容器之间提供的接口(interface)可以像您喜欢的那样健壮 - 在这里，我只充实了演示所需的丑陋骨架。

---

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