如何在保持高效查找的同时维护'std::map”中的插入顺序？

在 std::map 中维护插入顺序

在 std::map<:string int> 的场景中如果无法保留插入顺序，则需要一个保留此关键属性的容器。而 std::vector>看起来是一个可行的替代方案，但其频繁查找和增量操作的性能损失让人对其适用性产生怀疑。

一个有效的解决方案是采用 std::map 和 std::vector 的组合。由于映射可确保高效的基于字符串的查找，因此您可以在执行排序操作之前将映射内容复制到 std::vector 中。自定义函子可用于定义基于插入顺序的排序逻辑。

或者，Boost 库通过 boost::multi_index 提供了强大的解决方案。这允许对单个容器进行多个索引。在您的情况下，可以实现以下结构：

struct value_t {
  std::string s;
  int i;
};

struct string_tag {};

typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // index representing insertion order
        hashed_unique<tag<string_tag>, member<value_t, string, &value_t::s>>
    >
> values_t;

这里，random_access 索引维护插入顺序，而 hashed_unique 索引确保唯一的字符串标识符以实现高效查找。这种方法提供了有效的查找和插入顺序的保留。

以上是如何在保持高效查找的同时维护'std::map”中的插入顺序？的详细内容。更多信息请关注PHP中文网其他相关文章！