Distingushing STL containers

Question

Quite frequently, I want to specialize a function for different STL containers. However I don't want to specialize one by one, since some of them share most of the needed interfaces, e.g, std::vector and std::deque.

In my use cases, there are mostly three categories( vector-like, set-like, map-like ). For example, I want to implement something like,

template <class T>
struct A {
    template <class Y, class... Z>
    void func( Y y , Z... z ){
        //hypothetical static_if
        static_if ( T is similar to vector, deque, or boost::stable_vector etc which have push_back ) {
            t.push_back(y);
        }
        else static_if ( T is similar to set, unordered_set or boost::flat_set etc which have emplace)    {
            t.emplace(y);
        }

        else static_if ( T is similar to map, unordered_map or boost::flat_map etc which has emplace) {
            t.emplace(y, z...);
        }

    }

    T t;  
};

I think this seems impossible but I hope there is some kind of hack for this situation. It would be also good if it can be extended to the list types(std::list, std::forward_list, ...) or boost::heap or else. However it seems too difficult to achieve the goal.

Answer 1

Nope, sorry. Don't do it. A full section in Scott Meyers' Effective STL is devoted to this. Here is an excerpt to give you an idea of how problematic this is:

Suppose, then, you aspire to write code that can be used with the most common sequence containers: vector, deque, and list. Clearly, you must program to the intersection of their capabilities, and that means no uses of reserve or capacity (see Item 14), because deque and list don’t offer them. The presence of list also means you give up operator[], and you limit yourself to the capabilities of bidirectional iterators. That, in turn, means you must stay away from algorithms that demand random access iterators, including sort, stable_sort, partial_sort, and nth_element (see Item 31).

On the other hand, your desire to support vector rules out use of push_front and pop_front, and both vector and deque put the kibosh on splice and the member form of sort. In conjunction with the constraints above, this latter prohibition means that there is no form of sort you can call on your “generalized sequence container.”

That’s the obvious stuff. If you violate any of those restrictions, your code will fail to compile with at least one of the containers you want to be able to use. The code that will compile is more insidious.

The main culprit is the different rules for invalidation of iterators, pointers, and references that apply to different sequence containers. To write code that will work correctly with vector, deque, and list, you must assume that any operation invalidating iterators, pointers, or references in any of those containers invalidates them in the container you’re using. Thus, you must assume that every call to insert invalidates everything, because deque::insert invalidates all iterators and, lacking the ability to call capacity, vector::insert must be assumed to invalidate all pointers and references. (Item 1 explains that deque is unique in sometimes invalidating its iterators without invalidating its pointers and references.) Similar reasoning leads to the conclusion that every call to erase must be assumed to invalidate everything.

Want more? [yes, this item goes on, and on, and on.]

Answer 2

I tried sofisticated traits a week ago, but went for a better readability.

So see here an examples: Is there a better way to check if a STL container is a multi* container

Answer 3

Here is a crude type traits library for containers.

template<typename Container>
struct container_traits;

template<bool b=true>
struct has_emplace_back { typedef std::integral_constant<bool, b> emplace_back; };
template<bool b=true>
struct has_emplace { typedef std::integral_constant<bool, b> emplace; };

template<typename T, typename A>
struct container_traits< std::vector<T,A> > : has_emplace_back<>, has_emplace<> {};
// etc
template<typename T, typename A>
struct container_traits< std::set<T,A> > : has_emplace_back<false>, has_emplace<> {};
// etc

template<typename T>
using HasEmplaceBack = typename container_traits<T>::has_emplace_back;
template<typename T>
using HasEmplace = typename container_traits<T>::has_emplace;

template<int> struct enum_enum { enum class type {}; };
template<int index> using UniqueEnum = typename enum_enum<index>::type;

template<bool b, int index=1>
using EnableIf = typename std::enable_if< UniqueEnum<index> >::type;
template<bool b, int index=1>
using DisableIf = EnableIf< b, -index >;

template<typename Container, typename... Args, EnableIf< HasEmplace<Container>::value && !HasEmplaceBack<Container>::value, 1 >... >
void emplace_in( Container&& c, Args&&... args ) {
  std::forward<Container>(c).emplace( std::forward<Args>(args)... );
}
template<typename Container, typename... Args, EnableIf< HasEmplaceBack<Container>::value, 2 >... >
void emplace_in( Container&& c, Args&&... args ) {
  std::forward<Container>(c).emplace_back( std::forward<Args>(args)... );
}

The EnableIf<>... technique does not work in clang, and I didn't compile it so it probably requires some debugging to fix.

Answer 4

It's not impossible, it's just not convenient or trivial to implement. Really, there needs to be a container_traits library.

This could be implemented using SFINAE to detect if a certain type Container contains the necessary features to meet the requirements of various STL Container Concepts.

For example, is_associative_container could use SFINAE to check that the Container type has a key_type and mapped_type typedef, and a std::pair<const key_type, map_type> for value_type, along with all the other requirements for an object that implements the AssociativeContainer concept.

Anyway, this is really something that needs to be implemented as a fully-fledged library. It's not trivial to implement, and you should probably look for another solution if you have a simple one-time need. You'd be better off abstracting at the Iterator level.