boost::stable_vector's capacity member function does not return the allocated capacity

Question

Consider the following code.

#include <string>
#include <boost/container/stable_vector.hpp>
#include <iostream>

int main()
{
  boost::container::stable_vector<std::string> vec;
  vec.reserve(10);
  std::cout << "capacity = " << vec.capacity() << '\n';
}

On running this (on g++/Linux), the output is:

capacity = 4294967286 (that's 2^32 - 10)

If I replace boost::container::stable_vector with std::vector above, the output is:

capacity = 10

I know it could as well have been capacity = 20, or capacity = 64 or whatever but that's still sane behavior.

What capacity() returns for stable_vector seems to be (2^32 - N), N being the capacity requested with a call to reserve(). I didn't see such a definition of capacity in the docs: http://www.boost.org/doc/libs/1_56_0/doc/html/boost/container/stable_vector.html#idp33067968-bb.

Answer 1

This is an obvious bug. The culprit is this diff, which changed this line in capacity()

return (index_size ? (index_size - ExtraPointers + extra_capacity) : index_size);

to

const size_type index_offset =
    (ExtraPointers + extra_capacity) & (size_type(0u) - size_type(index_size != 0));
return index_size - index_offset;

which was intended as an "optimization", presumably by avoiding a branch.

Unfortunately, the two blocks of code are not equivalent. The second one is actually equivalent to

return (index_size ? (index_size - (ExtraPointers + extra_capacity)) : index_size);
//                                 ^                              ^

So, instead of adding extra_capacity (which is 10 in your case), it subtracted it.

The bug has since been fixed in the trunk of Boost.Container, and the fix should be in the next release of Boost.