Draft: Add a replacement for std::vector

(this is just an experiment and not intended to be merged)

Summary

This MR provides a container Dune::Vector with a similar interface as std::vector to be used as internal storage data structure in other dune vector and matrix types.

Rationale

The container std::vector is most of the time the best choice for storing contiguous data. Unfortunately, it has one design flaw that must be preserved for backwards compatibility reasons: The std::vector<bool> specialization. Instead of storing regular bools in the vector, these values are compressed resulting in the need for special proxy reference and pointer types. This change in interface is the reason why in some places in Dune we need to use a std::vector<char> to represent a bool vector. This is not very intuitive. Also, using the regular bool type even in containers using std::vector under the hood, e.g., BlockVector or VariableBlockVector from dune-istl, results in difficult to understand error messages.

Code that does not work

We cannot instantiate a BlockVector and VariableBlockVector (from dune-istl) with bool as element type:

Dune::BlockVector<bool> mask_vector(10); 
  // ERROR in dune/istl/bvector.hh:559:30: use of deleted function 
  // ‘void std::vector<bool, _Alloc>::data() [with _Alloc = std::allocator<bool>]’
  // this->p = storage_.data();

I tried to think about solutions to this issue. The solution I came up with are: writing out own std::vector-like class, as simple as possible, with an interface as close as possible to std::vector, to be used in some container data-structures, e.g. DynamicVector, mdarray, BlockVector...

In this (experimental) MR, I have provided such a vector implementation: Dune::Vector. The difference to a std::vector is the missing push_back and insert functions and the capacity is the same as the size.

In a second implementation in vector2.hh, I have changed this to inherit the implementation from std::Vector for types unequal to bool. An only for bool I do a specialization that provides the regular std::vector interface.

Discussion

Do you have another, maybe simpler, idea how to circumvent the problem with std::vector<bool>?

Related branches

In dune-istl I have created connected branches with the same name feature/vector to test the BlockVector and VariableBlockVector containers with this new Dune::Vector.

added discussion feature labels

As an alternative... how about storing a bool-wrapper instead of bool directly?

something like

struct bool8_t {
    bool _v;
    bool8_t(bool b) : _v(b) {}
    bool8_t() : _v(false) {}
    bool8_t operator = (bool b) { _v = b; return *this; }
    operator bool&() { return _v; }
    operator const bool&() const { return _v; }
};

It should behave like bool, but without special treatment.

What do you mean?

1. we teach everyone to use std::vector<Dune::bool8_t> or,
2. we write a vector class with specialization

template <class T, class A = ...>
class Vector : std::vector<T,A> {...};

template <class A>
class Vector<bool, A> : std::vector<bool8_t> {...};

Isn't bool8_t simply another proxy type that will lead to the same issues as the one provided by std::vector<bool> already?

The second option I have more-or-less implemented, by using std::vector<std::byte> and providing conversions where necessary.

No, it is not a proxy, as the object itself is stored in the container, so no big surprises. Still you can interact with it as with a bool.

I'm not quite sure which places you have in mind, where people face issues due to the specialization of std::vector<bool>, but my impression would have been that this mostly concerns internal code. Here I don't see a problem using std::vector<bool8_t> instead.

I have to admit, that I'm not a fan of a dune-specific implementation of std::vector. I don't want to teach new users that there is this dune-version of vector that is basically the same, but for bool and that they should now use that one.

Perhaps you could give some more concrete examples of the issues you have mind. I'm not saying that I'm a fan of std::vector<bool>, but I would really prefer having a work-around that does not require a new vector class.

The example that I always stumble over is in dune-functions. When creating a bitvector as a mask-vector to denote regions of Dirichlet BC, we have to use a BlockVector<char>. The BlockVector<bool> is not working, since internally the ->data() member is called on the storage vector. A std::vector<bool> does not have this data member, i.e., it is deleted.

Thus, here char is a valid alternative to bool and works fine. Also your bool8_t works after minor modifications. But I don't want to write as a user bool8_t when I mean bool.

My intention of the Dune vector class was (and this is really just an experiment) to replace the internal storage of some vector/matrix types in dune, e.g. BlockVector, VariableBlockVector,... that are all not instantiable with bool as element type. So, it is meant to be an internal data structure and not for the "regular" user. They are typically fine with a classical std::vector<bool>.

One other alternative I could think of is to specialize all the data structure in Dune that use currently a std::vector and make something special for bool to circumvent this issue, e.g. to replace automatically bool with bool8_t or char. The Dune::Vector class was meant to be a low-level automatic way of doing this.

If it is just XYZBlockVector, then maybe we can fix the bool case there directly.

What is the problem with char? I am also annoyed when I find templated implementations based on std::vector<bool>, but it also takes 3 seconds to realize that char is the (almost) perfect alternative.

I guess a problem would be with places where one explicitly needs bool rather than an implicitly convertible to bool. Then both your bool8_t and std::byte variants would solve that issue. But is this a problem at all? Are there places where char is not sufficient?

@simon.praetorius if you actually consider it OK to use std::vector<byte> or some other bool replacement and it is only used internally, I'd not go for a replacement of std::vector, but for an automatic way to map the "requested" (due to template arguments) std::vector<bool> to something else. One option might be a special creator that could then be used in your assembler.

std::vector<byte> is also complicated as internal data structure. std::vector<char> works, but one has to understand the consequence that the value_type is not bool and this and any type constraint or template meta-programming relying on the return type of the vector might give surprising results. A workaround this issue that transforms all return types and argument types to bool and all typedefs, is provdided in vector2.hh. Also just an experiment.

Note also that is not about me. I can use BlockVector<char> since I am aware of this issue. It does not introduce any overhead. But what I am concerned about is that BlockVector<bool> does not even compile.

I would also try to avoid a replacement. It will be hard to be complete unless you spend a lot of work to eventually duplicate the implementation. E.g. your implementation lacks several essential features for me. Then we would have to teach people about the dune-specific differences to std::vector in contrast to just the c++ folklore facts about std::vector<bool> that every c++ user should be aware of.

Also providing Dune::Vector<T> which forwards to std::vector<T> with the exception of T==bool where we forward to std::vector<SomethingLikeBool> is IMO not a good idea, because this template would again behave inconsistent for T==bool.

In principle I'm fine with using std::vector<char> myself. But @christi's proposal for some explicit replacement type has a few advantages:

• A name like bool8_t transports the meaning better than char or std::byte.
• Specializations of BlockVector<bool> could hint users to the named type in a static assertion.
• It helps to unify the replacement type among users.

Yes, the bool8_t might be more clear to the user since it communicates that the elements are actual bools. But this does not address the original issue: Our container types (at least in dune-istl) cannot be instantiated with the regular type bool. And this is annoying.

Note that the same issue shows up in the Std::mdarray class, also in the standard implementation, btw. This is, because std::vector<bool> is not a SequenceContainer and violates several assumptions we have on the container type to be wrapped by mdarray. Here as well a different default container in our Dune implementation of tensor data structures could be less surprising.

added 1 commit

• 2b938b09 - Add comparison operators

Compare with previous version

changed the description

While I like the idea, I was hoping we could some day be able to exploit stateful allocators in our containers and solvers. Rolling out our own version of std::vector would make this much more difficult because hierarchical containers are really complicated to implement while std::pmr::vector brings this out of the box. Therefore, I prefer much more the second approach.

You are right, the proper use of allocators is really difficult to implement.

I think the second approach could work, but it would need some testing. A hierarchical vector class needs that the underlying type is AllocatorAwareContainer. I think that the allocator generic constructor ensures that type rebinding is mostly enough, so your implementation should be fine, but better having a real test on that one.

Instead of writing our own class, couldn't we just have an std::vector selector to char or another suitable convertible to bool?

namespace Impl {

template<class T, class A>
struct StdVectorSelector {
    using type = std::vector<T,A>;
};

template<class A>
struct StdVectorSelector<bool,A> {
    using type = std::vector<char,A>;
};

template<class T, class A>
using StdVectorTypeSelector = typename StdVectorSelector<T,A>::type;

} // namespace Impl

added 1 commit

• 907dda71 - Replace imyplementation by vector2

Compare with previous version

I am not sure whether this is UB.

This looks fine to me

added 1 commit

• 12bcf28c - Update the documentation

Compare with previous version

mentioned in merge request !1433