CODEWITHSUNDEEP
c++containers
Ricardo Alves
Ricardo Alves

Reputation: 1121

C++ Best Key-Value container sortable by value and fast access to remove

I'm currently facing a problem that may be due to my lack of experience on this types of issues.

I need a Key-Value container, with the key being a specific value that is unique and a value of a primitive type (double). My application will construct a container of this type for each candidate and will store the probability (the double value) of that candidate being recognized as a specific type (the Key value which is actually an enumeration).

I will then need this to be sorted with the highest probability and choose the highest candidate from each container while removing the selected type from each of the other containers.

thanks.

EDIT: A little more explanation on the issue.

I have a image and through Image Analysis I find on it several objects. Those objects will be matched against a type, with the algorithm returning the probability of that object being of that type. Imagine I have only 3 objects and 3 types, I will have 3 containers, one for each object:

Object A

Type 1 - 95%

Type 2 - 87%

Type 3 - 15%

Object B

Type 2 - 85%

Type 1 - 23%

Type 3 - 5%

Object C

Type 3 - 91%

Type 1 - 10%

Type 2 - 1%

As you can see, I would end with with 3 containers and I would now see who fits better of each of those types. Since the highest probability on each container is 95% (for Object A), I now will say Object A is of Type 1. I will proceed to remove all entries of that key from the other containers. Now I would have:

Object B

Type 2 - 85%

Type 3 - 5%

Object C

Type 3 - 91%

Type 2 - 1%

The operation would be repeated. The highest probability is Type 3 on Object C with 91%,so I now that Object C is of type 1. I would now remove all the candidates of type 1 of the remaining containers and would end with:

Object B

Type 2 - 85%

Object B wouldnow end with type of 2.

Upvotes: 1

Views: 370

Answers (2)

Sebastian Redl
Sebastian Redl

Reputation: 71989

You can use a completely different data storage and algorithm. Here's some pseudo-code:

let data = vector<(object ID, type, probability)>;
run image analysis and fill data;
sort data on probability descending;
let seen_types = set<type>;
let seen_objects = set<object ID>;
for each tuple (oid, type, probability) in data {
  if (seen_types contains type or seen_objects contains oid) continue;
  assign type to oid;
  insert oid into seen_objects;
  insert type into seen_types;
}

The removal operation is a waste of time. One way or the other, you need to visit every piece of data once, and rearranging your data to remove things you no longer see is far more complicated than just ignoring it as you go along. Use hash sets or possibly bit sets for the two sets (depending on the shape of your object IDs and types) which give you O(1) insertion and lookup and your algorithm is O(NlogN) in the number of data items (which is objectstypes), which is the minimum you can achieve when you need to act on sorted probabilities.

Upvotes: 1

user4222907
user4222907

Reputation:

First, store everything in a map. map<int,int> order; Then you have to iterate through your data, suppose it is a vector of maps. So you check the maximum value for a specific type within all map objects.

You need to iterate through this vector (from A to C), then you need a double/int max = 0;

for(int i = 0; i<vec[0].size(); i++)
    for(int j = 0; i<static_cast<int>(vec.size()); i++){
        max = max(max,vec[j][i]);
    }
order[i] = max;
max = 0;

I did not check everything but I hope you got an idea.

Upvotes: 1

Related Questions