remove_if удаляет элемент, даже если предикат возвращает false? - PullRequest
Новая
       65

remove_if удаляет элемент, даже если предикат возвращает false?

0 голосов
/ 19 марта 2020

Я пишу алгоритм октри. Внутри функции я пересекаю октри. Я получаю указатель узла и Сферу в качестве входных данных. Я проверяю, должен ли узел содержать сферу, затем я хочу добавить его в список узлов s object list and remove it from its parent. следующий код 

functionBody()
{
 .....

  if (!node->objectList.empty())
      node->objectList.erase(std::remove_if(node->objectList.begin(), node->objectList.end()-1 , [&t](auto& temp) { return temp == t; }));

...
}

typedef struct Sphere
{
    Sphere() = default;
    Sphere(const Vector3 centre_, const float radius_, const Material& material_) : centre(centre_), radius(radius_), material(material_)
    {
        assert(radius != 0);
        invRadius = 1.0 / radius;

        Vector3 radiusOffset = Vector3(radius);
        aabb.min = Vector3(centre - radiusOffset);
        aabb.max = Vector3(centre + radiusOffset);
    }

    bool operator==(const Sphere& rhs)
    {
        return (centre == rhs.centre) && (radius == rhs.radius);
    }

    Vector3 centre;
    float radius;
    float invRadius;
    Material material;
    AABB aabb;

}Sphere;

Как вы можете видеть для сферы, я определил operator==.

Я вижу, что remove_if удаляет элемент, даже когда предикат возвращает false.

например, при первой итерации он находит одну сферу t и удаляет ее из родительского вектора, используя remove_if. Это t присутствовало в конце вектора. рассмотрим теперь, когда родительский элемент имеет 3 сферы в своем векторе, но когда я go другому дочернему элементу, мы все еще пытаемся найти t в родительском элементе, а remove_if все еще удаляет последнюю запись. Я не понимаю, почему?

Ответы [ 2 ]

1 голос
/ 19 марта 2020

std::remove_if возвращает предоставленный итератор end, когда он не находит ничего для удаления. Вы указали node->objectList.end()-1 в качестве конечного итератора, который является итератором последнего элемента в node->objectList. Это то, что вы передаете erase, когда не находите t, поэтому последний элемент стирается.

Чтобы решить проблему, используйте перегрузку erase, которая принимает диапазон элементов: 

if (!node->objectList.empty())
{
    auto end_iter = node->objectList.end();
    auto to_remove = std::remove_if(
        node->objectList.begin(), end_iter, 
        [&t](auto& temp) { return temp == t; });

    node->objectList.erase(to_remove, end_iter);
}

Теперь, если t не найден erase вообще ничего не сделает. В этом случае remove_if возвращает end_iter и erase пытался стереть элементы в пустом диапазоне, определенном end_iter и самим собой.

Я не уверен, почему вы использовали node->objectList.end() - 1 , Я предполагаю, что это была либо ошибка, либо обходной путь для cra sh, который вы, скорее всего, получите с помощью предыдущего кода.

0 голосов
/ 19 марта 2020

Когда вы вызываете метод erase, который принимает только один итератор (не диапазон итераторов), а алгоритм std::remove_if вызывается со вторым итератором диапазона элементов контейнера, указанного как 

node->objectList.end()-1

тогда, даже если элемент не найден в контейнере, алгоритм remove_if вернет итератор node->objectList.end()-1, который указывает на действительный объект в контейнере. Этот объект будет удален из контейнера.

Вот демонстрационная программа, которая воспроизводит проблему. 

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v = { 1, 3, 5, 7, 9 };

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';

    while ( v.size() > 1 )
    {
        v.erase( std::remove_if( std::begin( v ), std::prev( std::end( v ) ),
                                 []( const auto &item )
                                 { 
                                    return item % 2 == 0; 

                                 } ) );
    }

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

Ее вывод 

1 3 5 7 9 
1

Это не элемент в векторе четное число. Тем не менее, все элементы, кроме одного, были стерты из вектора.

Похоже, вы неправильно указали диапазон. Он должен быть указан как пара 

node->objectList.begin(), node->objectList.end()

. Или перед удалением элемента вы должны проверить, равен ли возвращаемый итератор node->objectList.end() - 1 (при условии, что вы действительно хотите использовать диапазон, показанный в вашем вопросе). В этом случае метод erase не должен вызываться. Или вы должны указать стертый диапазон итераторов, например 

if (!node->objectList.empty())
      node->objectList.erase(std::remove_if(node->objectList.begin(), node->objectList.end()-1 , [&t](auto& temp) { return temp == t; }).
                             node->objectList.end()-1);

Снова при условии, что вы действительно хотите использовать второй итератор диапазона, например node->objectList.end()-1 вместо node->objectList.end().

...