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.
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.