Preserve the insertion order of object keys

[alecava]

It is possibile to avoid the alphabetical sorting of the keys in an object?

[gasparfm]

Haven't tested, but I think you can use std::unordered_map instead of std::map in the object typedef json11.hpp

[artwyman]

Doing that would avoid the alphabetical sort, but wouldn't preserve insertion order as you mention. Hashes have an undefined iteration order. If you want both fast lookup, and insertion-order iteration, you need a hybrid structure like a linked hash (http://www.drdobbs.com/cpp/an-stl-compatible-hybrid-of-linked-list/184406207). STL doesn't include such a datastructure.

[alecava]

Thank you guys for you replies, I think I will try to use boost::multi_index_container it offers al the features I need

[rianhunter]

I think there is a way to do this by using the Compare parameter when instantiating the std::map template. You'd have to tag each inserted object with a "insert order" index, though, either using std::pair or something custom.

[artwyman]

@rianhunter I believe if you do that then you'd need to know the insertion order at the time of the lookup in order to construct an appropriate key with which to find an entry, otherwise it would never actually be equal. I'm willing to be proven wrong with sample code, though. :)

[rianhunter]

@artwyman Oops, good point, the Compare is on the key not the value. You can hack it using multiple maps though e.g.

class Json final {
public:
  class object final {
    typedef int insert_order_t;
    typedef std::pair<insert_order_t, std::string> map_key_type;

    struct MapKeyCompare {
      bool operator()(const map_key_type & lhs, const map_key_type & rhs) const {
         return std::less<insert_order_t>(lhs.first, rhs.first);
      }
    };

    insert_order_t _cur_insert_order = 1;
    std::map< map_key_type, Json, MapKeyCompare> _map;
    std::unordered_map<std::string, insert_order_t> _map_2;

  public:
    /* ... constructors, other std::map-like methods etc. */

    T& operator[](const std::string & key) {
      auto & insert_order_of_key = _map_2[key];
      if (!insert_order_of_key) {
        // key doesn't exist in map
        insert_order_of_key =  _cur_insert_order++;
      }
      return _map[std::make_pair(insert_order_of_key, key)];
    }
  };
};

Bookkeeping isn't too hard with this method since everything is still key'd off the original key. You do pay some extra space costs though it pays back in relative simplicity / code reuse.

btw congrats to your team on http://github.com/dropbox/djinni :)