STL map and set

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)

Code:

---

#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:

Code:

---

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

---

Have a look on this thread

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

Quote:

---

Originally Posted by Muthuveerappan

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

---

Nope.....no reason it should.

Quote:

---

Originally Posted by Muthuveerappan

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

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

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.

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.

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.

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.