A C++ implementation of LinkedHashMap This is my attempt at a C++ version of Java's LinkedHashMap. Any criticism is welcome.

I implemented important methods. Big thing still to do would be an iterator. First I wanted to get feedback on this thus far:

#include &lt;unordered_map&gt;
#include &lt;list&gt;
#include &lt;utility&gt;
#include &lt;algorithm&gt;
#include &lt;set&gt;

using namespace std;

template &lt;class K, class V&gt;
class linked_hash_map {
private:
    typedef typename list&lt;K&gt;::iterator list_iterator;
    unordered_map&lt; K, pair&lt;V, list_iterator &gt; &gt; hash; 
    list&lt;K&gt; ls;
public:
    int size() { return hash.size(); }
    bool empty() { return hash.empty(); }
    void insert(pair&lt;K,V&gt; kv) {
        if (hash.count(kv.first) == 1) {
            auto p = hash[kv.first];
            hash[kv.first] = make_pair(kv.second, p.second);  
        } else {
            ls.push_back(kv.first);
            auto it = ls.end(); --it;
            hash.insert( make_pair(kv.first, make_pair(kv.second, it)));
        }
    }
    void erase(K key) {
        if (hash.count(key) == 1) {
            auto p = hash[key];
            hash.erase(key);
            ls.erase(p.second);
        }
    }
    void eraseEldest() {
        if(!hash.empty()) {
            K key = ls.front();
            ls.pop_front();
            hash.erase(key);
        }
    }
    void eraseNewest() {
        if(!hash.empty()) {
            K key = ls.back();
            ls.pop_back();
            hash.erase(key);
        }
    }
    V at(K key) {
        auto p = hash.at(key);
        return p.first;
    }
    V operator[](K key) {
        auto p = hash[key];
        return p.first;
    }
    list&lt;K&gt;&amp; keyList() {
        return ls;
    }
};
#include &lt;algorithm&gt;
#include &lt;set&gt;


I don't see anything from &lt;algorithm&gt; or &lt;set&gt; in the code.

using namespace std;


Never do this. Just never do this. But especially never do this in a header.

unordered_map&lt; K, pair&lt;V, list_iterator &gt; &gt; hash; 
list&lt;K&gt; ls;


It seems a little inefficient to store the key twice - once in the map and once in the list. If the key is an int, no problem, but what if the key is an expensive type?

One possible solution is to store pointers to the keys in the list. So you have:

std::unordered_map&lt; K, pair&lt;V, list_iterator &gt; &gt; hash; 
std::list&lt;K const*&gt; ls;


But that's only one alternative.

int size() { return hash.size(); }
bool empty() { return hash.empty(); }


Both of these functions should be const, and probably both noexcept as well.

void insert(pair&lt;K,V&gt; kv) {
    if (hash.count(kv.first) == 1) {
        auto p = hash[kv.first];
        hash[kv.first] = make_pair(kv.second, p.second);  
    } else {
        ls.push_back(kv.first);
        auto it = ls.end(); --it;
        hash.insert( make_pair(kv.first, make_pair(kv.second, it)));
    }
}


There are a lot of inefficiencies in this function, and a lot of problems with exception safety.

Let's start with the inefficiencies, focusing on the case where the key is already in the map. You start by searching the map for the key (to count). And then you search the map for the key again to get the list iterator (using operator[]). And then you search it AGAIN to actually set the value.

Instead, what if you searched it just one time, and used the result from then on. For example:

void insert(std::pair&lt;K,V&gt; kv) {
    auto const p = hash.find(kv.first);
    if (p != hash.end()) {
        p-&gt;second.first = std::move(kv.second);
    } else {
        // ...


Now let's look at the exception issues in the second half of the function. First you create the key in the list, which can succeed or fail - if it fails, that's bad, but at least your class's invariants are still valid. Next you create the key, value, iterator set in the map. If that fails, then your class is now in the state where there is a key in the list that is not in the hash table.

Unfortunately, there is no easy fix for this. You are updating two different data structures; either one can fail, so no matter what you do you need to handle the case where the first one succeeds and the second one fails.

You could do something like this:

void insert(std::pair&lt;K,V&gt; kv) {
    auto const p = hash.find(kv.first);
    if (p != hash.end()) {
        p-&gt;second.first = std::move(kv.second);
    } else {
        ls.push_back(kv.first);
        try {
            auto it = ls.end(); --it;
            hash.insert( make_pair(kv.first, make_pair(kv.second, it)));
        }
        catch (...) {
            ls.pop_back();
            throw;
        }
    }
}


Or, a little more efficiently:

void insert(std::pair&lt;K,V&gt; kv) {
    auto const p = hash.find(kv.first);
    if (p != hash.end()) {
        p-&gt;second.first = std::move(kv.second);
    } else {
        auto const it = ls.insert(ls.end(), kv.first);
        try {
            hash.insert( make_pair(std::move(kv.first), make_pair(std::move(kv.second), it)));
        }
        catch (...) {
            ls.erase(it);
            throw;
        }
    }
}


It might also be worthwhile to create two insert() functions, one that takes std::pair&lt;K, V&gt; const&amp; and doesn't use std::move(), and one that takes std::pair&lt;K, V&gt;&amp;&amp; and uses std::move().

On to erase():

void erase(K key) {
    if (hash.count(key) == 1) {
        auto p = hash[key];
        hash.erase(key);
        ls.erase(p.second);
    }
}


Once again, you are searching the hash map multiple times (once for count(), once for operator[], and once again for erase()). Also, you are taking the key by value, which is unnecessary. You're only reading its value, so you should take it by const&amp;.

A more efficient version of the function might look like this:

void erase(K const&amp; key) {
    auto const p = hash.find(key):
    if (p != hash.end()) {
        ls.erase(p-&gt;second.second);
        hash.erase(p);
    }
}


The next two functions have basically the same problems:

void eraseEldest() {
    if(!hash.empty()) {
        K key = ls.front();
        ls.pop_front();
        hash.erase(key);
    }
}


There is no need to copy the key into a variable, then remove it from the list, then use the variable to remove it from the hash table. Do it the other way around, and you avoid copies:

void eraseEldest() {
    if(!hash.empty()) {
        hash.erase(ls.front());
        ls.pop_front();
    }
}


Once again, the next two functions have basically the same problems:

V at(K key) {
    auto p = hash.at(key);
    return p.first;
}


There are loads of unnecessary copies here. First, the key is copied into the function argument, because you don't take it by const&amp;. Then both the key and the value (and a list iterator) are copied into p. Then the value is copied again into the return value.

Let's start at the top.

The key doesn't need to be copied here, because you're just inspecting it's value. You can take it by const&amp;:

V at(K const&amp; key) {


The return value probably doesn't need to be copied either, and if you want to use it like lhm.at(key) = new_value;, it must be a reference. So:

V&amp; at(K const&amp; key) {


Now, in the function, you don't need to copy the result of hash.at(key) - in fact you really shouldn't. You should just take a reference to it:

auto&amp; p = hash.at(key);
return p.first;


But there's really no need for p:

return hash.at(key).first;


Putting it all together:

V&amp; at(K const&amp; key) {
    return hash.at(key).first;
}


For const correctness, you'll need two of these functions, one const and one not:

V&amp; at(K const&amp; key) {
    return hash.at(key).first;
}

V const&amp; at(K const&amp; key) const {
    return hash.at(key).first;
}


And of course, all of the same for operator[].

list&lt;K&gt;&amp; keyList() {
    return ls;
}


This is exceptionally dangerous. You are returning a non-const reference to the key list in your class. You are giving users the freedom to completely break your class's invariants. I can do:

auto&amp; key_list = lhm.keyList();
key_list.clear();
// now lhm.hash is full of dangling list iterators


If you want to return the key list, you should not return it as a non-const reference. Either return it as a const reference or - better - by value. Don't give outsiders access to the guts of your class.