C ++ removes specific elements of a vector
I am new to C ++ and want to perform removal of vector elements.
My vectors are like:
<vector<vector>> objPoints;
<vector<vector>> delPoints;
<vector<vector>> objPoints2;
each objPoints is 1000x3 in size and has all points. From objPoints, I want to remove delPoints, that is, the (X, Y, Z) values that are in each line.
Can anyone tell me the syntax?
source to share
I will interpret your questions as follows: you have two vectors objPoints
and delPoints
that contain 1000 3D points. I would code this as
std::vector<std::array<int,3> > objPoints;
where I assumed you have some kind of raster so that you can describe your points with values int
(otherwise for records the double
comparison is not so easy).
One of the benefits of using it std::array<int,3>
is that you automatically get the lexicographic ordering of the points (this means specializations std::less
and std::equal_to
that can be directly used without further needing to create some).
Algorithm:
Sort your arrays first. There may be algorithms where this is not required (see @ AshwaniDausodia's other answer), but the following suggests. Also, in general, by using sorted vectors, you can get better performance (at least in containers with a lot of O: for unsorted containers this is roughly O(size1*size2)
, whereas for the following algorithm it is lower). It takes effort to sort firstO(size1 log(size1)) + O(size2 log(size2))
Next, move both arrays at the same time and each time you find that a common element removes it from one of the vectors. When you traverse sorted arrays, where you can always increment only the iterator that points to the smaller element, this step takes O(size1+size2)
.
Implementation:
// deletes the elements from container c1 which are also present in c2
// requires sorted containers c1 and c2
//
template< class ContainerType1, class ContainerType2 >
void delete_common_elements(ContainerType1& c1, ContainerType2 const& c2 )
{
for(auto it1=c1.begin(), it2=c2.begin()
; it1!=c1.end() && it2!=c2.end(); )
{
if(*it1==*it2) // eventually change here if your points are not int's
// but are of floating-point type
{
it1 = c1.erase(it1); //it1 is increased here
}
else
{
*it1<*it2 ? ++it1 : ++it2;
}
}
}
Together, this takes effort O(c1.size()) + O(c1.size() * log(c1.size())
(assuming, of course c1.size()>=c2.size()
).
One can easily extend this to take an arbitrary comparison operator instead operator==
.
source to share
One commendable method:
for each point in delPoints
if point exists in objPoints
delete point from objPoints.
You can do this much more efficiently if you are allowed to sort vectors. I'll give you a method and pseudocode and then you can implement it yourself.
First sort objPoints and delpoints
i=0,j=0
while i < length(objPoints) and j < length(delPoints)
if objPoints[i] > delPoints[j] // Means delPoints[j] is not there in objPoints. If it would have, we would have found it.
j++
else if objPoints[i] < delPoints[j] // Means delPoints[j] is after objPoints[i] if it is there in objPoints
i++
else
erase objPoints[i] // Means we have found delPoints[j], so delete it.
For comaprison, compare wrt first x cordinate
, then y
then z
. For sorting, you can use std::sort
with the same comparison function as in the previous line. For removal, you can use std::vector::erase
.
Or you can implement your own fuctions.
source to share
You can check out this Q&A on StackOverflow on how to erase items from STL containers .
The key point is to use the erase-remove idiom to erase elements from a vector and use a lambda to express the erasure condition:
objPoints.erase(
std::remove_if(
objPoints.begin(),
objPoints.end(),
[&delPoints](const Point3D& point)
{
// Erasing condition:
// Is 'point' contained in the 'delPoints' vector?
auto it = std::find(delPoints.begin(), delPoints.end(), point);
return (it != delPoints.end());
}),
objPoints.end());
Full compiled code example ( live here ):
#include <algorithm> // for std::find(), std::remove_if()
#include <array> // for std::array
#include <iostream> // for console output
#include <vector> // for std::vector
typedef std::array<int, 3> Point3D;
std::ostream& operator<<(std::ostream& os, const Point3D& point)
{
os << "{" << point[0] << ", "
<< point[1] << ", " << point[2] << "}";
return os;
}
std::ostream& operator<<(std::ostream& os, const std::vector<Point3D>& v)
{
if (v.empty())
{
os << "{ <empty> }" << std::endl;
return os;
}
os << "{\n";
for (const auto& point : v)
{
os << " " << point << '\n';
}
os << "}" << std::endl;
return os;
}
int main()
{
std::vector<Point3D> objPoints{{1, 2, 3},
{4, 5, 6},
{11, 22, 33},
{44, 55, 66},
{77, 88, 99}};
std::vector<Point3D> delPoints{{10, 10, 10},
{11, 22, 33},
{44, 55, 66}};
std::cout << "objPoints =\n" << objPoints << std::endl;
std::cout << "delPoints =\n" << delPoints << std::endl;
objPoints.erase(
std::remove_if(
objPoints.begin(),
objPoints.end(),
[&delPoints](const Point3D& point)
{
// Erasing condition:
// Is 'point' contained in the 'delPoints' vector?
auto it = std::find(delPoints.begin(), delPoints.end(), point);
return (it != delPoints.end());
}),
objPoints.end());
std::cout << "\nAfter erasing, objPoints =\n";
std::cout << objPoints << std::endl;
}
Output:
objPoints = { {1, 2, 3} {4, 5, 6} {11, 22, 33} {44, 55, 66} {77, 88, 99} } delPoints = { {10, 10, 10} {11, 22, 33} {44, 55, 66} } After erasing, objPoints = { {1, 2, 3} {4, 5, 6} {77, 88, 99} }
source to share