Is there a hash algorithm with direct access to hash elements andreference count?

Discussion in 'C++' started by Bo Peng, Mar 11, 2006.

  1. Bo Peng

    Bo Peng Guest

    Dear list,

    I am looking for a way to store a large amount of unique sequences that
    will be accessed by objects. The most important operations are:

    1. Direct access to the sequences (from pointers stored in each object).
    Access through key lookup is not acceptable.

    2. Given a new sequence, determine if it is already in the factory of
    sequences. If so, increase the reference count of the existing sequence
    and use it; Otherwise, put the new sequence into the factory.

    3. If no object is using a sequence, the sequence should be removed from
    the factory.

    For the purpose of 2, I think I need a hash table algorithm. I will need
    reference count and direct access to sequences for 1 and 3. Is there an
    existing library that provide such facility? STL hash does not seem to
    work (but I am not quite sure).

    Of course, any implementation suggestion is welcome and performance is
    at the highest priority here.

    Many thanks in advance.
    Bo
    Bo Peng, Mar 11, 2006
    #1
    1. Advertising

  2. Bo Peng

    Greg Guest

    Re: Is there a hash algorithm with direct access to hash elements and reference count?

    Bo Peng wrote:
    > Dear list,
    >
    > I am looking for a way to store a large amount of unique sequences that
    > will be accessed by objects. The most important operations are:
    >
    > 1. Direct access to the sequences (from pointers stored in each object).
    > Access through key lookup is not acceptable.
    >
    > 2. Given a new sequence, determine if it is already in the factory of
    > sequences. If so, increase the reference count of the existing sequence
    > and use it; Otherwise, put the new sequence into the factory.
    >
    > 3. If no object is using a sequence, the sequence should be removed from
    > the factory.
    >
    > For the purpose of 2, I think I need a hash table algorithm. I will need
    > reference count and direct access to sequences for 1 and 3. Is there an
    > existing library that provide such facility? STL hash does not seem to
    > work (but I am not quite sure).
    >
    > Of course, any implementation suggestion is welcome and performance is
    > at the highest priority here.


    Sounds like a std::tr1::unordered_multiset would meet your
    requirements. Although whether the unordered_multiset uses
    reference-counting, multiple copies or some other mechanism to maintain
    the count of duplicate entries is not specified by the TR1 draft. And
    in fact, a unordered_multiset client is completely insulated from that
    implementation detail.

    Greg
    Greg, Mar 11, 2006
    #2
    1. Advertising

  3. Bo Peng

    Pete Becker Guest

    Re: Is there a hash algorithm with direct access to hash elementsand reference count?

    Greg wrote:
    >
    > Although whether the unordered_multiset uses
    > reference-counting, multiple copies or some other mechanism to maintain
    > the count of duplicate entries is not specified by the TR1 draft.


    A multiset can hold multiple entries that compare equal, but equal
    entries aren't necessarily the same. It depends on the equality
    operator. So, no, a multiset, unordered or otherwise, can't use
    reference counting.

    --

    Pete Becker
    Roundhouse Consulting, Ltd.
    Pete Becker, Mar 11, 2006
    #3
  4. Bo Peng

    Bo Peng Guest

    Re: Is there a hash algorithm with direct access to hash elementsand reference count?

    Pete Becker wrote:
    > A multiset can hold multiple entries that compare equal, but equal
    > entries aren't necessarily the same. It depends on the equality
    > operator. So, no, a multiset, unordered or otherwise, can't use
    > reference counting.


    Then I have to write everything from scratch? The storage and reference
    count parts seem to be easy. I just need something that will not
    re-locate itself during add/remove. What I am lacking is a quick way to
    look up a sequence. A linear 'memcmp' is not acceptable but a hash
    function is also difficult to define and implement. Any suggestion?

    Bo
    Bo Peng, Mar 11, 2006
    #4
  5. Bo Peng

    Greg Guest

    Re: Is there a hash algorithm with direct access to hash elements and reference count?

    Bo Peng wrote:
    > Pete Becker wrote:
    > > A multiset can hold multiple entries that compare equal, but equal
    > > entries aren't necessarily the same. It depends on the equality
    > > operator. So, no, a multiset, unordered or otherwise, can't use
    > > reference counting.

    >
    > Then I have to write everything from scratch? The storage and reference
    > count parts seem to be easy. I just need something that will not
    > re-locate itself during add/remove. What I am lacking is a quick way to
    > look up a sequence. A linear 'memcmp' is not acceptable but a hash
    > function is also difficult to define and implement. Any suggestion?


    You could use ref-counted shared_ptr's (again from the std::tr1
    library) to hold pointers to the sequences in the set. The set can be
    either an ordered, std::set (and would require a routine to return the
    "lesser" of two sequence pointers) or an unordered,
    std::tr1::unordered_set (which would require a routine to determine
    whether two sequence pointers are equivalent). Inserting a pointer into
    the set would also have to decrement the pointer's refcount. Futhermore
    when a shared_ptr's refcount reached 0, there would have to be some
    logic for the shared_ptr to remove itself from its container.

    Greg
    Greg, Mar 12, 2006
    #5
    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. Anan
    Replies:
    8
    Views:
    15,609
    John C. Bollinger
    Dec 8, 2004
  2. Pieter Claassen
    Replies:
    1
    Views:
    1,093
    CBFalconer
    Aug 4, 2004
  3. rp
    Replies:
    1
    Views:
    491
    red floyd
    Nov 10, 2011
  4. Arthur Chan
    Replies:
    0
    Views:
    158
    Arthur Chan
    Apr 27, 2009
  5. Robert Oschler
    Replies:
    1
    Views:
    112
    Lasse Reichstein Nielsen
    Sep 5, 2003
Loading...

Share This Page