Help! How to access to std::set elements?

[shuisheng]

Dear All,

std::set is sorted. So I am wondering is there any fast way to access
(sucn as random access) to its elements just like std::vector.

Assume I have a set

std::set<inta;

So I can easily get access to such as a[5].

Thanks for your help.

Shuisheng

[Victor Bazarov]

shuisheng wrote:

std::set is sorted. So I am wondering is there any fast way to access
(sucn as random access) to its elements just like std::vector.

Assume I have a set

std::set<inta;

So I can easily get access to such as a[5].

std::set<int>::iterator i = a.begin();
std::advance(i, 5);
// now use *i

'std::set' is not very suitable for random (indexed) access. Perhaps
you need to think of a different container...

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Kai-Uwe Bux]

shuisheng wrote:

Dear All,

std::set is sorted. So I am wondering is there any fast way to access
(sucn as random access) to its elements just like std::vector.

No.

Assume I have a set

std::set<inta;

So I can easily get access to such as a[5].

As far as easiness is concerned, you could use something like:
#include <set>
#include <iterator>

template < typename T, typename C, typename A >
typename std::set<T,C,A>::const_reference
n_th ( std::set<T,C,Aconst & s, typename std::set<T,C,A>::size_type n ) {
typename std::set<T,C,A>::const_iterator iter = s.begin();
std::advance( iter, n );
return ( *iter );
}

#include <iostream>

int main ( void ) {
std::set< int s;
s.insert( 5 );
s.insert( 3 );
s.insert( 7 );
std::cout << n_th( s, 1 ) << '\n';
}

For the kicks of syntactic sugar, you could write your own little adaptor to
std::set that would provide operator[] and at() based upon this idea.
If the set implementation of your STL keeps track of subtree sizes, it could
be that advance is specialized so that it takes logarithmic time. I doubt,
however, that this is done in any of the usual implementations: most users
would not benefit but all would bear the costs. Most likely, std::advance()
will be linear for set iterators.
Best

Kai-Uwe Bux