https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66418
Bug ID: 66418
Summary: Optimize set_intersection when one list is much
smaller and the other has random access
Product: gcc
Version: 6.0
Status: UNCONFIRMED
Keywords: missed-optimization
Severity: enhancement
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: glisse at gcc dot gnu.org
Target Milestone: ---
Computing the intersection of sorted lists of size N1 and N2 is done in time
N1+N2. When we have random access to the second list, it is also possible to
search each element of the first list in the second one in time N1*log(N2),
which is faster when N1 is much smaller than N2.
