How to calculate addition to given vector indices?

Question

I have a three-dimensional point vector represented by a class Point3D,

std::vector<Point3D> points;

I also have a vector size_tcontaining the indices of the vector points,

std::vector<size_t> indices_true;

Now I want to build an inversion indices_true, i.e. I want to create another pointer vector indices_falsecontaining all the indexes that are not in indices_true. How can this be done faster than the following:

for (size_t i = 0; i < points.size(); i++)
{
    // TODO: The performance of the following is awful
    if (std::find(indices_true.begin(), indices_true.end(), i) == indices_true.end())
        indices_false.push_back(i);
}

Answer 1

Additional memory is required, but gives a linear algorithm:

Here is an attempt (neither compiled nor tested):

indices_false.reserve(points.size() - indices_true.size());

std::vector<char> isTrue(points.size(), false); // avoided std::vector<bool> intentionally

for (const size_t i : indices_true)
{
    isTrue[i] = true;
}

for (size_t i = 0; i < points.size(); ++i)
{
    if (!isTrue[i])
        indices_false.push_back(i);
}

Answer 2

indices_true k . . ( ) .

( , ):

std::sort(begin(indices_true), end(indices_true));
indices_false.reserve(points.size() - indices_true.size());

size_t k = 0;
for (size_t i = 0; i < points.size(); ++i)
{
    if (k < indices_true.size() && i > indices_true[k])
        ++k;

    assert(k >= indices_true.size() || i <= indices_true[k]);

    if (k >= indices_true.size() || i != indices_true[k])
        indices_false.push_back(i);
    }
}

Answer 3

Correct the vector first indices_trueand use std::binary_search. To keep order in vector withstd::stable_sort.

std::stable_sort(indices_true.begin(), indices_true.end());
for (size_t i = 0; i < points.size(); i++)
{
    if (std::binary_search(indices_true.begin(), indices_true.end(), i))
        indices_false.push_back(i);
}