STL map and set

[Muthuveerappan]

Hi,

I read in a book that set and map (defined in STL) elements are stored in sorted order.

Given below is a program is an attempt to test the above, but however the memory allocation of the elements seem to be in the order in which the elements are inserted.

1) Am I missing something in my program ?
2) Does the memory allocation of the elements not depend at all on the key value ?

OS - Mac OS X 10.6
Compiler - gcc version 4.2.1 (Apple Inc. build 5646)

#include <iostream>
#include <string>
#include <map>
#include <set>
using std :: cout;
using std :: endl;
using std :: set;
using std :: map;
using std :: string;

int main()
{

    system("clear");
    
    //SET
    
    set<int> s1;
    s1.insert(20);
    s1.insert(15);
    s1.insert(17);
    s1.insert(12);
    s1.insert(25);


    cout << endl
         << "Key\tAddress\n"
         << "---\t-------\n";

    for(set<int> :: const_iterator itr = s1.begin(); itr != s1.end(); itr ++)
        cout << *itr << "\t" << &(*itr) << endl;

    //MAP

    map<int, string> m1;
    
    m1[4] = "aaaa";
    m1[1] = "bbbb";
    m1[3] = "cccc";
    m1[2] = "dddd";

    cout << endl
         << "Key\tElement\tAddress1\tAddress2\n"
         << "---\t-------\t--------\t--------\n";

    for(map<int, string> :: const_iterator itr = m1.begin(); itr != m1.end(); itr ++)
        cout << itr -> first << '\t' << itr -> second << '\t' << &(itr -> first) << '\t' << &(m1[itr -> first]) << endl;
     



    return(0);
}

code output:

Key	Address
---	-------
12	0x100100130
15	0x1001000d0
17	0x100100100
20	0x1001000a0
25	0x100100160

Key	Element	Address1	Address2
---	-------	--------	--------
1	bbbb	0x1001001e0	0x1001001e8
2	dddd	0x100100280	0x100100288
3	cccc	0x100100230	0x100100238
4	aaaa	0x100100190	0x100100198

[ashukasama]

Have a look on this thread

http://www.codeguru.com/forum/showthread.php?t=179442

[Lindley]

2) Does the memory allocation of the elements not depend at all on the key value ?

Nope.....no reason it should.

[Paul McKenzie]

Given below is a program is an attempt to test the above, but however the memory allocation of the elements seem to be in the order in which the elements are inserted.

What does the memory address have to do with what order things are placed in a tree? Nothing.

To clarify, let's say I give you 10 nodes to place in a tree in order. You don't know where or how I created these nodes. You order the nodes in the tree based on the criteria I gave you. So where does the address of each of these nodes come into play when you are building the tree?

Regards,

Paul McKenzie

[Muthuveerappan]

Thanks all for your replies.

Thanks a lot Paul, Yeah I think I completely misinterpreted the author's comments.

I assumed stored in sorted order means stored in ordered memory locations. If that was case, there would have to be a lot of shuffling after the insertion of every element, which is completely wrong.

Summary
------------
The nodes are ordered based on the Compare parameter or the default < operator on the Key. it doesn't mean the memory locations of the nodes are ordered.

Thanks again

[Lindley]

That property is what makes a set or multiset more suitable than using a vector with std::sort(), if you're going to be making many insertions or deletions and you need the elements to remain sorted after every one.

[Muthuveerappan]

I suppose the elements are sorted in any case.

It is sorted based on the criteria specified in the Compare template parameter (or defaults to the < operator of the key).

So the key does play a role in sorting the nodes, like Paul had stated the nodes are sorted and not the memory location of the nodes.

[Lindley]

The only time the sorted-ness of the nodes is relevant to you as a coder is when you're iterating through the set from begin() to end(). At all other times, you really shouldn't care that much.

[Muthuveerappan]

I agree, while iterating through from begin to end, the sorting order is essential.

Thanks a lot for all your replies has been very helpful for me.