set of iterators

Discussion in 'C++' started by Ralf Goertz, Apr 22, 2010.

  1. Ralf Goertz

    Ralf Goertz Guest

    Hi,

    I have a large number of objects A (about 50 Million):

    struct A {
    set<string> s;
    };

    The set A::s contains a rather small number of strings (about 100 on
    average). The number of elements in the superset of all A::s is about as
    large as the number of A's. In order to save space I use

    set<string> superset;

    and

    struct A {
    set< set<string>::iterator, IterComp> s;
    };

    However in order to do that I have to add a comparison function for
    set<string>::iterator. I chose it to be *left < *right. Is there any
    other way to do that? Especially, if the iterators were pointers then
    there should be an intrinsic order which I could use. Even if they are
    not pointers can I somehow refer to the order the iterators have in the
    superset without having to explicitely compare the strings?

    Ralf
     
    Ralf Goertz, Apr 22, 2010
    #1
    1. Advertising

  2. * Ralf Goertz:
    > Hi,
    >
    > I have a large number of objects A (about 50 Million):
    >
    > struct A {
    > set<string> s;
    > };
    >
    > The set A::s contains a rather small number of strings (about 100 on
    > average). The number of elements in the superset of all A::s is about as
    > large as the number of A's. In order to save space I use
    >
    > set<string> superset;
    >
    > and
    >
    > struct A {
    > set< set<string>::iterator, IterComp> s;
    > };
    >
    > However in order to do that I have to add a comparison function for
    > set<string>::iterator. I chose it to be *left < *right. Is there any
    > other way to do that? Especially, if the iterators were pointers then
    > there should be an intrinsic order which I could use. Even if they are
    > not pointers can I somehow refer to the order the iterators have in the
    > superset without having to explicitely compare the strings?


    It's no big deal to get a pointer from an iterator.

    &*i should work nicely (assuming all iterators point to valid data).

    And pointers can be compared willy-nilly, as you like, via std::less (but not
    via the built-in '<' operator).


    Cheers & hth.,

    - Alf
     
    Alf P. Steinbach, Apr 22, 2010
    #2
    1. Advertising

  3. Ralf Goertz

    Ralf Goertz Guest

    Alf P. Steinbach wrote:

    > * Ralf Goertz:
    >>
    >> However in order to do that I have to add a comparison function for
    >> set<string>::iterator. I chose it to be *left < *right. Is there any
    >> other way to do that? Especially, if the iterators were pointers then
    >> there should be an intrinsic order which I could use. Even if they are
    >> not pointers can I somehow refer to the order the iterators have in the
    >> superset without having to explicitely compare the strings?

    >
    > It's no big deal to get a pointer from an iterator.
    >
    > &*i should work nicely (assuming all iterators point to valid data).


    Yes thanks, that works. But the performance boost is not as big as I
    expected.

    > And pointers can be compared willy-nilly, as you like, via std::less (but not
    > via the built-in '<' operator).


    Hm, I could change the compare function to &*left < &*right. And isn't
    std::less defined using the operator "<"?

    Ralf
     
    Ralf Goertz, Apr 22, 2010
    #3
  4. * Ralf Goertz:
    > Alf P. Steinbach wrote:
    >
    >> * Ralf Goertz:
    >>> However in order to do that I have to add a comparison function for
    >>> set<string>::iterator. I chose it to be *left < *right. Is there any
    >>> other way to do that? Especially, if the iterators were pointers then
    >>> there should be an intrinsic order which I could use. Even if they are
    >>> not pointers can I somehow refer to the order the iterators have in the
    >>> superset without having to explicitely compare the strings?

    >> It's no big deal to get a pointer from an iterator.
    >>
    >> &*i should work nicely (assuming all iterators point to valid data).

    >
    > Yes thanks, that works. But the performance boost is not as big as I
    > expected.
    >
    >> And pointers can be compared willy-nilly, as you like, via std::less (but not
    >> via the built-in '<' operator).

    >
    > Hm, I could change the compare function to &*left < &*right. And isn't
    > std::less defined using the operator "<"?


    No.

    It might be implemented in terms of "<", but that's an implementation detail.

    std::less provides different guarantees from "<"; the latter is only well
    defined for comparing pointers that point within the same object (or one past
    the last element of an array).


    Cheers & hth.,

    - Alf
     
    Alf P. Steinbach, Apr 22, 2010
    #4
  5. Ralf Goertz

    Ralf Goertz Guest

    Alf P. Steinbach wrote:

    > * Ralf Goertz:
    >> Alf P. Steinbach wrote:
    >>
    >>
    >>> And pointers can be compared willy-nilly, as you like, via std::less (but
    >>> not via the built-in '<' operator).

    >>
    >> Hm, I could change the compare function to &*left < &*right. And isn't
    >> std::less defined using the operator "<"?

    >
    > No.
    >
    > It might be implemented in terms of "<", but that's an implementation detail.
    >
    > std::less provides different guarantees from "<"; the latter is only well
    > defined for comparing pointers that point within the same object (or
    > one past the last element of an array).


    Does that mean that

    http://www.cplusplus.com/reference/std/functional/less/

    has it wrong? It says

    <quote>

    This class is derived from binary_function and is defined as:

    template <class T> struct less : binary_function <T,T,bool> {
    bool operator() (const T& x, const T& y) const
    {return x<y;}
    };

    </quote>

    For me this sounds as if the standard *requires* std::less to be defined
    that way. And if it is defined like that (which is at least possible as
    you wrote) how can it provide different guaranties from "<"?

    Ralf
     
    Ralf Goertz, Apr 22, 2010
    #5
  6. * Ralf Goertz:
    > Alf P. Steinbach wrote:
    >
    >> * Ralf Goertz:
    >>> Alf P. Steinbach wrote:
    >>>
    >>>
    >>>> And pointers can be compared willy-nilly, as you like, via std::less (but
    >>>> not via the built-in '<' operator).
    >>> Hm, I could change the compare function to &*left < &*right. And isn't
    >>> std::less defined using the operator "<"?

    >> No.
    >>
    >> It might be implemented in terms of "<", but that's an implementation detail.
    >>
    >> std::less provides different guarantees from "<"; the latter is only well
    >> defined for comparing pointers that point within the same object (or
    >> one past the last element of an array).

    >
    > Does that mean that
    >
    > http://www.cplusplus.com/reference/std/functional/less/
    >
    > has it wrong? It says
    >
    > <quote>
    >
    > This class is derived from binary_function and is defined as:
    >
    > template <class T> struct less : binary_function <T,T,bool> {
    > bool operator() (const T& x, const T& y) const
    > {return x<y;}
    > };
    >
    > </quote>
    >
    > For me this sounds as if the standard *requires* std::less to be defined
    > that way. And if it is defined like that (which is at least possible as
    > you wrote) how can it provide different guaranties from "<"?


    At least what you're quoting from <url:
    http://www.cplusplus.com/reference/std/functional/less/> is incomplete wrt. the
    functionality the standard specifies.

    §20.3.3/8 guarantees a total ordering for std::less applied to pointers.

    Since this is the third time I write this in this thread, I think I'll abstain
    from repeating it even more times; it gets tiresome.


    Cheers & hth.,

    - Alf
     
    Alf P. Steinbach, Apr 22, 2010
    #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. Ken Sprague
    Replies:
    4
    Views:
    706
  2. Russ Perry Jr
    Replies:
    2
    Views:
    4,286
    Russ Perry Jr
    Aug 20, 2004
  3. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    519
    Kai-Uwe Bux
    May 8, 2005
  4. mathieu
    Replies:
    4
    Views:
    4,067
    Abhishek Padmanabh
    Mar 3, 2008
  5. , India
    Replies:
    10
    Views:
    1,103
    James Kanze
    Aug 8, 2009
Loading...

Share This Page