How to Maintain Insertion Order When Storing Key-Value Pairs in C ?

Storing Inserted Key-Value Pairs in Order with std::map

A std::map is a container data structure that stores key-value pairs in a sorted order based on the key. However, when the need arises to maintain the insertion order of the pairs, the map no longer provides this functionality.

Alternative Solutions

• std::vector>: Using a vector to store the pairs offers easy insertion-order tracking, but it might be slower for frequent lookups (10,000,000 times).
• boost::multi_index: This library provides an extended container that allows for multiple indexes on the same data structure. It can be used to create an index for insertion order, making it possible to iterate and access the pairs in that order.

Code Example:

Consider this code snippet using the boost::multi_index approach:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/random_access.hpp>
#include <boost/multi_index/hashed_unique.hpp>

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

struct string_tag {};

typedef boost::multi_index_container<
  value_t,
  boost::multi_index::indexed_by<
    boost::multi_index::random_access<>, // Insertion order index
    boost::multi_index::hashed_unique<boost::multi_index::tag<string_tag>, boost::multi_index::member<value_t, std::string, &value_t::s>>
  >
> values_t;

In this example, the values_t container uses two indexes: an insertion-order index and a hashed-unique index on the s member. This allows for both ordered iteration and efficient lookups by the s key.

The above is the detailed content of How to Maintain Insertion Order When Storing Key-Value Pairs in C ?. For more information, please follow other related articles on the PHP Chinese website!