CODEWITHSUNDEEP
c++
Guillaume Paris
Guillaume Paris

Reputation: 10539

which data structure for a list of object with fast lookup feature

I have a data structure and have to perform lookup on it, I would like to optimize things...

struct Data
{
 std::string id_;
 double data_;
};

I use currently a std::vector<Data> and std::find algorithm but I'm wondering if another data structure would be more convenient :

EDIT:

Each time I receive a message from network I have to lookup into this vector (with id as key), and update/retrieve some informations. (Data structure have more fields than in my example)

EDIT2:

Upvotes: 2

Views: 2385

Answers (2)

user2100815
user2100815

Reputation:

It really depends on your requirements, but two possibilities are to sort your vector and do a binary search, or to use a map. Both can be implemented within about 15 minutes, so I suggest you try both of them.

Edit: Given your requirement that you want to add and remove things often, and the size of your data, I'd use an unordered_map (i.e. a hash table) as the first try. You can always change to another container later.

Upvotes: 4

Gorpik
Gorpik

Reputation: 11028

It depends on whether you care about the order of the elements in your container or not. If you do care, you can do no better than now. If you don't, a hashed container should provide the fastest lookup.

But it also depends on other factors. For instance, if you create the container once and never change it, then maybe an ordered vector, with binary search, will be best.

Upvotes: 1

Related Questions