set of iterators

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

Ralf

 

[Alf P. Steinbach]

* 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

 

[Ralf Goertz]

* Ralf Goertz:

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

 

[Alf P. Steinbach]

* Ralf Goertz:

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


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

 

[Ralf Goertz]

* Ralf Goertz:

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

 

[Alf P. Steinbach]

* Ralf Goertz:

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