Re: Fast STL data structure
* Dave Steffen:
tim.lino@gmail.com writes:
Hello,
I would like to use C++ STL to store a set of Object's which is as
follows:
class Object
{
public:
int value;
......
}
I need to perform the following actions:
1. Sort Objects in the increasing order of their "value".
2. After sorting, I need to randomly access some of the Objects.
As I know, vector is very efficient in random access. However, sorting
vector of size n takes O(nlog n) time which is not good.
A point: _all_ sorting operations are O(n log n). You just can't do
any better.
Although off-topic in clc++m, this urban myth (an over-generalization of
a basic result) should not be propagated, so:
The O(n log n) limit is for random data, with enough of it, on a
sequential machine. Theoretically it stems from the fact that n items
can be arranged in n! ways, and n^n <= n!^2 <= (n^2)^n. Now just take
logs to find the number of bits needed to represent a permutation, which
is the same as the number of binary choices needed to select one.
As soon as you can make assumptions about the data, or can establish
properties of the data, you can do better (let's not discuss advanced
computer architectures). The most trivial example is when you know the
data is already sorted, yielding O(1) sorting time. As a more
practically useful example, a least significant digit radix sort has
sorting time O(nk), where k is the length of a key.
What you _can_ do is reduce the constants in front of
the n log n, by using well-implemented libraries, and being clever.
Being clever is in general not very clever...
For example, in Effective STL, Scott Meyers points out an
alternative to using sets (and maps) that, given certain usage
patterns, can provide significant run-time advantages. (If you
haven't read Effective STL, you should.)
The OP's problem is trivially solved by using std::map. He just needs
to provide a strict weak ordering, operator<, for his Object class.
Before optimizing or even thinking about it, measure.
----------------------------------------------------------------------
Dave Steffen, Ph.D. Disobey this command!
Software Engineer IV - Douglas Hofstadter
Numerica Corporation
dg@steffen a@t numerica d@ot us (remove @'s to email me)
Please use a proper signature delimiter (two dashes followed by space,
with nothing else on that line).
Oh well, I'll never get a PhD, nor a job with Numerica Corporation, I'm
sure. :-)
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?