Const correctness with a std::map

How much const should you apply to a std::map?

// Given a custom structure, really any type though
struct Foo
{
   int data;
};

// What's the difference between these declarations?
const std::map<int, Foo> constMap;
const std::map<const int, const Foo> moreConstMap;

What are the tradeoffs or differences between constMap and moreConstMap?

The answer may apply to other stl containers too.