Thread: Is std::map efficient for this problem?

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391

    Is std::map efficient for this problem?

    Greetings all,

    I have an assignment where certain "paths" ( one coordinate to another ) need to eventually be processed using Dijkstra's algorithm.

    First, a collection of coordinates (stored in a queue) are processed to find any valid paths. Because of the nature of the objects in the queue, there will be possible redundant paths being found.

    A path is valid if it's "slope" is within a given range. If so, it's valid, and should be used later on (with Dijkstra's algorithm).

    My question is:

    std::map has the find() function to check if a given path is in the map. So is it efficient enough to put the paths in the std::map, using find to make sure a redundant path is NOT put in the map? Or is there possibly a more efficient data structure to use here like a matrix?

    Thank you in advance
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    A map is certainly not a bad choice, although there may be a better problem-specific method. Maybe try it with map, and leave it at that, if performance is satisfactory.

  3. #3
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    okay, so if I want to move forward using a map,

    If a map has :
    Code:
    std::map <key_type, value_type>
    And a path object looks like this:
    Code:
    class Path{
    
      public:
    
        Path( Coord init, Coord term)
        : initial( init ), terminal( term ){};
    
      private:
    
        Coord initial;
        Coord terminal;
    }:
    Is there a way that "key_type" could contain both initial and terminal, since really that is the only way to distinguish one path from another, since many paths might share one coordinate, but no two paths can share both coordinates?

    Something like:
    Code:
    std::map < string coordinate_pair, path >
    where coordinate pair is a string like:
    Code:
    "0.0 0.0 0.0 50.367 99.889 72.440"
    Is this a good approach or am I missing the point here?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You could use std::pair, but then you'll be mapping coordinates to a path, where a path is defined by its coordinates. Why not use std::set instead and define operator== and operator< for Path?
    Last edited by laserlight; 04-10-2008 at 12:45 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    I've never used a set before but I just looked it up on cplusplus.com and it looks like a much better choice. Thanks laserlight.

    Also, If I overload == and <, must I still give a comparison object in the set's constructor?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Also, If I overload == and <, must I still give a comparison object in the set's constructor?
    No, that would not be necessary.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    hmmm....

    As an example, how can I overlaod the operator== for a class where I need to consider two different values?

    As an example class:
    Code:
    class path{
    
      public:
    
        path( int init, int term )
        : initial( init ), terminal( term ){};
    
        bool operator==( const path& p ){ 
    
          return p.initial == initial;
    
          // Also need to check terminal here?
        }
    
      private:
    
        int initial;
        int terminal;
    };
    How do I check both initial and terminal values?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  8. #8
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    I'm thinking one of you clever people out there will tell me, "Aha! Hence the importance of the comparison object!"

    So I would need the comparison object, right?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I would write something like this:
    Code:
    class path {
    public:
    
        path( int init, int term )
            : initial( init ), terminal( term ){};
    
        friend bool operator==(const path& lhs, const path& rhs);
        friend bool operator<(const path& lhs, const path& rhs);
    
    private:
    
        int initial;
        int terminal;
    };
    
    bool operator==(const path& lhs, const path& rhs)
    {
        return lhs.initial == rhs.initial && lhs.terminal == rhs.terminal;
    }
    Of course, you have to decide on how to make it less than comparable, perhaps by arbitrarily comparing lhs.initial < rhs.initial || (lhs.initial == rhs.initial && lhs.terminal < rhs.terminal).

    So I would need the comparison object, right?
    A comparison object is useful when you want to compare in a way other than the default (less than with std::less). In this case you have not even defined the default.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Code:
    return lhs.initial == rhs.initial && lhs.terminal == rhs.terminal;
    Yea, this was my next question. I never wrote a return statement with logical operators in it like that. I didn't even know that was allowed!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You can have more than one return statement. Usually, if you're doing less than comparison for objects with two parts, then you compare the first piece of data. If the two values are equal, then you return the comparison of the second piece of data.

    Remember to return false if both objects have the same values for the two pieces of data (both comparisons are equal).

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You can have more than one return statement.
    Of course, but in this case I think my earlier suggestion suffices:
    Code:
    bool operator<(const path& lhs, const path& rhs)
    {
        return lhs.initial < rhs.initial
            || (lhs.initial == rhs.initial && lhs.terminal < rhs.terminal);
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I didn't even know that was allowed!
    Why wouldn't it be? Conditions of if, while and for statements are not special.
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM