CODEWITHSUNDEEP
c++data-structures
parreirat
parreirat

Reputation: 715

Fast, sorted data structure with random access?

I want to add several objects in a structure which allows this:

  1. Insertion of objects, immediately ordering the entire structure on add so I have a descending ordering of an int;

  2. Being able to change the int by which the objects are ordered (I mean: say that object number 2, now has a int of 5, so it reorders the structure);

  3. Fast structure, because it will be completely iterated 60 times a second;

  4. Being able to directly access the objects by position;

  5. Only needs to be iterated from top to bottom: higher INT to lower INT

  6. No deletion required, but could become useful later on.

Some indications on how to use the structure would be great, since I don't know much about the C++ standard libraries.

Upvotes: 1

Views: 3651

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

All of the operations that you've listed (except for lookup by index) can be supported by a standard binary search tree, keyed by integer values. This gives you the ability to iterate over the elements in sorted order and to keep the objects sorted during any insertion. As @njr mentioned, you can also update priorities by removing objects from the binary search tree, changing their priority, then reinserting them into the binary search tree.

To support random access by index, you should consider looking into order statistic trees, a variant on binary search trees that in addition to all other operations supports very fast (O(log n)) lookup of an element by its index. That is, you could very efficiently query for the 15th element in the sorted sequence, or the 17th, etc. Order statistic trees aren't part of the C++ standard libraries, but this older question contains answers that can link you to an implementation.

Upvotes: 8

nishantjr
nishantjr

Reputation: 1820

Use a set or a map

For requirement 1 - provide a custom sorting function

For 2 - remove the item and add it again (or provide a wrapper that does that)

3 doesn't make sense (How big is the list, how fast is the processor/ram)

For 4 - Are you sure you need that? It seems to be kind of weird to try to access it by position when the position can change suddenly (some item was added or removed)

5 - same as 1

Upvotes: 2

Related Questions