Question on initializing STL hash-maps using Visual C++ Express

[Eric in San Diego]

Hi all -

A potential employer gave me a programming problem in C++. I've been
programming in several other languages for the past few years, but the
last time I used c++ was in school.

I installed Visual C++ Express. The IDE was pretty easy to use, and
I coded the algorithm using a hash table (er, hash map) without much
trouble. But I found that I was getting crappy performance as the
amount of input increased. Traced this to hash table performance,
which looked like it was behaving logarithmically (or worse) per the
size of the table. So I figure this is due to lots of resizing and
rehashing, and that the solution is to initialize the table to start
with a lot of buckets. I've seen code examples where hash maps are
initialized with a single numeric argument, like this:

#include <hash_map>
....
hash_map<string,int> table(1000); //use 1000 buckets
......

But Visual C++ Express does not seem to offer a constructor to do
this. When I do it anyway, I get an error. It's essentially the same
error that arises when I cut and paste code from the _C++ Cookbook_
(see below).

So here are my questions:
* Is this single-argument constructor (specifying bucket count)
standard for STL hash-maps?
* If I were to cough up the money and buy the commercial Visual Studio
for C++, would they deign to include a constructor that lets you
specify hash table size up front?
* Is there a work-around in Visual C++ Express?
* Failing that, what are my alternatives (assuming that I'm stuck in
Windows)?

Thanks,

- Eric in San Diego.


HERE'S THE ERROR MESSAGE FROM CODE TAKEN DIRECTLY FROM THE C++
COOKBOOK:

1>------ Build started: Project: HashmapTest, Configuration: Debug
Win32 ------
1> HashmapTest.cpp
1>c:\users\owner\documents\visual studio 2010\projects\hashmaptest
\hashmaptest\hashmaptest.cpp(16): error C2664:
'stdext::hash_map<_Kty,_Ty>::hash_map(const stdext::hash_map<_Kty,_Ty>
&)' : cannot convert parameter 1 from 'int' to 'const
stdext::hash_map<_Kty,_Ty> &'
1> with
1> [
1> _Kty=std::string,
1> _Ty=Session *
1> ]
1> Reason: cannot convert from 'int' to 'const
stdext::hash_map<_Kty,_Ty>'
1> with
1> [
1> _Kty=std::string,
1> _Ty=Session *
1> ]
1> No constructor could take the source type, or constructor
overload resolution was ambiguous
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped
==========

 

[Stefan van Kessel]

On 10/17/2010 3:56 PM, Eric in San Diego wrote:
[...]

I've seen code examples where hash maps are
initialized with a single numeric argument, like this:

#include<hash_map>
...
hash_map<string,int> table(1000); //use 1000 buckets
.....

Just in case somebody reading this did not know the difference, hash_map
is part of the STL but not the C++ standard library. There are no
hash_maps in the current standard but there will be in C++0x by the name
of unordered_map (the somewhat awkward name helps avoid breaking
existing code).

[...]

So here are my questions:
* Is this single-argument constructor (specifying bucket count)
standard for STL hash-maps?

According to http://www.sgi.com/tech/stl/hash_map.html there should be
in the sgi STL. In Microsoft's implementation there's no such
constructor though. (The documentation lists the available constructors
here[2])

* If I were to cough up the money and buy the commercial Visual Studio
for C++, would they deign to include a constructor that lets you
specify hash table size up front? No.
* Is there a work-around in Visual C++ Express?

You can use the C++0x unordered_map, or a different STL implementation,
or boost.unordered [1]. I don't know of a way how you can coerce the
msvc stdext::hash_map to do what you want but there might be.

--
Have a nice day,
Stefan

[1] http://www.boost.org/doc/libs/1_44_0/doc/html/unordered.html
[2] http://msdn.microsoft.com/en-us/library/8zz3703d.aspx

 

[Eric in San Diego]

Thanks!

On 10/17/2010 3:56 PM, Eric in San Diego wrote:
[...]> I've seen code examples where hash maps are

initialized with a single numeric argument, like this:

#include<hash_map>
...
hash_map<string,int>  table(1000); //use 1000 buckets
.....

Just in case somebody reading this did not know the difference, hash_map
is part of the STL but not the C++ standard library. There are no
hash_maps in the current standard but there will be in C++0x by the name
of unordered_map (the somewhat awkward name helps avoid breaking
existing code).

[...]> So here are my questions:

* Is this single-argument constructor (specifying bucket count)
standard for STL hash-maps?

According tohttp://www.sgi.com/tech/stl/hash_map.htmlthere should be
in the sgi STL. In Microsoft's implementation there's no such
constructor though. (The documentation lists the available constructors
here[2])> * If I were to cough up the money and buy the commercial Visual Studio

for C++, would they deign to include a constructor that lets you
specify hash table size up front? No.
* Is there a work-around in Visual C++ Express?

You can use the C++0x unordered_map, or a different STL implementation,
or boost.unordered [1]. I don't know of a way how you can coerce the
msvc stdext::hash_map to do what you want but there might be.

--
Have a nice day,
Stefan

[1]http://www.boost.org/doc/libs/1_44_0/doc/html/unordered.html
[2]http://msdn.microsoft.com/en-us/library/8zz3703d.aspx