> There is a set::insert where you can pass in a hint iterator, I wish
> there was a set::find version that took hint(s). Basically I have
> have two sets - one big set and one fairly small set. I am trying to
> do a set intersection. Both are sets of strings. The small set
> contains strings all with the same prefix. Eg. all have the prefix
> "foo" for instance. It would be great if I could pass a hint to find
> or even better if I could pass an upper and lower bounds - so find
> could possibly take advantage of the information that I have passed
> in.

>> There is a set::insert where you can pass in a hint iterator, I wish
>> there was a set::find version that took hint(s). Basically I have
>> have two sets - one big set and one fairly small set. I am trying to
>> do a set intersection. Both are sets of strings. The small set
>> contains strings all with the same prefix. Eg. all have the prefix
>> "foo" for instance. It would be great if I could pass a hint to find
>> or even better if I could pass an upper and lower bounds - so find
>> could possibly take advantage of the information that I have passed
>> in.

>
> You can try 2 optimizations.
>
> 1. Find intersection for your small set and subset of large set.
> Subset is found with the help of lower_bound and upper_bound.
> Unfortunately, you have to create temporary set in this case.
> 2. Use alternative intersection algorithm with complexity
> O(log(size_of_set1) * size_of_set2).
> ...

> The above looks great - except I have one question here..
> The creation of:
>
> Set sub(
> big.lower_bound(*small.begin()),
> big.upper_bound(*small.rbegin()));
>
> This could be somewhat expensive.
>
> If C++ had idea of subsets of a set that did not have to copy
> to create the new set this would be perfect.

> // complexity is O(log(e1 - b1) * (e2 - b2))
> template
> void log_intersection(RA1 b1, RA1 e1,
> RA2 b2, RA2 e2, Out out)
> {
> for (; b2 != e2; ++b2)
> if (binary_search(b1, e1, *b2))
> *out++ = *b2;
> }

> In article <1185362774.896921.277...@o61g2000hsh.googlegroups.com>,
>
> <"Roman.Perepeli...@gmail.com"> wrote:

>> // complexity is O(log(e1 - b1) * (e2 - b2))
>> template
>> void log_intersection(RA1 b1, RA1 e1,
>> RA2 b2, RA2 e2, Out out)
>> {
>> for (; b2 != e2; ++b2)
>> if (binary_search(b1, e1, *b2))
>> *out++ = *b2;
>> }

>
> what makes you think that this is faster std::set_intersection?
> its slower!! set_intersection be faster since log2(N1) > 1.

>> The above looks great - except I have one question here..
>> The creation of:

>

>> Set sub(
>> big.lower_bound(*small.begin()),
>> big.upper_bound(*small.rbegin()));

>

>> This could be somewhat expensive.

>

>> If C++ had idea of subsets of a set that did not have to copy
>> to create the new set this would be perfect.

>
> You are right, this copy can be expensive. But if 'small' contains
> only a few objects, and sub contains only a few objects, then it
> can be faster than other solutions.
>
> std::set is odd thing. Range [s.begin(), s.end()) is always sorted,
> but you can't use effective std::lower_bound or std::binary_search ...

>> In article <1185362774.896921.277...@o61g2000hsh.googlegroups.com>,
>>
>> <"Roman.Perepeli...@gmail.com"> wrote:

>>> // complexity is O(log(e1 - b1) * (e2 - b2))
>>> template

>> In article <1185362774.896921.277...@o61g2000hsh.googlegroups.com>,
>>
>> <"Roman.Perepeli...@gmail.com"> wrote:

>>> // complexity is O(log(e1 - b1) * (e2 - b2))
>>> template
>>> void log_intersection(RA1 b1, RA1 e1,
>>> RA2 b2, RA2 e2, Out out)
>>> {
>>> for (; b2 != e2; ++b2)
>>> if (binary_search(b1, e1, *b2))
>>> *out++ = *b2;
>>> }

>> what makes you think that this is faster std::set_intersection?
>> its slower!! set_intersection be faster since log2(N1) > 1.

>
> std::set_intersection complexity is O(N1 + N2). Complexity of
> log_intersection is log(N1) * N2. If N2 < N1 / (log(N1) - 1) then
> log_intersection is faster. It is the case when N2 is very small,
> and N1 is very large. ...