The paper is dated 94 which is the same year as the original implementation as the C++ STL (https://en.wikipedia.org/wiki/Standard_Template_Library#Impl...). So it's a fair bet they didn't have access to that. I would think the entire difficulty of the exercise would change with that.
I don't think you can compare the changes between Ada 83/95/2005/2012 to what has happened to C++. The Ada language seems much more stable and backwards compatible to me, and given it's nature, it makes sense to avoid introducing major changes. However, I'm not an Ada expert so correct me if I'm wrong.