I need a hash table implementation for Cygwin

Discussion in 'C++' started by Jim Cobban, Apr 12, 2008.

  1. Jim Cobban

    Jim Cobban Guest

    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?
     
    Jim Cobban, Apr 12, 2008
    #1
    1. Advertising

  2. Jim Cobban

    Brian Tyler Guest

    On Sat, 12 Apr 2008 15:14:04 -0400, Jim Cobban wrote:

    > 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?


    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.
     
    Brian Tyler, Apr 12, 2008
    #2
    1. Advertising

  3. Jim Cobban

    Jerry Coffin Guest

    In article <ae945$480105ff$cebf3893$>,
    says...

    [ ... ]

    > 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.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Apr 12, 2008
    #3
  4. Jim Cobban

    Guest

    On 4ÔÂ13ÈÕ, ÉÏÎç3ʱ14·Ö, Jim Cobban <> wrote:
    > 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
    hash_map<string, hash> my_map;

    >
    > 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?
     
    , Apr 12, 2008
    #4
  5. Jim Cobban

    Guest

    On 4ÔÂ13ÈÕ, ÉÏÎç3ʱ14·Ö, Jim Cobban <> wrote:
    > 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.
    >
    > 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?
     
    , Apr 12, 2008
    #5
  6. Jim Cobban

    Guest

    On 4ÔÂ13ÈÕ, ÉÏÎç4ʱ38·Ö, "" <> wrote:
    > On 4ÔÂ13ÈÕ, ÉÏÎç3ʱ14·Ö, Jim Cobban <jcob...@magma..ca> wrote:
    >
    >
    >
    > > 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>)

    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;
    } // 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.
    >
    >
    >
    >
    >
    > > 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?- Òþ²Ø±»ÒýÓÃÎÄ×Ö -

    >
    > - ÏÔʾÒýÓõÄÎÄ×Ö -- Òþ²Ø±»ÒýÓÃÎÄ×Ö -
    >
    > - ÏÔʾÒýÓõÄÎÄ×Ö -
     
    , Apr 12, 2008
    #6
  7. Jim Cobban

    Jim Cobban Guest

    Jerry Coffin wrote:
    > In article <ae945$480105ff$cebf3893$>,
    > says...
    >
    > [ ... ]
    >
    >> 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.
     
    Jim Cobban, Apr 13, 2008
    #7
  8. Jim Cobban

    Brian Tyler Guest

    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.
     
    Brian Tyler, Apr 16, 2008
    #8
  9. Jim Cobban

    Jerry Coffin Guest

    In article <88a79$48025997$d1d97cb2$>,
    says...

    [ ... ]

    > 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.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Apr 17, 2008
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    461
  2. Replies:
    0
    Views:
    434
  3. WELCOME to

    , Sep 3, 2003, in forum: Python
    Replies:
    1
    Views:
    514
    Robin Becker
    Sep 5, 2003
  4. Replies:
    0
    Views:
    416
  5. rp
    Replies:
    1
    Views:
    539
    red floyd
    Nov 10, 2011
Loading...

Share This Page