🔒 Locked

[STL] Difference between two std::vectors

Started by gimp Mar 30, 2004 at 7:36 PM 3 replies 1.1k views

Original Post

Mar 30, 2004 at 7:36 PM

Almost... I''d like to check to see if all the items within vector1 exist within vector2. If not I''d like vector3 to contain the missing elements. I was about to code a bunch of loops within loops. This is not ideal as it''s in my main loop. I expect vector1 to be large (1000''s), vector2 to be small(up to a few hundred) and the difference between the sets each frame will be in the order of a dozen at most. Can anyone think of a good way to do this without having to check vector1 for every item within vector2? I was sort of looking at set_difference but the word ''ordered sets'' scared me off. I doubt there is any order to my data and vector 2 is generated so I cannot keep it ordered... Any idea''s?

Sneftel

296

Sneftel

Mar 30, 2004 at 7:42 PM

In order for an efficient comparison to be done, the data will need to be sorted. Otherwise, it''ll be an O(n^2) operation.

What''s keeping you from sorting the two vectors, exactly?

"Sneftel is correct, if rather vulgar." --Flarelocke

gimp

Author

gimp

Mar 30, 2004 at 8:22 PM

I think your correct. I''ll sort...

Timkin

149

Timkin

Mar 30, 2004 at 8:55 PM

Or, if vector1 is fairly constant over time but vector2 isn''t, consider using a tree structure to store the data in vector1. The data in vector2 becomes the query keys for your search.

If vector1 is constant, then the tree can be built at startup (offline). The tradeoff here is the additional storage space required for the tree bookkeeping.

Timkin

sjelkjd

119

sjelkjd

Mar 31, 2004 at 1:20 AM


template<class T>
bool contains_all(const vector<T>& a,const vector<T>& b, vector<T>& c)
{
  c.clear();
  set_difference(b.begin(),b.end(),a.begin(),a.end(),back_inserter(c));
  return c.empty();
}

I love stl =)

edit: this function requires the vectors to be sorted

[edited by - sjelkjd on March 31, 2004 2:20:43 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.