CODEWITHSUNDEEP
algorithmdata-structures
bbtrb
bbtrb

Reputation: 4085

What datastructure to use for evaluation order of objects?

I'm trying to figure out the optimal implementation for the following problem:

Let's say we have a class A that represents a complex mathematical object and upon construction initially holds all needed intrinsic state. For every object a_i of A one can compute a final numerical value, that depends in a non-trivial way on other a_j with j < i, and a_0 is known. Moreover, the equations that lead to the final answer, require a special evaluation order and a comparison operator for the a_i can be defined.

What I want to do is to create all needed a_is first, push them into some ordered data structure and finally traverse the structure in the right order to get the final results.

Now to the real question: Which data structure do I use to implement the structure for the evaluation order in a general way? A binary heap? Or do I simply use a std::vector and sort it afterwards?

Thank you!

Upvotes: 1

Views: 132

Answers (2)

brado86
brado86

Reputation: 174

If a comparison operator (say less than) for a_i can be defined based upon the evaluation order, then a natural container would be a std::set. Traversing the map using a std::set::iterator would yield every a_i in increasing order, which would be your order of evaluation. Eg.

std::set<A> aMap;
A a_i;
... // You create the rest of the A's
aMap.insert(a_i);
aMap.insert(a_j);

for (std::set<A>::iterator aIter = aMap.begin(); aIter != aMap.end(); ++aIter) {
    // Do your evaluation
}

Upvotes: 1

regex
regex

Reputation: 3601

I would recommend using the vector, along with the swap function. Loop through every element in the array and swap with the previous element in the array if the math formula returns true.

Your loop would have to loop through every element in the vector and also have a loop inside of that the loops through all elements that are prior to the currently indexed vector item. This inner loop would contain your math formula check, i.e. the sorting logic.

Hopefully, that gives you an idea of what to do. Send me a comment if you need some pseudo code.

Upvotes: 0

Related Questions