How to check if a class is fully compliant with a given set of traits?

Question

Say I'm writing a custom container and want to provide a RandomAccessIterator for it.

template<class T>
class MyContainer
{
public:
    class RandomAccessIterator
    {
         /*
             ... operators, constructors, etc...
         */
    };
    RandomAccessIterator begin();
    RandomAccessIterator end();

/*
    ... class implementation ...
*/
};

Now, how can I check that the iterator I've just written is 100% compatible with standard library algorithms? One obvious solution is to simply try one:

MyContainer<int> list;
std::sort(list.begin(), list.end());

...and verify whether it compiles and produces desired results.

With that in mind, I am not sure if it's a reliable "trait compliance" test and that's exactly what this question is about. Will the compiler always complain if I forget to provide any of the required methods/operators? If not, what would be the best way to make sure that my types fully implement given traits?

@Edit: the post no longer refers to the standard library as to "the STL", which was incorrect as pointed out in the comments.

Answer 1

I would say it is possible based on C++20 iterator concepts¹:

template<std::input_iterator T>
using validate_input_iterator = T;

This would fail compilation:

struct meow {
    struct iterator{};
private:
    typedef validate_input_iterator<iterator> v; // fails here
};

However the below compiles:

struct meow: private std::string { // string has an input iterator
    // struct iterator{};
private:
    typedef validate_input_iterator<iterator> v; // passes!
};

https://godbolt.org/z/5DwiaT

If you actually want to check you implemented the required functions and traits correctly, this would of course couldn't be checked at compile time and requires writing some tests.

---

Syntactic requirements vs. Semantic requirements

Note that concepts, and specifically iterator concepts, declare both syntactic requirements and semantic requirements. While the syntactic requirements, stated based on the requires syntax, can be statically checked at compile time, the semantic requirements that are merely "notes" to be followed by that type, are not and cannot be checked at compile time. On the other hand algorithms and compiler decisions may be based on the fact that a type said to implement a specific concept follows its semantic requirements.

For example, bidirectional_­iterator is defined as:

23.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]

1. The bidirectional_­iterator concept adds the ability to move an iterator backward as well as forward.

     template<class I>
       concept bidirectional_iterator =
         forward_iterator<I> &&
         derived_from<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
         requires(I i) {
           { --i } -> same_as<I&>;
           { i-- } -> same_as<I>;
         };

2. A bidirectional iterator r is decrementable if and only if there exists some q such that ++q == r. Decrementable iterators r shall be in the domain of the expressions --r and r--.

3. Let a and b be equal objects of type I. I models bidirectional_­iterator only if:

   (3.1) If a and b are decrementable, then all of the following are true:

   (3.1.1) addressof(--a) == addressof(a)

   (3.1.2) bool(a-- == b)

   (3.1.3) after evaluating both a-- and --b, bool(a == b) is still true

   (3.1.4) bool(++(--a) == b)

   (3.2) If a and b are incrementable, then bool(--(++a) == b).

For a given iterator said to implement bidirectional_­iterator as seen above, bullet #1 can be checked at compile time while bullets #2 and #3 cannot.

---

_{¹ Should also be doable pre C++20 implementing your own SFINAE restricted template in a similar manner}