#include <iostream>
#include <vector>
#include <map>
#include <string>

template<typename Key, typename Val>
class OrderedMap
{
private:
	std::vector<std::pair<Key, Val>> ordered;
	std::map<Key, std::size_t> lookup;
	
public:
	void insert(Key k, Val v)
	{
		ordered.push_back(std::pair<Key, Val>(k, v));
		lookup.emplace(k, ordered.size() - 1);
	}
	
	Val find(Key k)
	{
		std::size_t index = lookup[k];
		return ordered[index].second;
	}
	
	// "typename" needed as the "iterator" is a dependent type
	typename std::vector<std::pair<Key, Val>>::iterator begin()
	{
		return ordered.begin();
	}
	typename std::vector<std::pair<Key, Val>>::iterator end()
	{
		return ordered.end();
	}
};

int main()
{
	OrderedMap<std::string, int> m;
	m.insert("1", 1);
	m.insert("2", 2);
	m.insert("3", 3);
	
	std::cout << m.find("2") << std::endl << std::endl;
	
	for (auto i = m.begin(); i != m.end(); i++)
		std::cout << i->first << " " << i->second << std::endl;
	std::cout << std::endl;
	
	return 0;
}