C++ remove certain elements of vector

Question

I am new to C++ and want to do vector element elimination.

My vectors are like:

<vector<vector>> objPoints;
<vector<vector>> delPoints;
<vector<vector>> objPoints2;

each objPoints has size 1000x3 and has all points. From objPoints i want to remove delPoints i.e. the (X,Y,Z) values that reside in each row.

Can anyone please tell me syntax?

Answer 1

I interpret your questions as follows: You have two vectors objPoints and delPoints which contain 1000 three-dimensional points. I would encode this as

std::vector<std::array<int,3> > objPoints;

where I assumed you have some raster such that you can desribe your points by int values (otherwise, for double entries, comparison is not that easy).

One benefit of using std::array<int,3> is that you automatically get a lexicographic ordering of the points (that means, specializations of std::less and std::equal_to which can directly be used without the further need to create some).

---

Algorithm:

First sort your arrays. There might be algorithms where this is not really necessary (see the other answer by @AshwaniDausodia), but the following assumes it. Further, in general by using sorted vectors one can obtain a better performance (at least in the big-O: for unsorted containers, it is roughly O(size1*size2), whereas it is lower for the following algorithm). The sorting first requires an effort of O(size1 log(size1)) + O(size2 log(size2))

Next, traverse both arrays at the same time and each time you find a common element delete it from one of the vectors. As you traverse sorted arrays, where you can always increase only the iterator pointing 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;
        }
    }
}   

DEMO

All together, this requires an effort of O(c1.size()) + O(c1.size() * log(c1.size()) (naturally assuming c1.size()>=c2.size()).

One can easily extend this to take an arbitrary comparison operator instead of the operator==.

Answer 2

If you definately have to use vectors, an easy (but inefficient) way would be to std::find the element in objPoints that you want to remove and then remove it with std::vector::erase.

Answer 3

One obivious method would be:

for each point in delPoints
    if point exists in objPoints
        delete point from objPoints.

You can do it much more efficiently if you are allowed to sort the vectors. I will provide you with method and pseudo code then you can implement it on you own.

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, first compare w.r.t x cordinate then y and then z. For sorting, you can use std::sort with same comparison function described in previous line. For deleting, you can use std::vector::erase.
Or you can implement your own fuctions.

Answer 4

You may consider read this Q&A on StackOverflow on how to erase elements from STL containers.

The key point is to use the erase-remove idiom to erase items from the vector, and use a lambda to express the erasing 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 compilable code sample (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}
}