Container optimization: Why are STL container method arguments no longer using allocator::const_reference typedef?

Question

BEFORE YOU READ: const_reference is typedef and does not need to be const T& as you can see in std::vector<bool>::const_reference = bool. Please keep that in mind while reading the rest to understand it properly (as suggested in commets, this is hard for many people).

---

I wanted to use STL containers for simple types (e.g. int) and found that they use the sub-optimal const T& "anti-pattern" - it works well for big classes, but is sub-optimal for simple/fundamental types when not inlined - consider embedded system, e.g. on ARM/ATSAM4L, with instantiation.

The question is: why was e.g. vector::push_back redesigned with argument of (const value_type&) instead of (Allocator::const_reference) since C++11? It should be the same for generic allocator, but doing it the other way would help me to write a custom allocator (or template specialization) for fundamental types that would define const_reference being the type itself (see vector<bool>::const_reference = bool).

Question 2: Is there any adaptor class that can do that for me?

Something like this:

template<class T, class base = std::vector<T> >
  class myvect: protected base {
public:
    typedef T const_reference;
    void push_back(const_reference value) {
        base::push_back(value); }}

Final usage would by like this:

typedef void (*action_t)(void*,int);
extern "C" void work(void *, action_t);
work(&vect, (action_t)&vect::push_back);

(note: ignore possible casting problems in previous code block, I hope you got the idea.)

EDIT: vector::const_reference is defined directly to be const value_type& but should in my opinion be defined as Alloc::const_reference which could then easily be changed (vector<int, MyAllocator<int> >). (This changed in C++11, it was defined as Alloc::const_reference but is now const value_type&)

EDIT: func(const T&) is sometimes described as "anti-pattern" here on stackoverflow because it is sub-optimal for fundamental types without inlining (yes, compiler generates optimal code even for func(const int&) if it gets inlined, but here is that IF. func(int) will do better work)

---

CONCLUSION: The very problem seems to be in the behaviour of const and therefore const T&. const does not really mean shall not change but do not change and therefore const T& is needed (and well defined and used) as return type for many methods. Creating custom adaptor class seems to be the best way for optimization and it seems to be widely accepted, that std::vector<bool> is odd exception which should be in separate class (e.g. dynamic_bitset).

Answer 1

Its a bit long in a comment, so I'll use an "answer" to speak about it, but really this is not an answer.

The feature you want, reworded:

You want te be able to avoid "pass by const reference" idiom in certain methods, to avoid the "slowdowns" incured by pointer operation for small types, versus direct copy. Notably true for push_back, if push_back had a parameter with a configurable type (by template means in the container type, like the allocator template parameter), then it could make you feel good.

It would be possible to provide the feature you want, definitely, for example by using the same method than the allocator template parameter, there could be a typename that specifies what kind of type is used in "push back" parameter.

But it was not designed that way, because it seems like a complexity, that is not worth it at all. It is not worth it because of compiler optimizations that will ellude a lot of overhead for fundamental types, because static analysis is much easier to run on fundamental types.

Secondly, the "lost time" of passing an int by reference versus copying it in a method parameters is deemed to be a platform specificity, that cannot be verified at the "virtual machine" level (the level at which language writers have to place themselves). Not to mention the "premature optimization" here that would cause a frank amout of code bloat to obtain, as a reasonable tradeoff for general purpose, it was completely evicted. This is also because at design time, you think fundamental types like rarities versus the infinity of possible types that can be contained.

ps: lastly, using a typedef as part of the allocator seems like a very bad separation of responsibility, having its own template parameter seems cleaner, because it has nothing to do with allocation, rather it has something to do with implementation choices of specific methods of the container.

ps2/Edit: I wish to add, as said in the comments, that the vector<bool>::const_reference cannot be taken as an example of what is possible to do, because it was a mistake in the standard, and is actually an infringement of the STL requirement that a container defines ..::reference as T&. A further proof of the problem is that vector<bool>::reference (not const) is not bool, it is an unspecified class (_Bit_reference in gcc) that serves as a proxy for access and mutation of a bit, packed in the vector, that shall serve as the storage support for the "virtual" bool value that is made into appearing like existing. These oddities cannot be ported to generic vector because they don't respect wide STL requirements. But it does not invalidate an orthogonal approach, like I mentioned with the pass_for_copy_param_type that could be a parameterizable, new typedef, and used in replacement in some places (suitable) where "const value_type&" is written today. But this is exactly the code bloat I mentioned before. I'm sure is definitely not worth so much for so little.

Answer 2

Changing the meaning of const_reference would break the semantics of methods that return a const reference:

std::vector<int> my_vector(100);
 // this needs an lvalue ref
my_vector[42]++;

// I want to track this value
std::vector<int>::const_reference i = my_vector[3];
  // I expect i to be be 1 after this
my_vector[3]++;

Answer 3

Allowing changing the type of const_reference breaks compatibility to the std::vector and container requirements. The standard explicitly assumes that const_reference is a reference and uses this many times, e.g. the semantics of data() and front(). In 23.3.6.4, it says "For a non-empty vector, data() == &front()". This make your modification invalid because with your modification, front() would not return a reference to the allocated memory anymore and hence the addresses would differ. In fact, it would be an address of a temporary object.

I also think that most compilers will optimize any additional costs of using const& away.

std::vector< bool > is a bad example because it is not a model of container in the STL sense. Most people agree that it should not have been defined in the standard, e.g. https://isocpp.org/blog/2012/11/on-vectorbool.