-
March 29th, 2004, 04:29 AM
#1
complexity
Hello,
anyone knows the complexity of the find function
of std::hash_map & std::map
and also fot the size function & insert function for both
thanks
avi
-
March 29th, 2004, 05:18 AM
#2
std::map:
size: O(1)
find & insert: O(log n)
stdext::hash_map:
Not actually a standardized container. Anyway.
size: probably O(1), no reason not to store it in a variable
find: Theta(1), but this can go down if the map is too small or the hash function is bad. Absolute worst case is O(n).
insert: Again, Theta(1), but O(n), or worse if it's a flat hash map and poorly implemented, then it might never stop.
All the buzzt
CornedBee
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|