[mattnewport]

> I only said that it has something that's essentially concepts, except it has been designed, implemented and used since ages ago.

I'm not sure why this is relevant to the topic at hand though, other than historical interest. What's relevant is that something like concepts are a useful thing for a language to have and C++ will be a better / more usable language with them, even if it means adding 'complexity'.

> The whole point to ADTs is that clients don't get to manipulate the internal representation! What exactly is that, if not encapsulation?

You said "The concrete representation of these three types must be hidden from the user" and mentioned the pimpl pattern which led me to think you were talking about ABI issues. In C++ generally private members are not accessible but they are visible (in headers) and affect object size and layout. That can be a problem for build times and for versioning / binary compatibility but it also allows for private functions to be inlined and avoids pointer indirections and simplifies certain other optimizations (devirtualization for example).

C++ does not currently have a language level concept of modules (and I'm not sure the modules proposal working its way through standardization addresses your issue here) or anything like the C# internal access level. There are patterns to structure your code to enable implementation hiding for collaborating classes in a 'module' but they don't tend to be very widely used due to lack of first class language support. In my own experience I haven't found this to be a huge issue but maybe I just don't know what I'm missing.