At least for the ordered versions (std::map
and std::set
), a map
facilitates use-cases of a set
by allowing you to introduce an external key (map::key_type
) to determine ordering of the elements that otherwise can't be derived from map
's data type (map::mapped_type
). If the ordering can be wholly derived (by comparing 2 elements) from map::mapped_type
, then you're typically better off using a set
, in which case you'll avoid duplicating the key as map::key_type
.
In a way, std::map
is redundant and you can always use std::set
instead by introducing a new element type which aggregates keys with data while providing the necessary comparison function. However, this is cumbersome and typically inelegant.
To clarify why a set
may be cumbersome over a map
; A set
will store the <key, data>
pair as an element while map
will maintain a separation between the 2. This means, for instance, that for a find
operation on a set
where find
's parameter is constructed on-the-spot, an entire <key, data>
element will have to be constructed while it's really on the key
that's needed for the find
operation. The construction of the data
members of a set
's element is then redundant, and can be rather inefficient if, for instance, data
members represent disk storage or involve some other complex or else time consuming construction operation. map
alleviates this by only having to construct the actual key
required for find
.
To summarize, consider an element <key, data>
for which you're wondering whether to use a map
or a set
to store multiple ordered elements. If key
spans the entire data
(meaning data
is empty or else key == data
) then you're better off using a set
in which case you'll avoid a) duplicating key
storage and b) likely having to keep 2 key
s synchronized. If key
is not contained in data
then (you have to) use a map
. The tricky part is when key
is a (proper) subset of data
. You then have to trade-off the cost of maintaining duplicate key
s (for a map
) vs the cost of constructing data
that doesn't overlap with key
(for a set
), the latter which may occur for find
operations.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…