A way to remove items from the vector immer::vector<>

[grauer-hase]

Hi,

I've got a very basic question and I can't figure out a way to remove an item from the immer:vector<>. The whole immutability concept is new to me. I know that I can produce a new vector by inserting items I need, but still it's not the most efficient way. Maybe there is a function like filter to produce a new vector, but I can't find it.

Could you please advise me on this?

Thanks a lot for your library and your effort :)
Best regards,
Sergii

[arximboldi]

Hi!

For immer::vector you need to produce a new vector without the elements in it, using something like filter in std. However, maybe what you need is immer::flex_vector. It has very similar performance characteristics to immer::vector, but it also has a erase function that works in logarithmic time.

Cheers!

[grauer-hase]

Thank you for your response. All is clear. I thought I missed something. Let me try :)

[grauer-hase]

I decided to implement erase_if for immer::flex_vector and I came up with 2 solutions:

1. Creating an empty vector and putting only filtered items (in this example, using std::accumulate):

template <typename T, typename Predicate>
::immer::flex_vector<T> erase_if_v1(::immer::flex_vector<T> v, Predicate pred) {
  return std::accumulate(v.begin(), v.end(), ::immer::flex_vector<T>(),
                         [&](auto result, T const& next) {
                           if (!pred(next)) return result.push_back(next);
                           return result;
                         });
}

2. Using erase from the immer::flex_vector:

template <typename T, typename Predicate>
::immer::flex_vector<T> erase_if_v2(::immer::flex_vector<T> v, Predicate pred) {
  for (auto i = 0u; i != v.size();) {
    if (pred(v[i])) {
      v = v.erase(i);
    } else {
      ++i;
    }
  }
  return v;
}

I am not sure which one is better/preferable. The first erase_if_v1 returns a new vector which shares no common information with the original vector. On the other hand, the second erase_if_v2 returns a new vector which might share some common information. The performance of both I can't analyse correctly.

I'd appreciate your comments/thoughts.

[arximboldi]

A couple of notes:

1. Better performance can be achieved by moving the values into the update operations, as in std::move(result).push_back(next) in the first version, and std::move(v).erase(i) in the second version. Of course, in general, this is only ok when this is the "last use" of this value, but this is the case in these both instances.

2. Whether options 1) or 2) are better, depends on the actual data. If you expect most of the elements to remain in the vector, and only a few items to be removed, then 2) is way better. If however a significant amount of elements is removed every time (e.g > 10%) then 1) is probably better. What actual exact percentage make 1) better than 2) is hard to tell and may also depend on the vector sizes and even data-types, and it can only be really known experimentally. However for most cases playing using the estimate above is probably a good rule of thumb.

[grauer-hase]

Thank you again for your notes :)