C++ удаляет определенные элементы вектора

Question

Я новичок в C++ и хочу удалить элемент векторного элемента.

Мои векторы как:

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

каждый objPoints имеет размер 1000x3 и имеет все точки. Из objPoints я хочу удалить delPoints, то есть значения (X, Y, Z), которые находятся в каждой строке.

Может ли кто-нибудь сказать мне синтаксис?

Answer 1

Если вы определенно должны использовать векторы, простой (но неэффективный) способ будет состоять из std::find элемента в objPoints, который вы хотите удалить, а затем удалить с помощью std::vector::erase.

Answer 2

Один obivious метод был бы:

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

Вы можете сделать это гораздо более эффективно, если разрешено сортировать векторы. Я дам вам метод и псевдокод, а затем вы можете реализовать его самостоятельно.

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. 

Для comaprison, первый сравнить w.r.t x cordinate затем y, а затем z. Для сортировки вы можете использовать std::sort с одинаковой функцией сравнения, описанной в предыдущей строке. Для удаления вы можете использовать std::vector::erase.
Или вы можете реализовать свои собственные fuctions.

Answer 3

Я интерпретирую ваши вопросы следующим образом: у вас есть два вектора objPoints и delPoints, которые содержат 1000 трехмерных точек. Я бы закодировать это как

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

где я предположил, что вы есть растр таким образом, что вы можете desribe ваши очки int значения (в противном случае, для double записей, сравнение не так просто).

Одним из преимуществ использования std::array<int,3> является то, что вы автоматически получаете лексикографическое упорядочение точек (что означает, специализации std::less и std::equal_to, которые непосредственно могут быть использованы без дальнейшей необходимости создания некоторых).

---

Алгоритм:

сортировать ваши массивы. Могут быть алгоритмы, где это не обязательно (см. Другой ответ @AshwaniDausodia), но следующее предполагает. Кроме того, в общем случае, используя отсортированные векторы, можно получить лучшую производительность (по крайней мере, в контейнерах с несортированными значениями большой-O: это примерно O(size1*size2), тогда как для следующего алгоритма ниже). Для сортировки вначале необходимо напряжение O(size1 log(size1)) + O(size2 log(size2))

Далее, перемещайте оба массива одновременно и каждый раз, когда вы обнаружите, что общий элемент удаляет его из одного из векторов. Когда вы пересекаете отсортированные массивы, где всегда можно увеличить только итератор, указывающий на меньший элемент, этот шаг занимает O(size1+size2).

---

Реализация:

// 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

Все вместе, это требует усилий O(c1.size()) + O(c1.size() * log(c1.size()) (естественно предполагая c1.size()>=c2.size()).

Можно легко расширить это, чтобы взять произвольный оператор сравнения вместо operator==.

Answer 4

Вы можете ознакомиться со статьей this Q&A on StackOverflow on how to erase elements from STL containers.

Ключевым моментом является то, чтобы использовать стирающего удалить идиомы для удаления элементов из вектора, и использовать лямбда, чтобы выразить условие стирания:

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()); 

Полный компилируется пример кода (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; 
} 

Выход:

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} 
}