Perl has a structure called "ordered hash" Tie::IxHash. One can use it as a hashtable/map. The entries are in the order of insertion.
Wonder if there is such a thing in C++.
Here is a sample Perl snippet:
use Tie::IxHash;

tie %food_color, "Tie::IxHash";
$food_color{Banana} = "Yellow";
$food_color{Apple} = "Green";
$food_color{Lemon} = "Yellow";

print "In insertion order, the foods are:\n";
foreach $food (keys %food_color) {
print " $food\n"; #will print the entries in order
Update 1
As @kerrek-sb pointed out, one can use Boost Multi-index Containers Library. Just wonder if it is possible to do it with STL.

Check Solution