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

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.

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?

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?

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?

Quote:

---

Also, If I overload == and <, must I still give a comparison object in the set's constructor?

---

No, that would not be necessary.

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?

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?

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).

Quote:

---

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.

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!

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).

Quote:

---

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:

---

I didn't even know that was allowed!

---

Why wouldn't it be? Conditions of if, while and for statements are not special.