c++11 - intersection of n vectors -

i'm new programming , i've come across issue finding intersection of n vectors, (int vectors) have sorted ints. approach came has complexity of o(n^2) , using std::set_intersect function.

the approach came having 2 vectors: first vector correspond first vector have, , second second vector. call set intersection on 2 , overwrite first vector, use vector clear function on second. overwrite next vector second, , repeat process, , returning first vector.

i believe there more efficient way of going this, @ moment, can not think of more efficient manner. on issue appreciated.

fortunately, think tighter bound can placed on complexity of algorithm.

the complexity of std::set_intersection on input sets of size n1 , n2 o(n1 + n2). take original vectors , intersect them in single-elimination tournament style, is, on first round intersect 1st , 2nd vectors, 3rd , 4th, 5th , 6th, , forth; on second round intersect 1st , 2nd intersections, 3rd , 4th, , forth; repeat until final round produces 1 intersection. sum of sizes of vectors surviving each round no more half sum of sizes of vectors @ start of round, algorithm takes o(n) time (also o(n) space) altogether n sum of sizes of original vectors in input. (it's o(n) because n + n/2 + n/4 + ... < 2n.)

so, given input consisting of already-sorted vectors, complexity of algorithm o(n).

your algorithm merges vectors in different sequence, while i'm not 100% sure o(n), suspect is.

---

edit: concerning how implement "tournament" algorithm in c++, depends on how hard want work optimize this, , on nature of input.

the easiest approach make new list of vectors; take 2 vectors old list, push vector onto new list, merge 2 old vectors onto new vector, destroy old vectors, hope library manages memory efficiently.

if want reduce allocation of new vectors, re-using vectors (as thought do) might help. if input data structure std::list<std::vector<int> >, example, start pushing 1 empty vector onto front of list. make 3 iterators, 1 new vector, , 1 each of original first 2 vectors in list. take intersection of vectors @ last 2 iterators, writing result first iterator, clear vectors @ last 2 iterators. move last 2 iterators forward 2 places each, move first iterator forward 1 place. repeat. if reach state 1 of last 2 iterators has reached end() other has not, erase list elements between first iterator , other iterator. have list of vectors again , can repeat long there more 1 vector in list.

if input std::vector<std::vector<int> > pushing element onto front of list relatively expensive, might want more complicated algorithm. there lots of choices, no obvious winners can think of.