How to check whether a container is stable

Question

std::vector is an unstable container, i.e. by resizing the vector, iterators might become invalidated. In contrast, std::list or boost::container::stable_vector are stable containers which keep the iterators valid until the removal of the corresponding element.

Is there a way to check whether a given container is stable? For instance, if I have something like

template<template <typename A, typename B=std::allocator<A> > class T=std::list>
class Foo
{
}

Is it possible to allow only for stable containers and forbid the unstable ones?

Answer 1

I don't think there is anything available providing such information, but you could write your own trait. However, you will need to specialize it for every stable container that may be used, which is perhaps not an option.

#include <boost/container/vector.hpp>

#include <iostream>
#include <type_traits>
#include <list>
#include <vector>

template <template <typename...> class Container>
struct is_stable
    : std::false_type
{};

template <>
struct is_stable<std::list>
    : std::true_type
{};

template <>
struct is_stable<boost::container::stable_vector>
    : std::true_type
{};

template<template <typename...> class Container = std::list>
class Foo
{
    static_assert(is_stable<Container>::value, "Container must be stable");
};

int main()
{
    Foo<std::list> f1; // ok
    Foo<std::vector> f2; // compiler error
}

I don't think there is a way you can automatically detect that a container is stable, without resorting to manual specialization.

---

Just for fun, I tried writing what the concept/axiom for stability would look like (concepts and axioms are an extension to the language that were considered for inclusion in C++11):

concept StableGroup<typename C, typename Op>
    : Container<C>
{
    void operator()(Op, C, C::value_type);

    axiom Stability(C c, Op op, C::size_type index, C::value_type val)
    {
        if (index <= c.size())
        {
            auto it = std::advance(c.begin(), index);
            op(c, val);
            return it;
        }
        <->
        if (index <= c.size())
        {
            op(c, val);
            return std::advance(c.begin(), index);
        }
    }
}

If think this correctly captures the requirement that every iterator over the original container is equivalent to the corresponding iterator over the modified container. Not sure this is very useful, but coming up with such axioms is an interesting exercise :)!