Thread: Design problem: std::map, custom key, inheritance

  1. #1
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13

    Design problem: std::map, custom key, inheritance

    I would like to derive classes from an ABC, the main difference between the children would be the key (a nested class in the ABC) to access data stored into a std::map member. Here is some test-code with comments showing the problems I encounter.

    Code:
    #include <map>
    class Base
    {
        public:
        class Key
        {
            public:
            /* virtual bool operator<(const Key&) const = 0; NOT POSSIBLE */
        };
        
        std::map<Key, double> map;
        
        /* virtual double lookup(Key&) = 0; REMAINS PURE VIRTUAL */
    };
    
    /* THIS ONE IS CALLED */
    #include <cassert>
    inline bool operator<(const Base::Key& lhs, const Base::Key& rhs)
    { assert(false); return true; }
    
    class A: public Base
    {
        public:
        class Key: public Base::Key
        {
        public:
            Key(int i = 0): i_(i) {}
    
            bool operator<(const Key& rhs) const
            { return i_ < rhs.i_; }
    
        private:
            int i_;
    
            friend bool operator<(const A::Key&, const A::Key&);
        };
    
        double lookup(Key& key)
        { return map[key]; }
    };
    
    /* NEVER CALLED */
    inline bool operator<(const A::Key& lhs, const A::Key& rhs)
    { return lhs.i_ < rhs.i_; }
    
    int main()
    {
        A a;
        A::Key k1(1);
        A::Key k2(2);
    
        a.map[k1] = 0.1;
        a.map[k2] = 0.2;
    
        return 0;
    };
    I hope the code makes it clear. I would also have methods summing all the elements of a map and that kind of things. I did not include them in the code to simplify.

    I understand that one problem comes from std::map<Key, double> where Key is not a pointer, that is probably why the operator< for the base is called, but it would be less than practical to have a std::map<Key*, double, cmp_pointees<Key> > type. I also tried this approach without much success anyway. Is there a practical solution?

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Using a pointer to Key is the only solution, but you can use a smart pointer to get rid of the memory management necessary.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I think it couldn't possibly work like this: if the map has Base::Key as key_type, you simply cannot put A::Key into it without slicing - the variable i_ is lost.

    If the map stored Base::Key* you might be able to make it work polymorphically. However, it seems that it would require a double dispatch mechanism. The map could contain A::Key's, B::Key's etc and all these would have to be comparable among themselves...

    Perhaps you could move the map into A and use A::Key as the key_type.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    I'm pretty sure you could make the Base class a template and the Key could be a template parameter. Does the Key class actually need to be defined inside the Base class?

  5. #5
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    Quote Originally Posted by anon View Post
    Perhaps you could move the map into A and use A::Key as the key_type.
    Thank you all for your input. I would actually need to define 3 keys for my program, so for now, I just do not use inheritance at all and define all 3 keys independently. It would improve clarity to say "these things are the same things" with inheritance, though. I found on the internet that a virtual operator< can be made using a double dispatch mechanism, as pointed out. But this above my C++ skills for now I think. I should check on the template-based solution, too.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Is std::map efficient for this problem?
    By dudeomanodude in forum C++ Programming
    Replies: 12
    Last Post: 04-10-2008, 02:15 PM
  2. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  3. Window message loop (Keys)
    By Blackroot in forum Windows Programming
    Replies: 3
    Last Post: 09-12-2006, 05:15 PM
  4. need help program crashing
    By tunerfreak in forum C++ Programming
    Replies: 14
    Last Post: 05-22-2006, 11:29 AM
  5. design problem
    By hannibar in forum C Programming
    Replies: 6
    Last Post: 11-17-2005, 06:22 PM

Tags for this Thread