If it "doesn't make sense" for one Airport
to come before another Airport
then the use of std::set<Airport>
doesn't make sense, either. This container leverages the order amount elements to locate objects in O(log(n))
operations (where n
is the size of the container). If you can identify object by identity only, the best complexity you can achieve is O(n)
. You can use a combination of std::find()
or std::find_if()
and one of the sequence containers, e.g., std::vector<Airport>
or std::deque<Airport>
.
Since you don't need to define an order in terms of operator<()
, it may be reasonable to just bring the Airport
s into some order for the purpose of locating them in a std::set<Airport>
which is done by using a different comparison function object than std::less<Airport>
. The attribute you currently have in your Airport
object don't really look like suitable keys, though. In fact, they all look as if they would be mutable, i.e., you probably wouldn't want a std::set<Airport>
anyway because you can't modify the elements in an std::set<T>
(well, at least, you shouldn't; yes, I realize that you can play tricks with mutable
but this is bound to break the order of the elements).
Based on this, I'd recommend to use a std::map<std:string, Airport>
: the std::string
is used to identify the airport, e.g., using the airport codes like "JFK"
for the John F. Kennedy Airport in New York or "LHR"
for London Heathrow. Conveniently, there is already a strict weak order defined on strings.
That said, to define a strict weak order on a set of objects O
, you need to a binary relation r(x, y)
such that the following conditions hold for elements x
, y
, and z
from O
:
- irreflexive:
r(x, x) == false
- asymmetric:
r(x, y) == true
impliesr(y, x) == false
- transitive:
r(x, y) == true
andr(y, z) == true
impliesr(x, z) == true
- incomparability:
r(x, y) == false
andr(y, x) == false
andr(y, z) == false
andr(z, y) == false
impliesr(x, z) == false
andr(z, x) == false
The first three should be simple enough. The last one is a bit odd at first but actually not that hard either: The basic idea is that the relation doesn't entirely order element but groups them into equivalent classes. If you think of the relation r
to be "smaller than" it just says that if neither x
is smaller than y
nor y
is smaller than x
, then x
and y
are equivalent. The incomparable elements are just equivalent.
The standard containers work with a strict weak order but, e.g., std::set<T>
and std::map<K, V>
keep just one version of equivalent keys. It is nice that this is sufficient but it is often simpler to just use a total order which is a strict weak order where for each pair of element x
and y
either r(x, y) == true
or r(y, x) == true
(but, due to the asymmetry not both).