space complexity of a map

[hopesfall]

What would the worst, average and best case space complexity be for a data structure of type map<string, vector<int> > in big O notation? I'm parsing through a document and storing each word as a key and im attaching an associated int (in a vector) to it as the value.

Thanks

[naraku9333]

It depends on the operation, http://www.cplusplus.com/reference/map/map/ gives the time (not space) complexity for each function.

[hopesfall]

yeah, I saw that page had time listed but I'm looking for space :\.

[TheIdeasMan]

It's impossible to say for each of these cases - it depends entirely on the words in the file. Imagine you have one file made from a Computer Science text book (sans the code), and another from the Bible - the word frequencies are going to be rather different I think.

Why does it matter for you? Your data structure contains a vector, so this can grow to the worst case scenario.

As I pointed out in one of your other threads (I wish you wouldn't keep making new ones about the same subject), analysis of data structures & algorithms is often very complicated for real world situations.

Any way how is your Word Storage program going? Hope you had some fun & learnt some stuff - Cheers.

[hopesfall]

Thanks for replying again, TheIdeasMan. It's just been so long since I've used c++ and the assignment served as a refresher for us. I am finished now and I did relearn some things I had forgotten.

Thanks for your replies