General comparison of objects in inheritance hierarchy in C ++

Question

I plan to write a multimap like this

std::multimap <key, base_ptr> mymap; 

And I would like to be able to store pointers to many derived classes (e.g. Der1 , Der2 ) that are derived from the database.

Now, when I try to insert an object into the map, I do a key search first, and then I need to compare if the EQUIVALENT object (does not have to be the same object, therefore, do not make pointer comparisons) to the one located in this place. Therefore, for this we can say that I redefine == operator or write some kind of comparison function. Now I would like to write code for this in such a way that when adding new derived classes I do not need to change or add anything.

So I think there should be a general way to write this. But unable to think about it.

I was thinking about something like the following

 class Base { virtual Base * get() { return this; } virtual bool isEqual(const Base& toObj) { .... } } class Der1 { Der1 * get() { return this; } bool isEqual(const Der1& toObj) { .... } } 

But that doesn't work either. because when i do this:

 Base* bp1; Base* bp2; bp1->get()->isEqual(*(bp2->get())) 

I see that the get() call ends in the get() derived class, as I expect, but then the compiler treats the return value as Base* . This is most likely due to its polymorphism at runtime. But I find it hard to believe that there will be no elegant and obvious way to do this.

Can someone advise.

Answer 1

You can try something like this:

 class Base { public: // derived classes must implement this. // the implementation is always the same code virtual type_info getType() const = 0; virtual bool isEqual(const Base& toObj) = 0; } class Der1 : Base { public: type_info getType() const { return typeid (this); } bool isEqual(const Base& toObj) { if (this.getType() == toObj.getType()) { // we have 2 instances of Der1! // do comparison here } else { // the other one is no Der1 => we are not equal return false; } } } class Der2 : Base { public: type_info getType() const { return typeid (this); } bool isEqual(const Base& toObj) { if (this.getType() == toObj.getType()) { // we have 2 instances of Der2! // do comparison here } else { // the other one is no Der1 => we are not equal return false; } } } void MyFunc() { Base* bp1; Base* bp2; // ... // this should work now (although I have not tested it!) bool theyAreEqual = bp1->isEqual(*bp2); } 

Answer 2

The equivalence relation is not suitable. std::multimap , and all ordered associative containers need to be ordered. Therefore, if this is a strict requirement, you should use an unordered container, i.e. unordered_multimap .

In any case, you need to provide a function object that takes two arguments Base* a,b and returns bool , which says a<b or a==b according to your definition.

Unfortunately, C ++ allows time search for virtual methods for only one type at a time, and here you have two. One way to limit this is the double dispatch method. So a common function object with two arguments

 struct eq { bool operator()(const Base& a, const Base& b) { return a.isEqual(b); } }; 

will eventually call the right isEqual one of the two objects, for example. Der1 definition if a is of this type. Now in Der1 general definition will be

 bool isEqual(const Base& x) { return x.isEqual(*this); } 

Unfortunately, at this point you will need to define several overloaded methods in each derived class, for example. isEqual(const Der1&) , isEqual(const Der&) , etc.

 class Der1 { // ... bool isEqual(const Base& x) { return x.isEqual(*this); } bool isEqual(const Der1& x) { ... } bool isEqual(const Der2& x) { ... } bool isEqual(const Der3& x) { ... } }; 

Note that only the first isEqual above is virtual and overrides the Base method. The rest are not virtual overloads, but the call x.isEqual(*this) will find the appropriate one, because when *this is of type Der2& , then isEqual(const Der2& x) will be preferable to isEqual(const Base& x) (and the remaining overloads, of course )

This will run smoothly, without the need for any dynamic_cast or fully executable if or switch . However, for n derived classes, you need n * (n+1) worst-case isEqual definitions (unless you use generic templates in a hierarchy and make savings).

In addition, this approach violates your requirement that “when new derived classes are added, I do not need to change or add anything.” Again, I don't know how you expected to change anything - how would you compare a new derived type?

Sorry, I don’t know a really more elegant solution. In general, I prefer static polymorphism when possible, but here you need a container of elements of the same type, so this does not apply.

Answer 3

It's pretty simple, read the comments on this code:

 class Dervived; class Base { public: /* Note: * You can get rid of those functions and use dynamic_cast instead * which might be better. See down for example. */ const Base *getBase() const { return this; } virtual const Dervived *getDervived() const { return NULL; } virtual bool operator==(const Base& other) const { printf("base call\n"); } }; class Dervived : public Base { public: const Dervived *getDervived() const { return this; } bool operator==(const Base& other) const { // case Base to Dervived here, either with dynamic_cast or C-style cast, but since you're very sure that other is Dervived, you can go for static_cast right away and no need to check for cast success. printf("dervive call\n"); } }; int main() { Base *b = new Dervived(); Base *b2 = new Dervived(); if (*b == *b2); // calls Dervived::operator== // ... /* An alternative way of casting: */ const Dervived *d = dynamic_cast<Dervived *>(b); if (d); // cast successfull /* Or use the members. */ d = b->getDervived(); if (d); } 

I prefer dynamic_cast mode, however the functions you made are completely useless, but I prefer to use such functions, like so:

 class Base { ... virtual bool isDervived() const { return false; } }; class Dervived { ... bool isDervived() const { return true; } }; 

Note You do not need to compare before casting, at least this is what I would do.

Answer 4

You can use Multiple Submissions :

The following may help (C ++ 11 required): http://ideone.com/lTsc7M

 #include <cstdint> #include <array> #include <iostream> #include <tuple> #include <type_traits> ///////////////////////// #if 1 // multiple dispatch // sequence of size_t // not in C++11 template <std::size_t ...> struct index_sequence {}; // Create index_sequence<0, > template <std::size_t N, std::size_t ...Is> struct make_index_sequence : make_index_sequence <N - 1, N - 1, Is... > {}; template <std::size_t ... Is> struct make_index_sequence<0, Is...> : index_sequence<Is...> {}; // Generic IVisitor // Do: using MyIVisitor = IVisitorTs<Child1, Child2, ...> template <typename ... Ts> class IVisitorTs; template <typename T, typename ... Ts> class IVisitorTs<T, Ts...> : public IVisitorTs<Ts...> { public: using tuple_type = std::tuple<T, Ts...>; using IVisitorTs<Ts...>::visit; virtual void visit(const T& t) = 0; }; template <typename T> class IVisitorTs<T> { public: using tuple_type = std::tuple<T>; virtual void visit(const T& t) = 0; }; namespace detail { // retrieve the index of T in Ts... template <typename T, typename ... Ts> struct get_index; template <typename T, typename ... Ts> struct get_index<T, T, Ts...> : std::integral_constant<std::size_t, 0> {}; template <typename T, typename Tail, typename ... Ts> struct get_index<T, Tail, Ts...> : std::integral_constant < std::size_t, 1 + get_index<T, Ts...>::value > {}; // retrieve the index of T in Tuple<Ts...> template <typename T, typename Tuple> struct get_index_in_tuple; template <typename T, template <typename...> class C, typename ... Ts> struct get_index_in_tuple<T, C<Ts...>> : get_index<T, Ts...> {}; // get element of a multiarray template <std::size_t I> struct multi_array_getter { template <typename T, std::size_t N> static constexpr auto get(const T& a, const std::array<std::size_t, N>& index) -> decltype(multi_array_getter<I - 1>::get(a[index[N - I]], index)) { return multi_array_getter<I - 1>::get(a[index[N - I]], index); } }; template <> struct multi_array_getter<0> { template <typename T, std::size_t N> static constexpr auto get(const T& a, const std::array<std::size_t, N>& index) -> decltype(a) { return a; } }; // Provide an implementation of visitor // by forwarding to C implementation (which may be non virtual) template <typename IVisitor, typename C, typename...Ts> struct IVisitorImpl; template <typename IVisitor, typename C, typename T, typename...Ts> struct IVisitorImpl<IVisitor, C, T, Ts...> : IVisitorImpl<IVisitor, C, Ts...> { virtual void visit(const T& t) override { C::visit(t); } }; template <typename IVisitor, typename C, typename T> struct IVisitorImpl<IVisitor, C, T> : IVisitor, C { virtual void visit(const T& t) override { C::visit(t); } }; // helper to expand child type to IVisitorImpl template <typename IVisitor, typename C> struct IVisitorImplType; template <typename ... Ts, typename C> struct IVisitorImplType<IVisitorTs<Ts...>, C> { using type = IVisitorImpl<IVisitorTs<Ts...>, C, Ts...>; }; // Create an multi array of pointer of function // (with all combinaisons of overload). template <typename Ret, typename F, typename Arg> class GetAllOverload { private: template <typename...Ts> struct Functor { // function which will be in array. static Ret call(F&f, const Arg& arg) { return call_helper(f, arg, make_index_sequence<sizeof...(Ts)>()); } private: // The final dispatched function template <std::size_t ... Is> static Ret call_helper(F&f, const Arg& arg, index_sequence<Is...>) { using RetTuple = std::tuple<Ts&...>; // static cast is suffisant if arg is the abstract type // when given arg is concrete type, reinterpret_cast is required. // TODO: build a smaller table with only possible value to avoid that return f(reinterpret_cast<typename std::tuple_element<Is, RetTuple>::type>(std::get<Is>(arg))...); } }; // helper class to create the multi array of function pointer template <std::size_t N, typename Tuple, typename...Ts> struct Builder; template <typename...Ts, typename...Ts2> struct Builder<1, std::tuple<Ts...>, Ts2...> { using RetType = std::array<Ret (*)(F&, const Arg&), sizeof...(Ts)>; static constexpr RetType build() { return RetType{ &Functor<Ts2..., Ts>::call... }; } }; template <std::size_t N, typename ...Ts, typename...Ts2> struct Builder<N, std::tuple<Ts...>, Ts2...> { template <typename T> using RecType = Builder<N - 1, std::tuple<Ts...>, Ts2..., T>; using T0 = typename std::tuple_element<0, std::tuple<Ts...>>::type; using RetType = std::array<decltype(RecType<T0>::build()), sizeof...(Ts)>; static constexpr RetType build() { return RetType{ RecType<Ts>::build()... }; } }; public: template <std::size_t N, typename VisitorTuple> static constexpr auto get() -> decltype(Builder<N, VisitorTuple>::build()) { return Builder<N, VisitorTuple>::build(); } }; template <typename Ret, typename IVisitor, typename F, std::size_t N> class dispatcher { private: std::array<std::size_t, N> index; struct visitorCallImpl { template <typename T> void visit(const T&) const { *index = get_index_in_tuple<T, IVisitor>::value; } void setIndexPtr(std::size_t& index) { this->index = &index; } private: std::size_t* index = nullptr; }; template <std::size_t I, typename Tuple> void set_index(const Tuple&t) { using VisitorType = typename IVisitorImplType<IVisitor, visitorCallImpl>::type; VisitorType visitor; visitor.setIndexPtr(index[I]); std::get<I>(t).accept(visitor); } public: template <typename Tuple, std::size_t ... Is> Ret operator () (F&& f, const Tuple&t, index_sequence<Is...>) { const int dummy[] = {(set_index<Is>(t), 0)...}; static_cast<void>(dummy); // silent the warning unused varaible constexpr auto a = GetAllOverload<Ret, F&&, Tuple>:: template get<sizeof...(Is), typename IVisitor::tuple_type>(); auto func = multi_array_getter<N>::get(a, index); return (*func)(f, t); } }; } // namespace detail template <typename Ret, typename Visitor, typename F, typename ... Ts> Ret dispatch(F&& f, Ts&...args) { constexpr std::size_t size = sizeof...(Ts); detail::dispatcher<Ret, Visitor, F&&, size> d; return d(std::forward<F>(f), std::tie(args...), make_index_sequence<size>()); } #endif // multiple dispatch #if 1 // multiple dispatch usage struct Square; struct Rect; struct Circle; using IShapeVisitor = IVisitorTs<Square, Rect, Circle>; struct IShape { virtual ~IShape() = default; virtual void accept(IShapeVisitor&) const = 0; }; struct Rect : IShape { virtual void accept(IShapeVisitor& v) const override { v.visit(*this); } }; struct Square : Rect { virtual void accept(IShapeVisitor& v) const override { v.visit(*this); } }; struct Circle : IShape { virtual void accept(IShapeVisitor& v) const override { v.visit(*this); } }; class ShapePrinter : public IShapeVisitor { public: void visit(const Rect& s) override { std::cout << "Rect"; } void visit(const Square& s) override { std::cout << "Square"; } void visit(const Circle& s) override { std::cout << "Circle"; } }; struct IsEqual { bool operator() (IShape& s1, IShape& s2) const { ShapePrinter printer; s1.accept(printer); std::cout << " != "; s2.accept(printer); std::cout << std::endl; return false; } template <typename S> bool operator() (S& s1, S& s2) const { ShapePrinter printer; s1.accept(printer); std::cout << " == "; s2.accept(printer); std::cout << std::endl; return true; } }; int main(int argc, char *argv[]) { Rect rect; Square sq; Circle c; IShape* shapes[] = { &rect, &sq, &c }; for (auto shape1 : shapes) { for (auto shape2 : shapes) { dispatch<bool, IShapeVisitor>(IsEqual(), *shape1, *shape2); } } return 0; } #endif // multiple dispatch usage