I need a hash table implementation for Cygwin

J

Jim Cobban

I am writing a program in which I need a hash table implementation of a
Map. The version of g++ available for Windo$e does not yet include the
TR1 support for this. It just has the original SGI implementation.
However the SGI implementation is so old that it predates the STL, so it
does not, among other things, include hash support for std::basic_string.

So I tried implementing the hash map from Stroustrup 3rd edition. At
the least I thought this would be a useful learning experience about
template programming. However even after I correct all of the typos I
can identify or which are described in postings I still cannot get it to
compile. Of course template error messages never provide much guidance
on how to resolve the issues so I am getting a little frustrated.

For example I have succeeded in getting a specialization for the hash
functor for std::string to compile, but I cannot get the more general
specialization for std::basic_string<C> to compile.

// this compiles
size_t hash<string>:: operator() (string const & key) const
{
size_t res = 0;
string:: const_iterator p = key.begin();
string:: const_iterator end = key.end();
while (p != end)
res = (res << 1)^*p++;
return res;
} // hash(string)

// this doesn't
template <class C>
size_t hash<basic_string<C> >:: operator() (basic_string<C> const & key)
const
{
size_t res = 0;
basic_string<C>:: const_iterator p = key.begin();
basic_string<C>:: const_iterator end = key.end();
while (p != end)
res = (res << 1)^*p++;
return res;
} // hash(basic_string<C>)

But even if I skip over that, since my specific application does not
need the more general case, as soon as I instantiate an instance I get a
flood of errors. Including:

If in my implementation of the hash table I code:

hash(key)

I get an error that I have to specify the class instance, which I did
not expect, but if I try to make the compiler happy by coding:

hash<Key>(key)

I get: error: no matching function for call to `GedCom::
hash<std::string>:: hash(std::string&)'

All I really would prefer to do is invoke the TR1 implementation which
Cygnus hasn't gotten around to incorporating yet. So what is your
advice on how to get this to work?

Specifically is there some place where I can get a pre-built Windo$e
implementation of g++ that includes TR1?
 
B

Brian Tyler

I am writing a program in which I need a hash table implementation of a
Map. The version of g++ available for Windo$e does not yet include the
TR1 support for this. It just has the original SGI implementation.
However the SGI implementation is so old that it predates the STL, so it
does not, among other things, include hash support for
std::basic_string.

So I tried implementing the hash map from Stroustrup 3rd edition. At
the least I thought this would be a useful learning experience about
template programming. However even after I correct all of the typos I
can identify or which are described in postings I still cannot get it to
compile. Of course template error messages never provide much guidance
on how to resolve the issues so I am getting a little frustrated.

For example I have succeeded in getting a specialization for the hash
functor for std::string to compile, but I cannot get the more general
specialization for std::basic_string<C> to compile.

// this compiles
size_t hash<string>:: operator() (string const & key) const {
size_t res = 0;
string:: const_iterator p = key.begin(); string:: const_iterator end =
key.end(); while (p != end)
res = (res << 1)^*p++;
return res;
} // hash(string)

// this doesn't
template <class C>
size_t hash<basic_string<C> >:: operator() (basic_string<C> const & key)
const
{
size_t res = 0;
basic_string<C>:: const_iterator p = key.begin();
basic_string said:
const_iterator end = key.end(); while (p != end)
res = (res << 1)^*p++;
return res;
} // hash(basic_string<C>)

But even if I skip over that, since my specific application does not
need the more general case, as soon as I instantiate an instance I get a
flood of errors. Including:

If in my implementation of the hash table I code:

hash(key)

I get an error that I have to specify the class instance, which I did
not expect, but if I try to make the compiler happy by coding:

hash<Key>(key)

I get: error: no matching function for call to `GedCom::
hash<std::string>:: hash(std::string&)'

All I really would prefer to do is invoke the TR1 implementation which
Cygnus hasn't gotten around to incorporating yet. So what is your
advice on how to get this to work?

Specifically is there some place where I can get a pre-built Windo$e
implementation of g++ that includes TR1?

Boost has a full implementation of TR1 plus a lot more

http://www.boost.org/doc/libs/1_35_0/doc/html/boost_tr1.html

Just install that and include those headers.
 
J

Jerry Coffin

[ ... ]
All I really would prefer to do is invoke the TR1 implementation which
Cygnus hasn't gotten around to incorporating yet. So what is your
advice on how to get this to work?

Specifically is there some place where I can get a pre-built Windo$e
implementation of g++ that includes TR1?

Yes. ConceptG++ (Boostcon edition) includes TR1.

http://www.generic-programming.org/software/ConceptGCC/download.php

As a bonus, this is based on gcc 4.3.0, which is substantially newer
than most other builds for Windows.

This also includes a number of features new to C++ 0x, obviously
including concepts, but also including some other things like delegating
constructors and rvalue-references.
 
K

kepeng

I am writing a program in which I need a hash table implementation of a
Map. The version of g++ available for Windo$e does not yet include the
TR1 support for this. It just has the original SGI implementation.
However the SGI implementation is so old that it predates the STL, so it
does not, among other things, include hash support for std::basic_string.

So I tried implementing the hash map from Stroustrup 3rd edition. At
the least I thought this would be a useful learning experience about
template programming. However even after I correct all of the typos I
can identify or which are described in postings I still cannot get it to
compile. Of course template error messages never provide much guidance
on how to resolve the issues so I am getting a little frustrated.

For example I have succeeded in getting a specialization for the hash
functor for std::string to compile, but I cannot get the more general
specialization for std::basic_string<C> to compile.

// this compiles
size_t hash<string>:: operator() (string const & key) const
{
size_t res = 0;
string:: const_iterator p = key.begin();
string:: const_iterator end = key.end();
while (p != end)
res = (res << 1)^*p++;
return res;

} // hash(string)

// this doesn't
template <class C>
size_t hash<basic_string<C> >:: operator() (basic_string<C> const & key)
const
{
size_t res = 0;
basic_string<C>:: const_iterator p = key.begin();
basic_string<C>:: const_iterator end = key.end();
while (p != end)
res = (res << 1)^*p++;
return res;

} // hash(basic_string<C>)

But even if I skip over that, since my specific application does not
need the more general case, as soon as I instantiate an instance I get a
flood of errors. Including:

If in my implementation of the hash table I code:

hash(key)
hash is a functor class, you should use its instance. for example:
hash()(key);
or
hash fun;
fun(key);
or
 
K

kepeng

I am writing a program in which I need a hash table implementation of a
Map. The version of g++ available for Windo$e does not yet include the
TR1 support for this. It just has the original SGI implementation.
However the SGI implementation is so old that it predates the STL, so it
does not, among other things, include hash support for std::basic_string.

So I tried implementing the hash map from Stroustrup 3rd edition. At
the least I thought this would be a useful learning experience about
template programming. However even after I correct all of the typos I
can identify or which are described in postings I still cannot get it to
compile. Of course template error messages never provide much guidance
on how to resolve the issues so I am getting a little frustrated.

For example I have succeeded in getting a specialization for the hash
functor for std::string to compile, but I cannot get the more general
specialization for std::basic_string<C> to compile.

// this compiles
size_t hash<string>:: operator() (string const & key) const
{
size_t res = 0;
string:: const_iterator p = key.begin();
string:: const_iterator end = key.end();
while (p != end)
res = (res << 1)^*p++;
return res;

} // hash(string)

// this doesn't
template <class C>
size_t hash<basic_string<C> >:: operator() (basic_string<C> const & key)
const
{
size_t res = 0;
basic_string<C>:: const_iterator p = key.begin();
basic_string<C>:: const_iterator end = key.end();
while (p != end)
res = (res << 1)^*p++;
return res;

} // hash(basic_string<C>)
I can not see why this template doesn't work.
Which compiler do you use? Does it support partial specialization?
Maybe you should post the error message from compiler.
 
K

kepeng

ok, the following should work.
you should do the specialization for the class, not for the member
function.

template<class C>
class hash<basic_string<C> >
{
public:
size_t operator() (basic_string<C> const & key) const ;
};

// this doesn't
template <class C>
size_t hash<basic_string<C>>::eek:perator() (basic_string<C> const & key)
const
{
size_t res = 0;
basic_string<C>::const_iterator p = key.begin();
basic_string<C>::const_iterator end = key.end();
while (p != end)
res = (res << 1)^*p++;
return res;
 
J

Jim Cobban

Jerry said:
[ ... ]
All I really would prefer to do is invoke the TR1 implementation which
Cygnus hasn't gotten around to incorporating yet. So what is your
advice on how to get this to work?

Specifically is there some place where I can get a pre-built Windo$e
implementation of g++ that includes TR1?

Yes. ConceptG++ (Boostcon edition) includes TR1.

http://www.generic-programming.org/software/ConceptGCC/download.php

As a bonus, this is based on gcc 4.3.0, which is substantially newer
than most other builds for Windows.

This also includes a number of features new to C++ 0x, obviously
including concepts, but also including some other things like delegating
constructors and rvalue-references.
My primary desire is to write programs that are as portable as possible
between development platforms. This, for example, is a major reason
that I do not use Visual C++ or Borland C++; by their code building
techniques they lock you into their product. ConceptGcc is a wonderful
idea, but it is not standards compliant. If I implement my programs
under ConceptGcc then they are locked into ConceptGcc, which is
antithetical to my objective.

I should have mentioned that I am running g++ under Eclipse, both under
Windo$e and on Ubuntu. On Ubuntu I have no problem because the version
of g++ installed there includes an implementation of TR1. However I
want to be able to implement both Linux and Windo$e versions of the
applications I write. When I go to boost.org to see how to use the
boost libraries with Eclipse I find, for example:

"It is quite simple to make in place.

"You just have to put bjam in your path, replace the default make tools
"(make in eclipse) by bjam, and after you define target to be launch with
"bjam, that's all :)

"Be sure to have at least a Jamfile in your project root in eclipse, and
"lauching bjam through eclipse as the same effet than launching it in a
"command line...

Which leaves me wondering ... where does the jamfile come from? The
Eclipse CDT creates a makefile as required, but I would not expect it to
understand jamfiles.

Which brings me back to my basic issue that all I really want, for now,
is TR1, just TR1 with no potential extensions, however attractive, that
might tempt me into writing non-compliant code, in the simplest possible
way.
 
B

Brian Tyler

I think the idea is that the JAM file probably gives eclipse knowledge
about boost libraries for some sort of code completion or something.

You don't need to do that stuff to use the libraries and they will be as
cross compiler compliant as possible.
 
J

Jerry Coffin

[ ... ]
My primary desire is to write programs that are as portable as possible
between development platforms. This, for example, is a major reason
that I do not use Visual C++ or Borland C++; by their code building
techniques they lock you into their product. ConceptGcc is a wonderful
idea, but it is not standards compliant. If I implement my programs
under ConceptGcc then they are locked into ConceptGcc, which is
antithetical to my objective.

ConceptG++ is probably the closest thing there is to a compiler that
conforms with the upcoming C++ 0x standard. Unfortunately, conforming
with the upcoming standard (or even the current) standard doesn't really
help portability much -- the only compiler that makes a serious attempt
at conforming with the current standard is Comeau. Right now, Comeau and
ConceptG++ seem to be about the only ones even making an attempt at
adding the features of the new standard.
I should have mentioned that I am running g++ under Eclipse, both under
Windo$e and on Ubuntu. On Ubuntu I have no problem because the version
of g++ installed there includes an implementation of TR1. However I
want to be able to implement both Linux and Windo$e versions of the
applications I write. When I go to boost.org to see how to use the
boost libraries with Eclipse I find, for example:

G++ is about as non-standard as any of the others. If you're only
interested in portability to other ports of G++, that's no problem at
all. If you want portability to other compilers, you need to be at least
as careful with it as with Borland, Microsoft, or any of the others.

[ ... ]
Which brings me back to my basic issue that all I really want, for now,
is TR1, just TR1 with no potential extensions, however attractive, that
might tempt me into writing non-compliant code, in the simplest possible
way.

You'll probably need to learn to live with the fact that everything has
extensions, and it's up to you to control any temptations you might
experience.

My own approach has been to typically have three or more compilers
installed all the time, and compile most code with at least a couple of
them. As noted above, if you want a "reference" level compiler, Comeau
is probably the one for the current standard. If you want something to
at least give an idea about the upcoming C++ 0x standard, both Comeau
and ConceptG++ have some features, though in that regard I think
ConceptG++ is ahead at the moment.
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top