Need some advice to choose the proper container

I'm trying to design a task scheduler to a game engine. A task could be an animation, a trigger controller, etc.

开发者_运维知识库My problem is what container to choose. The idea is: when you insert a new task, the container must reorder and put the task in the proper place. Once executed, task could change and be scheduled again or deleted. This is mainly push and pop.

But, if possible, it would be nice if I could have random access to an element, but not vital. No matter if the container supports one or more elements with the same key.

I think that priority queue fits my needs but I saw that is based on vector implementation, and I think that this container must be somehow optimized to push and pop.

Opinions?

(original source: Liam Devine)

A priority queue seems to be the best option for you.

As you can see, the pop functions has a constant complexity and the push function is logarithmic in time.

std::vector is pretty good for this task, especially if the "steady-state" size of the container remains reasonably constant (you have a number of tasks on the queue doesn't differ widely).

If you need an updatable queue (and std::priority_queue is not), I would suggest you use the d_ary_heap_indirect (which can be found in the Boost.Graph "detail" folder). This is a priority queue used a lot for Dijkstra and A* algorithms that require an updatable priority queue. Random-access is necessary, anyways. Also, using an indirect makes the insertion and deletion from the queue quite efficient. Finally, you can choose your container (as a template argument), but it has to be random-access (so, you can try either vector or deque). Pop is constant-time, push and/or update is log-time, and the proper choice of container will make the container insertion constant-amortized (and the d_ary_heap_indirect amortizes a second time as well, so I wouldn't worry about that).

The vector is optimized for push and pop at one end. :-)

To prioritize you will have to sort the tasks. A vector isn't that bad, if the number of objects is reasonably small, even if it means copying objects during the sort.

Other containers, like linked lists, instead suffer from the need to allocate a new node for each object.

You can specify the container type you want with std::priority_queue. However: you're storing pointers (I presume, since it sounds like what you're is polymorphic and has identity), so copying is cheap. You're managing it as a heap (that's what std::priority_queue does), so insertions are done using push_back and a number of swaps (lg(n) max). I can't see any reason to even consider another structure than std::vector.

std::priority_queue does hide all of the direct access operators (e.g. operator[]). It does this because if you modify an entry, you're likely to invalidate the heap (which is a class invariant of the class). If you do want to provide direct read access, however, the underlying container is only protected, not private, so you can derive from it and add the operators you want. I'd very much limit it to const operators, however.

Depends on how often you're going to be adding tasks and pulling tasks off (and presumably executing them) and how many there are.

If you're going to have tons of little tasks, then prefer priority queue because the cost of node allocation will probably not hurt you as much as the asymptotic growth of n log n for the sort.

If you're going to have a small number of tasks that constantly keep changing priority, then sorting a vector might be reasonable, but you want to use an sorting algorithm that works well when the list is almost sorted.

Scheduling is an art though and you're going to have to profile it once you build it. There's probably too little information at this point so say. I'd lean towards a priority queue, but keep other options in mind if performance isn't adequate.