CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: complexity

  1. #1
    Join Date
    Sep 2003
    Posts
    815

    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

  2. #2
    Join Date
    Nov 2003
    Location
    Vienna, Austria
    Posts
    212
    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
  •  





Click Here to Expand Forum to Full Width

Featured