Vector Vs Multimap

Question

Hi

I have a problem statement which I try to solve by two different dataset vector and multiset.

https://code.sololearn.com/cFDhDYOx4C6d/?ref=app

I did this as I could not decide which one is best for suggested problem statement.

In case of multimap, I don't have to sort it everytime. This overhead is avoided... But it's value is not modifiable and hence I had to erase and reinsert new value.

In case of vector, I don't have to reinsert / erase as it allows value to be modified... But I added overhead of sorting every time...

So I need help to decide best data structure for this problem... Share your thoughts please... If any other data structure is best or one amongst these two ?

Answer 1

Are you afraid the sorting will take too long?
If so, you could sort all values into a nested vector first. Every next vector is a new range from 2^n to 2^(n+1) - 1. This way, you can cut most of the sorting. Dividing by 2 means you move one vector back.

Answer 2

I'll try to write some code for it soon. Keep an eye out for it on my profile

Answer 3

Yeah seems so that sorting is expensive as it's in loop....

I couldn't get how to store values in nested vector.... We gonna get updated values for next vector post we update values in vector... How can we avoid this sorting... Plz elaborate so can digest

Answer 4

Hi Mathieu Asselbergs , thank you for your time and help..

I tried to go through the code .. it has so many error to compile and run the code.. wanted to check whether code works for duplicate value as input vector for example, 8 8 9... I tried to fix but couldn't get rid of those error on mob app

However, I got a bit of idea reg what you are doing... Isn't erase you introduce is costlier again ? Overhead of erase is added now....

Answer 5

Hey Ketan Lalcheta,
I fixed all the errors that were left in the code.
Sorry for the sloppy programming.

SoloLearn still isn't able to run the code, though.
Maybe an IDE on your computer can!

I don't know if erase is costly or not, but if I find the time, I'll look for solutions.