Re: set_intersection
In article <1184934181.791764.244680@q75g2000hsh.googlegroups.com>,
Martin Bonner <martinfrompi@yahoo.co.uk> wrote:
On Jul 20, 4:05 am, John <qjohnny2...@yahoo.com> wrote:
Suppose you have a large set of strings like for say 1 million
elements.
Say you have a pretty small set of strings like say 20 elements.
You want to find which of the 20 elements are also in the 1 million
element set.
To do this you can iterate through each of the 20 elements and look
them each up in the bigger set.
Now if you have another set say 900,000 elements this is not the best
way to do the
set intersection. Better way is to linearly iterator through both
sets in order keeping the matching
elements.
How does the algorithm set_intersection work ? Does it take into
account the above type of analysis ?
Does the standard tell the running time for set_intersection and what
the algorithm is or is this implementation dependent ?
25.3.5.3 [lib.set.intersection] / 4
Complexity: At most
2 * ((last1 - first1) + (last2 - first2)) - 1
comparisons.
The standard almost /never/ specifies the algorithm just a maximum
complexity (which may imply an algorithm, but doesn't prevent a clever
implementer coming up with something better).
It does specify that equivalent entries are copied from the first
sequence. and if there are k equivalent members of both sets those k are
copied. so it must iterate over the first set, but since it can start
the iteration of the second sequence where it left off last time as
soon as either iterator reaches its end the process stops. That is
if you want the elements from the large set copied it goes first, if
you want the copies of the smaller set copied it goes first. It will
stop with the same # of compares. [not stated. but all I see is a
permutation of the actual compares if the sequences are interchanged]
In short it makes no difference as far as speed which sequence is
presented first. It might make a difference if the comparison does not
ensure equiv(A,B) means they are identical. Example
struct foo
{
int a;
int b;
};
bool operator < (const foo &x,const foo &y) {return x.a < y.a;}
std::vector<foo> f1,f2,i1,i2;
// fill f1 and f2 sorted on op <.
std::set_intersect(f1.begin(),f1.end(),f2.begin(),f2.begin(),
std::back_inserter(i1));
std::set_intersetion(f2.begin(),f2.end(),f1.begin(),f1.end,
std::back_inserter(i2));
does not ensure i1 == i2.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]