Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > set of iterators

Reply
Thread Tools

set of iterators

 
 
Ralf Goertz
Guest
Posts: n/a
 
      04-22-2010
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
 
Reply With Quote
 
 
 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-22-2010
* 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
 
Reply With Quote
 
 
 
 
Ralf Goertz
Guest
Posts: n/a
 
      04-22-2010
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
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-22-2010
* 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
 
Reply With Quote
 
Ralf Goertz
Guest
Posts: n/a
 
      04-22-2010
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
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-22-2010
* 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
plain iterators and reverse iterators on vector subramanian100in@yahoo.com, India C++ 10 08-08-2009 08:28 AM
Using std::set::erase with iterators mathieu C++ 4 03-03-2008 02:39 PM
Iterators and reverse iterators Marcin Kaliciński C++ 1 05-08-2005 09:58 AM
Nested iterators (well, not nested exactly...) Russ Perry Jr Java 2 08-20-2004 06:51 PM
Any interest in lightweight coroutines in Java ala C# 2.0 iterators? Ken Sprague Java 4 10-28-2003 08:03 PM



Advertisments