I am writing a class which requires highly efficient function for filtering member container (lets say std::vector
). This function should have interface similar to the following:
void filter(std::vector<SomeType>& items, const std::vector<int>& inds);
The function should leave the container items
in the following state:
- items that are pointed to by the index from inds
should be removed
- other items should remain in container keeping initial order.
For simplicity lets assume that inds
is a perfect container with O(1) on every operation and all indices are valid with no duplication.
My idea was to create the second container, reserve required space and then move (through std::move
) every element not indexed by inds
into this new container; and afterwards just swap the old and the new containers.
For example like this:
void filter(std::vector<SomeType>& items, const std::vector<int>& inds)
{
std::vector<SomeType> new_items{};
new_items.reserve( items.size() - inds.size() );
for(size_t i = 0; i < items.size(); ++i)
if( contains( inds, i ) ) // magic O(1) function, never mind
new_items.push_back( std::move( items[i] ) );
items.swap(new_items);
}
My questions are:
1) after using std::move
on some element inside the vector
(or generally any other standard container) will there be any issues like double destructing of these elements?
2) Is there a standard way to do such filtering efficiently?
std::vector<T>
by nature requires type which can be "moved" ("T must meet the requirements of CopyAssignable and CopyConstructible."), as thevector
itself will reallocate the whole buffer when it runs out of space, and "moves" all values from one memory buffer to the new one (usually memmove-like in case of simple types, copy-assignment in case of more complex types). I.e. if yourSomeType
is already correct for usage insidestd::vector
, thestd::move
should work for it too I think (hopefully I didn't forget about some formal detail whystd::move
may fail on such type). – Ped7g Aug 27 at 12:51