How Can I Preserve Insertion Order in a Map While Maintaining Efficient Lookups?

Preserving Insertion Order in a std::map

In situations where the order of insertion is crucial, relying solely on a std::map may not suffice. If maintaining the insertion order is a priority, there are alternative approaches to consider.

One option involves converting the map's contents into a std::vector before iterating and printing its values. By leveraging a suitable functor, you can employ std::sort to arrange the elements based on their insertion order.

However, if rapid lookups are essential (e.g., 10 million times), using a vector may introduce performance concerns. For such scenarios, the boost::multi_index library offers a solution that combines the efficiency of a map with the flexibility of multiple indexes.

Using boost::multi_index:

This library allows you to establish multiple indexes for each container. In this specific case, you can define a value_t struct with string and int members, and utilize two indexes:

1. Random Access: Represents the insertion order
2. Hashed Unique: Indexes the string member to facilitate quick lookups

You can then instantiate a multi_index_container like so:

struct value_t {
    string s;
    int i;
};

struct string_tag {};

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

This approach grants efficient lookups while preserving the insertion order when iterating the container.

The above is the detailed content of How Can I Preserve Insertion Order in a Map While Maintaining Efficient Lookups?. For more information, please follow other related articles on the PHP Chinese website!