Update the STL containers

[gnzlbg]

What is the status on updating the STL containers to use concepts (and ranges) as well?

Have there been any discussions about this?

[ericniebler]

Not yet. Want to start the discussion?

[gnzlbg]

I was kind of hoping that the discussion had already happened and I could get some guidance, but maybe my questions will kickstart the discussion.

I was working on a static_vector<T, size_t Capacity> and looking at this static_vector::insert overload:

CONCEPT_REQUIRES(CopyConstructible<T>{} and Swappable<T>{})
constexpr iterator insert(const_iterator position, std::initializer_list<T> il) {
    // one cannot move elements out of an `initializer_list`...
}

I can easily constrain it with two "fundamental" (Range TS) concepts, but range-v3 also defines Insertable-like concepts. I was wondering if I should try to use those, define my own, or just stick to the fundamental ones as long as I can. I cannot really use the concepts defined for range actions since they would turn out recursive within the containers (e.g. insert requires that insert exist and works).

After the experience with static vector I believe that constraining std::array should be trivial. I wonder, however, how easy it could be to constrain std::vector. In C++14 I would have said that we would need to constrain Allocators first, but IIUC most "troublesome" allocator methods are deprecated in C++17, I'd guess I'll have to try.

I've also found out that for testing whether a type's non-template methods are properly constrained explicit template instantiations are great, but this has resulted in me implementing workarounds to support explicit instantiating static_vector<const unique_ptr<int>, N> and similar crippled types. So obviously I wonder whether doing this makes sense at all.

Is there a trick to find out if I've properly constrained something? I don't really mind that much about over-constraining things a bit, but I would like to catch all the under-constrained functions. I thought I had properly constrained static_vector when static_vector<int, N> explicitly instantiated properly just to find out that I hadn't when I tried to explicitly instantiate static_vector<unique_ptr<int>, N> and then have it break another two times when I tried static_vector<const int, N> and static_vector<const unique_ptr<int>, N> (and now that I wrote this I realize I might want to try instantiating it with int& and const/volatile friends just to be really sure...).

[CaseyCarter]

CONCEPT_REQUIRES(CopyConstructible<T>{} and Swappable<T>{})
constexpr iterator insert(const_iterator position, std::initializer_list<T> il) {
   // one cannot move elements out of an `initializer_list`...
}

IIRC static_vector uses a fully-initialized array of T as its backing store, in which case this function needs to copy assign, not copy construct. The constraint should then be Copyable<T>{} and Swappable<T&>{}.

I can easily constrain it with two "fundamental" (Range TS) concepts, but range-v3 also defines Insertable-like concepts.

I would be leery of anything not defined in the TS: there are a lot of "ad hoc" concepts in range-v3 that are syntax without well-documented semantic constraints.

I wonder, however, how easy it could be to constrain std::vector

I have an archive lying around somewhere from a few days I spent trying to constrain vector and forward_list while respecting the allocator completeness requirements in the C++17 WP. It's messy. Consider that e.g. allocator-aware containers never directly construct or destroy objects of their element types: they only do so indirectly through their allocator.

Is there a trick to find out if I've properly constrained something?

The best we can do right now is to test with parameter types specially engineered to meet only the minimal requirements. This is harder than it sounds, especially when the writer of the test is the writer of the component being tested. Your biases and assumptions tend to carry over from one to the other and inhibit effective testing.

[gnzlbg]

IIRC static_vector uses a fully-initialized array of T as its backing store, in which case this function needs to copy assign, not copy construct.

That's an optimization for when std::is_trivial<T>{} == true. When it is false it uses std::aligned_storage and constructs the elements using placement new on it using the copy constructor. I guess that the constraints don't say that if T is trivial, then copy assignment will happen, but if T is trivial, it is always Copyable. EDIT: maybe something like (CopyConstructible<T>{} and Swappable<T&>{}) or std::is_trivial<T>{} would make it more clear, but if T is trivial the condition left of the or is always true anyways.

Consider that e.g. allocator-aware containers never directly construct or destroy objects of their element types: they only do so indirectly through their allocator.

This is what I thought as well, and what seems true in C++14. In C++17 Allocator::construct and Allocator::destroy (and Allocator::adressof) are deprecated, and there doesn't seem to be any replacement. I thought this meant that C++17 allocators only allocate and free raw memory, and that in C++17 it is the container's job to manage object construction and destruction. This would actually simplify constraining vector, since it can define its own construct / destroy functions that it can properly constrain.

EDIT: I got it wrong: double checking it seems that the member functions of std::allocator are deprecated, but the std::allocator_traits<Allocator> static functions construct, destroy, ... are not.

[CaseyCarter]

if T is trivial, it is always Copyable.

Not necessarily. A trivial class can have deleted special member functions N4606 [class]/6:

A trivially copyable class is a class:

(6.1) — where each copy constructor, move constructor, copy assignment operator, and move assignment operator (12.8, 13.5.3) is either deleted or trivial,

(6.2) — that has at least one non-deleted copy constructor, move constructor, copy assignment operator, or move assignment operator, and

(6.3) — that has a trivial, non-deleted destructor (12.4).

A trivial class is a class that is trivially copyable and has one or more default constructors (12.1), all of which are either trivial or deleted and at least one of which is not deleted.

This is what I thought as well, and what seems true in C++14, but in C++17 Allocator::construct and Allocator::destroy (and Allocator::adressof) are deprecated, and there doesn't seem to be any replacement. I thought this meant that C++17 allocators only allocate and free raw memory, and that in C++17 it is the container's job to manage object construction and destruction.

More precisely, allocator-aware containers are required to use allocator_traits<Allocator> as an intermediary instead of interacting directly with allocators. The deprecated members of std::allocator are no longer needed since they are equivalent to the default implementations of those members in std::allocator_traits. C++17 allocators are no less complicated than those in C++14, the only difference is that we've deprecated some members of std::allocator in the expectation that we won't have to support those "old" C++03-era members forever.

[gnzlbg]

@CaseyCarter could you share your forward_list and vector experiments somewhere?

[CaseyCarter]

could you share your forward_list and vector experiments somewhere?

containers. Caveat emptor - it's more than a bit rough and incomplete.