STL, hash_map is sorted !!

STL, hash_map is sorted !!

[Mohammad Shojatalab]

Hi  There,

I am trying to make use of hash_map from STL, and I was assuming that 
hash_map doesn't sort the (key, value) pairs and keep the
pairs in the order I inserted them into the hash_map.

This is the simple program:

#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

typedef vector<int> cvCodes;
typedef hash_multimap<int, std::string> cvValues;

int main()
{
 cvCodes items;
 cvValues itemsvalues;
 cvValues::iterator pos;

 itemsvalues.insert(make_pair(3,"Z"));
 itemsvalues.insert(make_pair(1,"C"));
 itemsvalues.insert(make_pair(2,"A"));

 for (pos = itemsvalues.begin(); pos != itemsvalues.end(); pos++)
   cout << pos->first << "  " << pos->second << endl;

return 0;
}

I was expecting to see the following output:

3  Z
1  C
2  A

but instead I get this one:

1  C
2  A
3  Z

I need to use a container which keeps the order of thing as I insert them.

Im using gcc version 4.0.2 20051125 (Red Hat 4.0.2-8)
on Linux   2.6.14-1.1653_FC4smp

I appreciate any help.

Thanks
Mohammad

Re: STL, hash_map is sorted !!

[Noel Yap]

By definition, hash_map is _not_ sorted and _not_ ordered.  Your
example may have just lucked out.  Try larger numbers.

If you want to keep the order, use std::vector< std::pair<> > or
std::deque< std::pair<> >.  If you know how many elements you'll have,
you can also try boost::array< std::pair<> >.

HTH,
Noel

On 6/26/06, Mohammad Shojatalab <shoja@ebi.ac.uk> wrote:
> Hi  There,
>
> I am trying to make use of hash_map from STL, and I was assuming that
> hash_map doesn't sort the (key, value) pairs and keep the
> pairs in the order I inserted them into the hash_map.
>
> This is the simple program:
>
> #include <ext/hash_map>
>
> using namespace std;
> using namespace __gnu_cxx;
>
> typedef vector<int> cvCodes;
> typedef hash_multimap<int, std::string> cvValues;
>
> int main()
> {
>  cvCodes items;
>  cvValues itemsvalues;
>  cvValues::iterator pos;
>
>  itemsvalues.insert(make_pair(3,"Z"));
>  itemsvalues.insert(make_pair(1,"C"));
>  itemsvalues.insert(make_pair(2,"A"));
>
>  for (pos = itemsvalues.begin(); pos != itemsvalues.end(); pos++)
>    cout << pos->first << "  " << pos->second << endl;
>
> return 0;
> }
>
> I was expecting to see the following output:
>
> 3  Z
> 1  C
> 2  A
>
> but instead I get this one:
>
> 1  C
> 2  A
> 3  Z
>
> I need to use a container which keeps the order of thing as I insert them.
>
> Im using gcc version 4.0.2 20051125 (Red Hat 4.0.2-8)
> on Linux   2.6.14-1.1653_FC4smp
>
> I appreciate any help.
>
> Thanks
> Mohammad
>
>
>

Re: STL, hash_map is sorted !!

[Brian Budge]

Have you tried longer examples?  I highly doubt that, in general, the
hash_map will keep sorted order.  I would guess this is a fluke.

Stick to containers built on balanced binary search trees (such as map).

  Brian

On 6/26/06, Mohammad Shojatalab <shoja@ebi.ac.uk> wrote:
> Hi  There,
>
> I am trying to make use of hash_map from STL, and I was assuming that
> hash_map doesn't sort the (key, value) pairs and keep the
> pairs in the order I inserted them into the hash_map.
>
> This is the simple program:
>
> #include <ext/hash_map>
>
> using namespace std;
> using namespace __gnu_cxx;
>
> typedef vector<int> cvCodes;
> typedef hash_multimap<int, std::string> cvValues;
>
> int main()
> {
>  cvCodes items;
>  cvValues itemsvalues;
>  cvValues::iterator pos;
>
>  itemsvalues.insert(make_pair(3,"Z"));
>  itemsvalues.insert(make_pair(1,"C"));
>  itemsvalues.insert(make_pair(2,"A"));
>
>  for (pos = itemsvalues.begin(); pos != itemsvalues.end(); pos++)
>    cout << pos->first << "  " << pos->second << endl;
>
> return 0;
> }
>
> I was expecting to see the following output:
>
> 3  Z
> 1  C
> 2  A
>
> but instead I get this one:
>
> 1  C
> 2  A
> 3  Z
>
> I need to use a container which keeps the order of thing as I insert them.
>
> Im using gcc version 4.0.2 20051125 (Red Hat 4.0.2-8)
> on Linux   2.6.14-1.1653_FC4smp
>
> I appreciate any help.
>
> Thanks
> Mohammad
>
>
>

Re: STL, hash_map is sorted !!

[Mohammad Shojatalab]

Thanks  for your answers,

Yes, Actually what I needed was std::vector< std::pair<> >


Cheers
Mo
Noel Yap wrote:

> By definition, hash_map is _not_ sorted and _not_ ordered.  Your
> example may have just lucked out.  Try larger numbers.
>
> If you want to keep the order, use std::vector< std::pair<> > or
> std::deque< std::pair<> >.  If you know how many elements you'll have,
> you can also try boost::array< std::pair<> >.
>
> HTH,
> Noel
>
> On 6/26/06, Mohammad Shojatalab <shoja@ebi.ac.uk> wrote:
>
>> Hi  There,
>>
>> I am trying to make use of hash_map from STL, and I was assuming that
>> hash_map doesn't sort the (key, value) pairs and keep the
>> pairs in the order I inserted them into the hash_map.
>>
>> This is the simple program:
>>
>> #include <ext/hash_map>
>>
>> using namespace std;
>> using namespace __gnu_cxx;
>>
>> typedef vector<int> cvCodes;
>> typedef hash_multimap<int, std::string> cvValues;
>>
>> int main()
>> {
>>  cvCodes items;
>>  cvValues itemsvalues;
>>  cvValues::iterator pos;
>>
>>  itemsvalues.insert(make_pair(3,"Z"));
>>  itemsvalues.insert(make_pair(1,"C"));
>>  itemsvalues.insert(make_pair(2,"A"));
>>
>>  for (pos = itemsvalues.begin(); pos != itemsvalues.end(); pos++)
>>    cout << pos->first << "  " << pos->second << endl;
>>
>> return 0;
>> }
>>
>> I was expecting to see the following output:
>>
>> 3  Z
>> 1  C
>> 2  A
>>
>> but instead I get this one:
>>
>> 1  C
>> 2  A
>> 3  Z
>>
>> I need to use a container which keeps the order of thing as I insert 
>> them.
>>
>> Im using gcc version 4.0.2 20051125 (Red Hat 4.0.2-8)
>> on Linux   2.6.14-1.1653_FC4smp
>>
>> I appreciate any help.
>>
>> Thanks
>> Mohammad
>>
>>
>>