How to Maintain Insertion Order in a `std::map` While Preserving Efficient Lookups?

Maintaining Insertion Order in a std::map

In a scenario where a std::map fails to retain the insert order, the need arises for a container that preserves this critical property. While a std::vector> seems like a viable alternative, its performance penalty for frequent lookups and increment operations casts doubts on its suitability.

One effective solution is to employ a combination of std::map and std::vector. As the map ensures efficient string-based lookups, you can copy the map contents into a std::vector before performing sort operations. A custom functor can be used to define the sorting logic based on the insertion order.

Alternatively, the Boost library offers a powerful solution with boost::multi_index. This allows for multiple indexing of a single container. In your case, the following structure can be implemented:

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;

Here, the random_access index maintains the insertion order while the hashed_unique index ensures the unique string identifier for efficient lookups. This approach provides both efficient lookups and preservation of the insertion order.

The above is the detailed content of How to Maintain Insertion Order in a `std::map` While Preserving Efficient Lookups?. For more information, please follow other related articles on the PHP Chinese website!