CODEWITHSUNDEEP
c++templatesdata-structures
javaLover
javaLover

Reputation: 6425

Data structure with type-specific, but without template

I have noticed that most (all?) of C++ data structures that can store a user defined type use template:

std::vector<T>, std::unordered_map<T....>, etc.

It seems to me that it is required, otherwise those data-structures will have to return as the sinister pointer void* that users have to cast manually as follows:

std::vector a; 
int b;
a.push_back(b);
static_cast<int>(a.get(0));

Is it possible to not use the template? Are there any other alternative approaches?

Edit: Many comments suggest that without template, it is impossible / impractical. (Thank!)

What if I limited <T> to be a real pointer (e.g. not int/float), will it still be impractical?

Upvotes: 2

Views: 306

Answers (4)

lorro
lorro

Reputation: 10880

I agree that templates are the correct way to approach containers, std::any (or boost::any) when you can't use containers. However, just for the fun part I'd like to note that perfect type reconstruction is possible via exceptions. Note this is very much ill-recommended, I'm just adding this for completeness. In this case,

  • your vector is like std::vector<std::function<void()>> (can be simplified),
  • you push elements like v.push_back([e](){ throw e; }); and
  • you visit elements by, yuck, not less than catching the exception thrown by e.g. try{ v[i](); } catch(EType& e) { ... }.

This is ugly, don't do this, this is slow, don't do this.. but, on the other hand, it allows for perfect visitation (including inheritance, which you don't get with type_info), open hierarchies (which you don't get with variant), chaining of visitors, without the need for base class & additional virtual functions.

BIG FAT WARNING: you probably wouldn't pass my CR with such a code - it's just mentioned for fun and theoretical completeness.

Upvotes: 2

skypjack
skypjack

Reputation: 50550

You can rely on type erased structures.
As a minimal, working and naïve example:

#include<memory>
#include<iostream>
#include<vector>

struct Container {
    struct B {
        virtual void operator()() = 0;
    };

    template<class T>
    struct D: B {
        D(T t): o{t} {}
        void operator()() override { o(); }
        T o;
    };

    template<typename T>
    void add(T t) {
        vec.push_back(std::unique_ptr<B>{new D<T>{t}});
    }

    void operator()() {
        for(auto &ref: vec) (*ref)();
    }

    std::vector<std::unique_ptr<B>> vec;
};

struct P {
    void operator()() { std::cout << "P" << std::endl; }
};

struct Q {
    void operator()() { std::cout << "Q" << std::endl; }
};

int main() {
    Container c;
    P p;
    Q q;
    c.add(p);
    c.add(q);
    c();
}

C++17 will probably bring in std::any and let you doing it easily.
Until then, you can use boost::any or an homemade type erased class like the one above.

Upvotes: 2

eerorika
eerorika

Reputation: 238351

Is it possible to not use the template?

Yes. It is possible to define a general data structure, that allows grouping <-- I don't know what verb to use here objects of any type, without using a template.

There is the "C way" (templates do not exist in C). The C way is to use void*. You are apparently already familiar, but for other readers of the answer, void* is a special pointer type, that can point to an object of any type. When you use void* to refer to an object, you essentially throw away all type safety that the language offers.

I don't think there are any non-template containers † in the standard library. However, if it is not too much to use the offered templates to instantiate std::vector<void*> or similar, then you can certainly use such template instance to store pointers to any objects.

Templates are strongly preferred to void* because templates do not throw type safety out of the window. Templates are much easier to use correctly.

† Not yet. But std::any is planned to be introduced in C++17. It can be used in stead of void*. Using std::any you still throw away compile time type safety, but at least you retain run time safety (you'll get an exception instead of potentially dragons when you have a bug). And unlike void*, std::any manages the memory of the stored object. Note that while std::any is not a template, most of its member functions are.

Are there any other alternative approaches?

Besides templates and void*? Technically, you could also use macros to generate different versions of same program, similarly to instantiating a template. This is sometimes used in C. There is no reason do this in C++, because templates are better in every way.

Upvotes: 4

W.F.
W.F.

Reputation: 13988

I will give you an example why can it be dangerous to use such an collection. Consider the code below:

#include <vector>
#include <iostream>

using anyvector = std::vector<void *>;

int main() {
   anyvector av;
   av.push_back(new int(10));
   std::cout << (*static_cast<int*>(av[0])) << std::endl;
}

the av[0] is a pointer to int created by old-fashioned c++ way using new keyword. As such one should free the memory allocated this way using delete keyword. But to do this the pointer should be first cast to the right type to let compiler know what is he really deleting in order to prevent from undefined behaviour.

To be clear I'm not saying it is impossible nor impractical but it require from the programmer full consciousness...

Upvotes: 2

Related Questions