In c++, is it safe to use std::numeric_limits<double>::max() as a special "flag"?

Question

Given

std::vector<double> a;
std::vector<int> ind;

where ind is ¹sorted in ascending order.

I want to do the equivalent of the following:

for (auto it=ind.rbegin();it!=ind.rend();it++) a.erase(a.begin() + *it);

I came up with this:

for (auto it=ind.begin();it!=ind.end();it++) 
   a[*it] = std::numeric_limits<double>::max();
std::erase(std::remove(a.begin(),a.end(),std::numeric_limits<double>::max()),a.end());

This is very fast, but it doesn't feel right to use the std::numeric_limits::max() as a flag in this context.

Of course feelings shouldn't play too much into the equation ... clearly comparing the doubles within the std::remove is safe, and the limit will never occur in practice in this vector in a working application, so it should be ok, no?

Any thoughts on this?

---

^{1) Ref comment by the OP. – Alf}

Labbe

It's impossible to rule out a vector already containing that value, since you yourself show that it's possible for a vector to contain that value. There's no way to answer this unless you clearly document which assumptions are valid, and which aren't. Another assumption seems to be that the elements of ind are in increasing order and without duplicates, but you don't actually say so in your question. – Scrotum

There are other values you can choose as flags: positive and negative inf, as well as NaN. – Facsimile

It may be better to use std::numeric_limits<double>::infinity() or std::numeric_limits<double>::quiet_NaN() instead, if it is known that none of the values in the arrays will be that value. – Incogitable

Yes, in my case the elements of ind are sorted, hence the reverse iteration alternative/equivalent. – Labbe

Good points re infinity or quiet_NaN. They will never appear in the array unless something else is seriously wrong ... – Labbe

I wouldn't use NAN since it's hard to test for it - none of the standard algorithms will work with it. – Crumple

Can you accidentally get infinity by dividing by zero, or will that cause an exception? – Crumple

I think if double a=1./0; then std::isinf(a) evaluates to true. Not sure about the exception. In my case I could check for infs upfront since they should not occur in my context. But it seems it might be better to implement my own erase-remove idiom which can use the entries in ind rather than the values do identify entries to delete. – Labbe

What's wrong with your first snippet? – Goodhen

Perhaps nothing, but as the first reply points out there is a possibility that std::numeric_limits<double>::max() is already a number in the vector, and hence the operation will fail. Ideally, I would have wanted to reserve a "special" double which I could have used as a flag, for example by using std::numeric_limits<double>::max() as the flag, but then at the same time reducing the max double for everybody else to the second-to-largest possible double value. – Labbe

@shabbi: the direct approach in the first snippet is O(a.size()*ind.size()). – Nonrecognition

Answer 1

Let's look at your "baseline" code, that you say you want to do the "equivalent" of:

std::vector<double> a;
std::vector<int> ind;

for (auto it = ind.rbegin(); it != ind.rend(); it++)
    a.erase(a.begin() + *it);

What we gather from this is that ind is a vector of indexes in a which should be removed, and that they are sorted ascending. Those indexes must be removed from a. I assume your goal is to do this efficiently in terms of space and time.

If you think about it in terms of the minimum number of operations required, you have to shift many/most/all of the elements in a in order to erase the ones indicated by ind. You don't want to erase() several times because this means shifting some elements more than once. One optimal solution (in the general case, not imposing special requirements on the values in a) looks like this:

size_t slow = 0; // where we are currently copying "to"
std::vector<int> inditer = ind.begin();
for (size_t fast = 0; fast != a.size(); ++fast) {
    if (inditer != ind.end() && *inditer == fast) {
        // "remove" this element by ignoring it
        ++inditer;
    } else {
        a[slow] = a[fast];
        ++slow;
    }
}
a.resize(slow);

Now, you could probably reformulate this using STL algorithms and a custom predicate (functor) which remembers its "current" position in ind, but it will not be much less code and it might be harder to understand.

Taunt

Thanks a lot - yes, I think that the solution will be to just implement something like this. Somewhat surprising though that there's no analog to std::remove for this particular situation. I would guess it's a common case. – Labbe

@Jens: I can't recall wanting to do anything like this, but even if it were more directly supported by the STL, there are a couple issues: (1) your ind deals in integers rather than iterators, and (2) ind must be sorted. The STL algorithms tend to be more basic/general/widely-applicable. Think of the STL as a set of examples of what you can do with iterators, rather than a toolbox with fixed contents. – Taunt