What caontainer shall be used instead of std::map is there is noorders in keys?

Discussion in 'C++' started by Peng Yu, Sep 14, 2008.

  1. Peng Yu

    Peng Yu Guest

    Hi,

    Suppose I have a bunch of keys that map to some values. I can only
    compare whether two keys are equal or not but there is no order
    between different keys, that is, there is no ">" and "<" operator.

    I think sgi's hash_map can be used for this case. But it is not in C++
    standard. I'm wondering what other STL container I can use?

    Thanks,
    Peng
    Peng Yu, Sep 14, 2008
    #1
    1. Advertising

  2. Peng Yu

    Kai-Uwe Bux Guest

    Re: What caontainer shall be used instead of std::map is there is no orders in keys?

    Peng Yu wrote:

    > Hi,
    >
    > Suppose I have a bunch of keys that map to some values. I can only
    > compare whether two keys are equal or not but there is no order
    > between different keys, that is, there is no ">" and "<" operator.
    >
    > I think sgi's hash_map can be used for this case. But it is not in C++
    > standard. I'm wondering what other STL container I can use?


    The next iteration of the standard will contain unordered_map<>. It may
    serve your needs, but you will have to supply a hash-function (the standard
    will provide hash-functions for some standard types). If your
    implementation is slightly ahead of things, it may already contain
    tr1::unordered_map<>.

    Otherwise,

    std::some_sequence< pair< key_type, mapped_type > >

    comes to mind.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Sep 14, 2008
    #2
    1. Advertising

  3. Re: What caontainer shall be used instead of std::map is there isno orders in keys?

    On 2008-09-14 05:39, Peng Yu wrote:
    > Hi,
    >
    > Suppose I have a bunch of keys that map to some values. I can only
    > compare whether two keys are equal or not but there is no order
    > between different keys, that is, there is no ">" and "<" operator.


    Unless you can use unordered_map or similar, as Kai-Uwe Bux advised, you
    can always impose an artificial ordering on the keys. There are a lot of
    things that has no logical order in real life (colours for one). But as
    soon as you model them in a computer they become a pattern of bits,
    which can always be interpreted as a number.

    If you do not want your key-class to have a public < operator there is
    an (kind of ugly) trick you can use. Declare the operator private and
    make std::less<key-class> a friend. This works because std::map uses
    std::less to compare two elements, unless you tell it to use something else.

    --
    Erik Wikström
    Erik Wikström, Sep 14, 2008
    #3
  4. Peng Yu

    Peng Yu Guest

    On Sep 14, 5:27 am, Erik Wikström <> wrote:
    > On 2008-09-14 05:39, Peng Yu wrote:
    >
    > > Hi,

    >
    > > Suppose I have a bunch of keys that map to some values. I can only
    > > compare whether two keys are equal or not but there is no order
    > > between different keys, that is, there is no ">" and "<" operator.

    >
    > Unless you can use unordered_map or similar, as Kai-Uwe Bux advised, you
    > can always impose an artificial ordering on the keys. There are a lot of
    > things that has no logical order in real life (colours for one). But as
    > soon as you model them in a computer they become a pattern of bits,
    > which can always be interpreted as a number.
    >
    > If you do not want your key-class to have a public < operator there is
    > an (kind of ugly) trick you can use. Declare the operator private and
    > make std::less<key-class> a friend. This works because std::map uses
    > std::less to compare two elements, unless you tell it to use something else.


    http://www.boost.org/doc/libs/1_36_0/doc/html/unordered.html
    There is 'unordered' in boost.

    If I don't use 'unordered', I could define an artificial order by
    defining std::less<T>. The good thing of this approach is that I don't
    have specify the comparator for std::map. However, this could break
    other code. For example, I first have two double's compared, later I
    change double to std::complex<double>, which shall not be compared.
    But since I defined std::less<T> for std::complex<T>, the compiler
    would accept the code, which is wrong.

    If I could make an function object that gives artificial order, but
    then I have to specify it whenever I use std::map, which is too
    tedious.

    Since both the above approaches have shortcoming, it is then better to
    use 'unordered' if I can, right?


    Thanks,
    Peng
    Peng Yu, Sep 14, 2008
    #4
  5. Peng Yu

    James Kanze Guest

    On Sep 14, 12:27 pm, Erik Wikström <> wrote:
    > On 2008-09-14 05:39, Peng Yu wrote:
    > > Suppose I have a bunch of keys that map to some values. I
    > > can only compare whether two keys are equal or not but there
    > > is no order between different keys, that is, there is no ">"
    > > and "<" operator.


    > Unless you can use unordered_map or similar, as Kai-Uwe Bux
    > advised, you can always impose an artificial ordering on the
    > keys. There are a lot of things that has no logical order in
    > real life (colours for one). But as soon as you model them in
    > a computer they become a pattern of bits, which can always be
    > interpreted as a number.


    > If you do not want your key-class to have a public < operator
    > there is an (kind of ugly) trick you can use. Declare the
    > operator private and make std::less<key-class> a friend. This
    > works because std::map uses std::less to compare two elements,
    > unless you tell it to use something else.


    Why bother with an operator< at all? Just defined an ordering
    function (isBefore), then specialize std::less to use it.
    (You're allowed to specialize standard types and functions over
    user defined types, as long as the specialization fulfills the
    requirements of the function or type.) Or just provide some
    ordering functional object, and require the user to specify it
    when instantiating the map or the set.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Sep 14, 2008
    #5
  6. Peng Yu

    James Kanze Guest

    On Sep 14, 3:59 pm, Peng Yu <> wrote:
    > On Sep 14, 5:27 am, Erik Wikström <> wrote:
    > > If you do not want your key-class to have a public <
    > > operator there is an (kind of ugly) trick you can use.
    > > Declare the operator private and make std::less<key-class> a
    > > friend. This works because std::map uses std::less to
    > > compare two elements, unless you tell it to use something
    > > else.

    >
    > http://www.boost.org/doc/libs/1_36_0/doc/html/unordered.html
    > There is 'unordered' in boost.


    > If I don't use 'unordered', I could define an artificial order
    > by defining std::less<T>. The good thing of this approach is
    > that I don't have specify the comparator for std::map.
    > However, this could break other code. For example, I first
    > have two double's compared, later I change double to
    > std::complex<double>, which shall not be compared. But since
    > I defined std::less<T> for std::complex<T>, the compiler would
    > accept the code, which is wrong.


    Not if the user code used < for the comparison. The whole point
    of specializing std::less (rather than defining operator<) is
    that user code won't use it; it will only be used for ordering
    in containers.

    > If I could make an function object that gives artificial
    > order, but then I have to specify it whenever I use std::map,
    > which is too tedious.


    Really?

    > Since both the above approaches have shortcoming, it is then
    > better to use 'unordered' if I can, right?


    Using unordered means that you have to define a hash function,
    defining a good hash function is a lot more complex than
    defining ordering (usually), and if you provide a bad one, it
    almost certainly won't show up in your tests, but your actual
    application will run significantly slower. (Actually, it is
    possible to more or less test the quality of a hash function;
    hash a large number of random instances of your object, modulo
    something (say 100), and count each of the results. Then do
    some very simple statistical analysis on the counts. I actually
    do this when reasonable, but most people I've seen don't, and
    it's not necessarily simple to generate "random" values for many
    classes.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Sep 14, 2008
    #6
    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. Erik Arner
    Replies:
    0
    Views:
    1,311
    Erik Arner
    Nov 2, 2004
  2. Replies:
    10
    Views:
    725
    Daniel T.
    Feb 3, 2006
  3. Replies:
    10
    Views:
    776
    Jerry Coffin
    Jan 18, 2008
  4. Replies:
    1
    Views:
    420
    red floyd
    Dec 21, 2008
  5. Thomas J. Gritzan
    Replies:
    6
    Views:
    1,019
    James Kanze
    Dec 22, 2008
Loading...

Share This Page