[Bug libstdc++/66418] New: Optimize set_intersection when one list is much smaller and the other has random access

[glisse at gcc dot gnu.org]

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.