Recently I've read things about abstract machine and as-if rule ([What exactly is the "as-if" rule?](https://stackoverflow.com/questions/15718262/what-exactly-is-the-as-if-rule)), and the requirements on time complexity of standard library (like this one: [Is list::size() really O(n)?](https://stackoverflow.com/questions/228908/is-listsize-really-on)).

1. Are the time/space complexity requirements on standard library in terms of abstract machine or in terms of real concrete machine?

If these are in terms of abstract machine, it seems an implementation can actually generate less efficient code in terms of complexity even though it seems not to be practical.

2. Did the standards mention anything about time/space complexity for non-standard-library code?

e.g. I may write a custom sorting code and expect O(n log n) time, but if an implementation just treats this as code in abstract machine, it is allowed to generate a slower sorting in assembly and machine code, like changing it to O(n^2) sort, even though it unlikely will do that in real situation.

Or maybe I missed something about the transformation requirements between abstract machine and real concrete machine. Can you help me to clarify? :)

Even thought I mainly read things about C++ standard, I also want to know the situation about C standard. So this question tags both.