STL multi_map entry size?

Discussion in 'C++' started by rzhu, Dec 9, 2003.

  1. rzhu

    rzhu Guest

    Hi, there

    I'm a beginer of STL and I have a question about the size of each map
    entry. I'm using STL on Linux for string search and reverse search.
    I'm using a multi_map for regular search (to handle the case of
    multiple values per key) and a map for reverse search. For both maps,
    the key and value types are 'string'. What I found out was that for
    something as simple as a 2 character key and value size, my memory
    usage is increasing at the rate of about 40 bytes per entry in the
    multi_map and about 1000 bytes per entry in the map. I'm sure
    something's not right but don't know where to start looking. Can
    anyone point me to the right direction?

    BTW, I'm using gcc 3.3.1 on linux for this program. Any suggestion is
    greatly appreciated.

    R. Zhu
    rzhu, Dec 9, 2003
    1. Advertisements

  2. rzhu

    tom_usenet Guest

    On a typical red-black tree based implementation of map, the overhead
    per node is typically: 3 pointers (to the parent and left and right
    children) and a boolean indicating colour (red or black, although a
    clever implementation might steal an unused bit from one of the
    pointers), say 16 bytes. Additionally each node might include a
    std::allocator or three (another 3-12 bytes), if the implementation
    isn't optimal.

    sizeof(string) is typically 12 to 48 (depending on presence of SSO,
    etc.), before you add the character memory (2 bytes for your thing).

    Finally, every memory allocation using ::eek:perator new has perhaps 16
    bytes of book-keeping associated with it, though this is very
    implementation dependent.

    The 1000 bytes per map entry seems high - but lets examine it:

    The sizeof the map node will be 32? + sizeof(pair<string, string>) or,
    say, 96 bytes. With allocation overhead, say 112 bytes.

    The two strings add about 20 bytes each, giving a total of 150 bytes.
    Are you sure about the 1000? How are you measuring?

    multimap is a bit different in that you get a node for a particular
    key, and then additional values for the same key incur overhead in the
    same way as a linked list of pair<key, value>. Hence it does a bit
    better on memory usage.

    I suspect I've missed some bits of overhead, but you get the general


    C++ FAQ:
    C FAQ:
    tom_usenet, Dec 10, 2003
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.