S
Stephen Horne
Is sorting a deque using std::sort O(n log n) as for an array or
vector?
It's a fairly common problem to generate/recieve a large number of
keys and related data unordered, potentially with recurring keys, and
later on to need both to find particular keys randomly, and to iterate
through all keys in order several times.
Would your first choice be to...
1. Store the keys and data in an std::map, so that duplicate keys are
detected and handled as soon as they occur, and the data is always
sorted.
2. Store the keys and data in an std::vector or std::deque. Once all
data is in, sort it and handle duplicate keys.
3. Store the data in a priority queue. Once all data is in, extract
it in order, handling duplicate keys, writing to the container
most appropriate for later use (std::vector/std::deque/std::list).
4. Something else
Assume the data is substantial, but not enough to cause out-of-memory
problems on even quite old machines like mine. Efficiency may be an
issue, but not the only issue.
Just questioning a common habit of mine. My reflex is the first
choice, but the second/third have some appealing features WRT
separating phases of processing - first get the data, then sort/handle
duplicates/generally process the data, then use the data. With the
first approach, being forced to handle duplicate keys in the first
loop tends to mean the first two phases get merged into one.
Obviously the generating/collecting and processing of the data is
still easily separated into different functions as needed, but maybe
that splitting into phases would be better.
vector?
It's a fairly common problem to generate/recieve a large number of
keys and related data unordered, potentially with recurring keys, and
later on to need both to find particular keys randomly, and to iterate
through all keys in order several times.
Would your first choice be to...
1. Store the keys and data in an std::map, so that duplicate keys are
detected and handled as soon as they occur, and the data is always
sorted.
2. Store the keys and data in an std::vector or std::deque. Once all
data is in, sort it and handle duplicate keys.
3. Store the data in a priority queue. Once all data is in, extract
it in order, handling duplicate keys, writing to the container
most appropriate for later use (std::vector/std::deque/std::list).
4. Something else
Assume the data is substantial, but not enough to cause out-of-memory
problems on even quite old machines like mine. Efficiency may be an
issue, but not the only issue.
Just questioning a common habit of mine. My reflex is the first
choice, but the second/third have some appealing features WRT
separating phases of processing - first get the data, then sort/handle
duplicates/generally process the data, then use the data. With the
first approach, being forced to handle duplicate keys in the first
loop tends to mean the first two phases get merged into one.
Obviously the generating/collecting and processing of the data is
still easily separated into different functions as needed, but maybe
that splitting into phases would be better.