1

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
parreirat
  • 715
  • 3
  • 9
  • 22
  • 2
    You can just use an `std::map` or any implementation of a balanced binary tree, which gives you fast (O(logN)) access to keys, as well as ordered keys. Changing the order is simply a matter of deleting the old key and inserting the new key. – Charles Salvia Jan 05 '13 at 16:40
  • How many elements are you storing? You'd be surprises how many insert/deletes you can make in 1/60th of a second on a modern processor, if the code is otherwise reasonably well written. – Mats Petersson Jan 05 '13 at 17:07
  • And how big is each object? What are you doing with each? – Mats Petersson Jan 05 '13 at 17:28
  • Each object will be the size of a small (50 to 50px) to big (300 to 300px), with the odd big image (background). Each frame that passes I will iterate the entire map/set, grabbing it's image and coordinates. – parreirat Jan 05 '13 at 17:32
  • 1
    And what are you doing with each image? Blitting it to the screen, or something else? – Mats Petersson Jan 05 '13 at 17:46
  • How strong of a need to you have for lookup by index? There are good data structures for that. – templatetypedef Jan 05 '13 at 18:29
  • if there's a good reason to avoid it, I think I can go without it... I can do a search, and once finding what I need, store that pointer, I guess – parreirat Jan 05 '13 at 18:39

2 Answers2

8

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.

Willi Mentzel
  • 27,862
  • 20
  • 113
  • 121
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
2

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

nishantjr
  • 1,788
  • 1
  • 15
  • 39