Templates and STL

Question

The following code represents a container based on std::vector

template <typename Item>
struct TList
{
    typedef std::vector <Item> Type;
};


template <typename Item>
class List
{
private
            typename TList <Item>::Type items;
    ....
}

int main()
{
  List <Object> list;
}

Is it possible to templatize std::vector and create a general container, something like that?

template <typename Item, typename stl_container>
struct TList
{
    typedef stl_container<Item>;
};

where stl_container represents std::vector, std::list, std::set...? I would like to choose the type of container at the time of the creation.

List <Object, std::vector> list; //vector of objects, not a real code
List <Object, std::vector> list; //list of objects, not a real code

Thanks for your answers...

Updated question:

I tried the following code but there are errors:

#include <vector>
template <typename Item, typename Container>
struct TList
{
   typedef typename Container <Item>::type type; //Error C2059: syntax error : '<', Error C2238: unexpected token(s) preceding ';
};


template <typename T>
struct vector_container
{
  typedef std::vector<T> type;
};

int _tmain(int argc, _TCHAR* argv[])
{
TList <int, vector_container> v;
TList <int, map_container> m;
}

Answer 1

Yes, but not directly:

template <typename Item, template <typename> class Container>
struct TList
{
    typedef typename Container<Item>::type type;
};

Then you can define different container policies:

template <typename T>
struct vector_container
{
    typedef std::vector<T> type;
};

template <typename T>
struct map_container
{
    typedef std::map<T, std::string> type;
};

TList<int, vector_container> v;
TList<int, map_container> m;

A bit verbose, though.* To do things directly, you'd need to take the route described by James, but as he notes this is ultimately very inflexible.

However, with C++0x we can do this just fine:

#include <map>
#include <vector>

template <typename Item,
            template <typename...> class Container, typename... Args> 
struct TList
{
    // Args lets the user specify additional explicit template arguments
    Container<Item, Args...> storage;
};

int main()
{
    TList<int, std::vector> v;
    TList<int, std::map, float> m;
}

Perfect. Unfortunately there's no way to reproduce this in C++03, except via the indirection policy classes introduce as described above.

---

*I want to emphasize that by "A bit verbose" I mean "this is unorthodox". The correct solution for your problem is what the standard library does, as Jerry explains. You just let the user of your container adapter specify the entire container type directly:

template <typename Item, typename Container = std::vector<Item>>
struct TList
{};

But this leaves a big problem: what if I don't want the value type of the container to be Item but something_else<Item>? In other words, how can I change the value type of an existing container to something else? In your case you don't, so read no further, but in the case we do, we want to rebind a container.

Unfortunately for us, the containers don't have this functionality, though allocators do:

template <typename T>
struct allocator
{
    template <typename U>
    struct rebind
    {
        typedef allocator<U> type;
    };

    // ...
};

This allows us to get an allocator<U> given an allocator<T>. How can we do the same for containers without this intrusive utility? In C++0x, it's easy:

template <typename T, typename Container>
struct rebind; // not defined

template <typename T, typename Container, typename... Args>
struct rebind<T, Container<Args...>>
{
    // assumes the rest are filled with defaults**
    typedef Container<T> type; 
};

Given std::vector<int>, we can perform rebind<float, std::vector<int>>::type, for example. Unlike the previous C++0x solution, this one can be emulated in C++03 with macros and iteration..

---

**Note this mechanism can be made much more powerful, like specifying which arguments to keep, which to rebind, which to rebind themselves before using as arguments, etc., but that's left as an exercise for the reader. :)

Answer 2

I'm a bit puzzled why some very smart (and competent) people are saying no.

Unless I've misread your question, what you're trying to accomplish is virtually identical to the "container adapters" in the standard library. Each provides an interface to some underlying container type, with the container type that will be used provided as a template parameter (with a default value).

For example, a std::stack uses some other container (e.g., std::deque, std::list or std::vector) to hold the objects, and std::stack itself just provides a simplified/restricted interface for when you just want to use stack operations. The underlying container that will be used by the std::stack is provided as a template parameter. Here's how the code looks in the standard:

namespace std {
    template <class T, class Container = deque<T> >
    class stack {
    public:
        typedef typename Container::value_type value_type;
        typedef typename Container::size_type  size_type;
        typedef Container                      container_type;
    protected:
        Container c;
    public:
        explicit stack(const Container& = Container());
        bool empty() const             { return c.empty(); }
        size_type size() const         { return c.size(); }
        value_type& top()              { return c.back(); }
        const value_type& top() const  { return c.back(); }
        void push(const value_type& x) { c.push_back(x); }
        void pop()                     { c.pop_back(); }
    };
}

Of course, perhaps I've just misunderstood the question -- if so, I apologize in advance to the people with whom I'm (sort of) disagreeing.

Answer 3

Yes and no.

You can use a template template parameter, e.g.,

template <typename Item, template <typename> class Container>
struct TList { /* ... */ };

However, in general, template template parameters are not particularly useful because the number and types of the template parameters have to match. So, the above would not match std::vector because it actually has two template parameters: one for the value type and one for the allocator. A template template parameter can't take advantage of any default template arguments.

To be able to use the std::vector template as an argument, TList would have to be declared as:

template <typename Item, template <typename, typename> class Container>
struct TList { /* ... */ };

However, with this template, you wouldn't be able to use the std::map template as an argument because it has four template parameters: the key and value types, the allocator type, and the comparator type.

Usually it is much easier to avoid template template parameters because of this inflexibility.

Answer 4

well, you can hack it up with a macro:

template <typename T, typename stl_container = std::vector<T> >
struct TList
{
    typedef stl_container Type;
};

#define TLIST(T, C) TList<T, C<T> >

TList<int> foo;
TList<int, std::list<int> > bar;
TLIST(int, std::list) baz;

Answer 5

Is it possible to templatize std::vector and create a general container, something like that?

No. You would have to templatize the function or object using the container -- you couldn't templatize the container itself.

For example. consider a typical std::find:

template<class InputIterator, class T>
InputIterator find ( InputIterator first, InputIterator last, const T& value )
{
    for ( ;first!=last; first++) if ( *first==value ) break;
    return first;
}

This works for any container, but doesn't need a tempalte with the container at all.

Also, given that it looks what you're trying to do is make container independent code, you might want to buy or borrow yourself a copy of Scott Meyers' Effective STL and read Item 2: Beware the illusion of container-independent code.

Answer 6

You can use template template parameters as others have mentioned here. The main difficulty with this is not that dissimilar container types have dissimilar template parameters, but that the standard allows the standard containers, like vector, to have template parameters in addition to the documented, necessary ones.

You can get around this by providing your own subclass types that accept the appropriate template parameters and let any extras (which have to have defaults) be filled in my the implementation:

template < typename T > struct simple_vector : std::vector<T> {};

Or you can use the templated typedef idiom:

template < typename T > struct retrieve_vector { typedef std::vector<T> type; };