STL map (key-value pair) is a widely used data structure because it provides us key value mapping. Complexity to find and insert an element in map is log2N where N is number of elements.
But there are situations where map is not the best data structure to use so we will talk about one such situation here :
Say you want to have mapping of integer vs string e.g. roll number vs name. Many software developers use map for this mapping and think that it is a best solution because complexity to add and search an element is logN which is pretty good.
But this job could be done in complexity of O(1) by using arrays of strings where index can be used as roll number (key in map). e.g.
std::string s[20] = {student1,student2,.....};
But this solution may not work if your keys start from some very high value or there are so many insertions and deletions
But if your key starts from 0 and there are reasonable number of elements, you should definitely use it. It will improve your software's performance by many folds in terms of run-time . In one of the application, I have seen 5X improvement with this optimization. Program that used to take 60 min finished in 10-12 min.
But there are situations where map is not the best data structure to use so we will talk about one such situation here :
Say you want to have mapping of integer vs string e.g. roll number vs name. Many software developers use map for this mapping and think that it is a best solution because complexity to add and search an element is logN which is pretty good.
But this job could be done in complexity of O(1) by using arrays of strings where index can be used as roll number (key in map). e.g.
std::string s[20] = {student1,student2,.....};
But this solution may not work if your keys start from some very high value or there are so many insertions and deletions
But if your key starts from 0 and there are reasonable number of elements, you should definitely use it. It will improve your software's performance by many folds in terms of run-time . In one of the application, I have seen 5X improvement with this optimization. Program that used to take 60 min finished in 10-12 min.
No comments:
Post a Comment