CODEWITHSUNDEEP
c++data-structuresdictionarystl
Swami
Swami

Reputation: 81

C++ data structure to perform indexed list

I am looking for the most efficient data structure to maintain an indexed list. You can easily view it interms of a STL map :

std::map<int,std::vector<int> > eff_ds;

I am using this as an example because I am currently using this setup. The operations that I would like to perform are :

I am also trying to use an unordered map and a forward list,

std::unordered_map<int,std::forward_list<int> > eff_ds;

Is this the best I could do in terms of time if I use C++ or are there other options ?

UPDATE:

I can do insertion either way - front/back as long as I do the same for all the keys. To make my problem more clear, consider the following:

At each iteration of my algorithm, I am going to have an external block give me a (key,value) - both of which are single integers - pair as an output. Of course, I will have to insert this value to the corresponding key. Also, at different iterations, the same key might be returned with different values. At the end my output data(written to a file) should look something like this:

k1: v1 v2 v3 v4
k2: v5 v6 v7
k3: v8
.
.
.
kn: vm

The number of these iterations are pretty large ~1m.

Upvotes: 0

Views: 2103

Answers (1)

harmic
harmic

Reputation: 30577

There are two dimensions to your problem:

  1. What is the best container to use where you want to be able to look up the items in the container using a numeric key, with a large number of keys, and the keys are sparse

    A numeric key might lend itself to a vector for this, however if the keys are sparsely populated that would waste a lot of memory.

    Assuming you do not want to iterate through the keys in order (which you did not state as a requirement), then an unordered_map might be the best bet.

  2. What is the best container for a list of numbers, allowing for insertion at either end and the ability to retrieve the list of numbers in order (the value type of the outer map)

    The answer to this will depend on how frequently you want to insert elements at the front. If that is commonly occurring then you might want to consider a forward_list. If you are mainly inserting on the end then a vector would be lower overhead.

Based on your updated question, since you can limit yourself to adding the values to the end of the lists, and since you are not concerned with duplicate entries in the lists, I would recommend using std::unordered_map<int,vector<int> >

Upvotes: 1

Related Questions