Prevent adding multiple same items to vector in recursion

Question

I got a method that adds adjacent Voxels to a vector. This method uses an vector with all the remaining points (means, they still need to be looked at as they are possible adjacents) and looks on every one of them if it is near enough to be added. If an element is a neighbor it also checks all adjacents of this element to add them too. This happens in a recursive manner.

void remove(std::vector<pcl::PointXYZ> &vec, pcl::PointXYZ p) {
    for (int i = 0; i < vec.size(); i++) {
      if (vec[i].x == p.x && vec[i].y == p.y && vec[i].z == p.z) {
        vec.erase(vec.begin() + i);
        break; // as all points should be unique
      }
    }
}

void addAdjacents(pcl::PointXYZ start, std::vector<pcl::PointXYZ> &newCluster, std::vector<pcl::PointXYZ> &remainingPoints) {
  for (pcl::PointXYZ p : remainingPoints) {
    if (distance(p, start) < 0.015) {
      newCluster.push_back(p);
      remove(remainingPoints, p);
      if (remainingPoints.size() > 0)
        addAdjacents(p, newCluster, remainingPoints);
    }
  }
}

The problem is, that many points from the remainingPoints-vector are added to the newCluster multiple times. I thought this wouldn't happen but it seems like internally it makes copies of the vector in the recursion? If a point is removed in a deeper layer the for-loop in the outer execution is somehow still iterating over this (removed) element.

I am fairly new to c++ so I am not sure how to prevent this. Can anyone help me? Thanks!

For sure I can just write a method addToCluster which just checks if the vector has this element before adding it but I thought that maybe there is a more elegant way to prevent this happening in the first place.

Edit: As I understand I am breaking my iterator in the loop. So I would need to somehow update my iterator after calling addAdjacents. Is this right? Can I do something like that?

Your code is missing definitions, please see [How to create a Minimal, Reproducible Example](https://stackoverflow.com/help/minimal-reproducible-example) — Superlokkus, Jan 14 '20 at 12:26
Try to pass the vector by value not reference. In your code, you're passing a reference, so all function calls share the same object. Just remove `&` in the function prototype and try. — Mohammed Deifallah, Jan 14 '20 at 12:27
How is (e.g.) `remove` implemented? We cannot help you with your implementation without knowing how your implementation looks like. At first glance, changing a vector while iteration over it might not be the best idea (depending on how the implementation looks like). — MSpiller, Jan 14 '20 at 12:28
a container with unique elements is `std::set`, on the other hand, if you want to fix the logic of the code, such that no element is inserted multiple times you need to provide a [mcve] — 463035818_is_not_an_ai, Jan 14 '20 at 12:30
@MohammedDeifallah I passed it as reference exactly because I want all to share the same object. — progNewbie, Jan 14 '20 at 12:30
Can you also share some sample data which results in duplicates? As far as I can tell, the code looks fine. — Tanveer Badar, Jan 14 '20 at 12:32
when you erase element from a container while iterating you have to account for the removed elements. — 463035818_is_not_an_ai, Jan 14 '20 at 12:32
@formerlyknownas_463035818 This is what I thought what would be my problem. I just don't know how to solve this. — progNewbie, Jan 14 '20 at 12:39
@Superlokkus This comes from the [pcl](http://docs.pointclouds.org/1.0.1/structpcl_1_1_point_x_y_z.html). Sorry for not mentioning. — progNewbie, Jan 14 '20 at 12:55
Any reason why you are not using the PCL for this kind of processing? From what I can guess, this is more or less the extraction of an euclidian cluster from a single start point. — MSpiller, Jan 14 '20 at 13:22
@M.Spiller Yes. I used the `PCL` first but got some problems with that so I wanted to also implement it by myself. — progNewbie, Jan 14 '20 at 13:26
I think you have a design issue. IMHO, you can't address your problem this way. What happens if `remainingPoints` contains a point that is not adjacent to any other one ? It will never be added to `newCluster`, never be removed from `remainingPoints`, so your recursion end condition will never be reached and it will lead to infinite recursion (evil) :) — Fareanor, Jan 14 '20 at 13:33
@Fareanor It is totally fine if some points are not adjacent to the rest. I mean this should be the case. If it wouldn't it would be just copying the elements from one vector to another. — progNewbie, Jan 14 '20 at 13:37
@progNewbie I know it should be the case, but regarding your code, it is not _"totally fine"_. Because your recursion condition is `remainingPoints.size() > 0` which would always be `true` if you have at least one non-adjacent point ;) But anyway, you got a good answer. — Fareanor, Jan 14 '20 at 13:39
@Fareanor I handle this where I initially call my `addAdjacents` method. But thank you very much for your effort! :) — progNewbie, Jan 14 '20 at 13:40

score 1 · Accepted Answer · edited Jan 14 '20 at 13:33

You need to separate identifying the points you wish to migrate with erasing them from the input.

template<typename BidirIt>
BidirIt addAdjacentsImpl(pcl::PointXYZ start, std::vector<pcl::PointXYZ> &newCluster, BidirIt first, BidirIt last) {
    auto part = std::stable_partition(first, last, [&](auto p){ return distance(p, start) >= 0.015; });
    for (auto it = part; it != last; ++it) {
        newCluster.push_back(*it);
        part = addAdjacentsImpl(*it, newCluster, first, part);
    }
    return part;
}

This only re-orders the elements, such that those we wish to remove are after those we wish to keep. I've written it as a template because I don't care to name the particular iterator types.

void addAdjacents(pcl::PointXYZ start, std::vector<pcl::PointXYZ> &newCluster, std::vector<pcl::PointXYZ> &remainingPoints) {
    auto last = addAdjacentsImpl(start, newCluster, remainingPoints.begin(), remainingPoints.end());
    remainingPoints.erase(last, remainingPoints.end());
}

This is a great solution. Thank you! – progNewbie Jan 14 '20 at 13:33 — progNewbie, Jan 14 '20 at 13:33

463035818_is_not_an_ai · Answer 2 · 2020-01-14T15:32:08.140

-2

Here

list.erase(list.begin() + i);

You erase an element from the std::vector called list (really not the best name for a vector) which invalidates iterators at and after the erased position. It isnt that obvious, but this erasing happens while addAdjacents iteratates over the same container. Leaving only the broken part in we have

void addAdjacents(pcl::PointXYZ start, std::vector<pcl::PointXYZ> &newCluster, std::vector<pcl::PointXYZ> &remainingPoints) {
  for (pcl::PointXYZ p : remainingPoints) {
      newCluster.push_back(p);
      //remove(remainingPoints, p); // <- calls erase
      remainingPoints.erase( remainingPoints.begin() + some_index); 
    }
  }
}

Erasing an element from remainingPoints does break the range-based loop, because under the hood it uses iterators that potentially got invalidated in remove.

edited Jan 14 '20 at 15:32

answered Jan 14 '20 at 12:38

463035818_is_not_an_ai

109,796
11
89
185

yes. I think this is exactly my problem. But I am not sure how to solve this. – progNewbie Jan 14 '20 at 12:41
@Hawky if you look at the column for `std::vector` you can read in the table that references and iterators are valid after erase conditionally and the condition is that the iterator is before the erased one, ergo iterators after the erased are not guaranteed to be valid after erase – 463035818_is_not_an_ai Jan 14 '20 at 12:50
@formerlyknownas_463035818 Look at my comment under the main post, I was talking about `std::list` since the name `list`, so my mistake here. – Hawky Jan 14 '20 at 12:56
1

@Hawky yes saw that. I left the comment just in case the misunderstanding happens again – 463035818_is_not_an_ai Jan 14 '20 at 12:58

Prevent adding multiple same items to vector in recursion

2 Answers2