A C++ container which keeps insertion order

C++ is a poorly designed programming language, and I live a love-hate relatioship with it.

On my vacation days, when working on WinLamb for the next version of SRTEd, I needed a container to keep track of the order the elements were inserted. Among the many useless obscure things that C++ has, it doesn’t have such a container. So I had to write one, which after much struggle I named it the insert_order_map.

Usage example, including iterator support for C++11 range-based for loop:

insert_order_map<wstring, wstring> all = {
  { L"initial", L"blab" },
  { L"initial2", L"bleb" }
};

all[L"first"] = L"abcdef";
all[L"second"] = L"123456";

for (insert_order_map<wstring, wstring>::entry& e : all) {
  wstring key = e.key;
  wstring val = e.value;
}

At first I wondered about using a sentinel linear search, line the one used within store. But then I realized that 99% of the time I’ll be using a string as the key with few elements inserted, thus the initial copy of the string at each search would take away the performance gains of the sentinel algorithm. So I decided to stick to an ordinary linear search.