3
\$\begingroup\$

I am trying to optimise my remove-erase functions by using some attributes of C++ containers. This function should delete all indices defined in std::set form given vector. I am pretty sure that algorithm is functionality-wise working, but every time I see STL implementation or any code using STL I see a lot of checks around which I cannot come up when I am writing my own code.

I decided to practise by trying so I hope for some tips or tricks on how to improve my code-writing skills.

The algorithm is trying to prevent unnecessary copies. So it is copying just the elements that are supposed to survive. It goes by two iterators. One for a destination where the next element should be copied and second the next element that should "survive". When it arrives at the end of the vector minus the number of deleted elements it stops and leaves the rest for erase() function.

//=================================================================================
// Deletes all indexes defined in set from vector. Leverages the advantage of set being 
// sorted from the smallest to the highest number and continuity of vector storage.
template <class T, class IdxT> 
typename std::vector<T>::iterator remove_indices(std::vector<T>& vector, const std::set<IdxT>& set)
{
    if (set.empty())
    {
        return vector.end();
    }

    auto       nextDelete       = set.begin();
    const auto destinationIndex = *nextDelete;
    auto       destination      = vector.begin();
    auto       source           = vector.begin();
    std::advance(destination, destinationIndex);
    std::advance(source, destinationIndex + 1);
    ++nextDelete;
    auto sourceIndex = destinationIndex + 1;
    while (destination != vector.end() - set.size())
    {
        while (nextDelete != set.end())
        {
            if (sourceIndex == *nextDelete)
            {
                ++source;
                ++nextDelete;
                ++sourceIndex;
            }
        }
        *destination = std::move(*source);
        ++destination;
        ++source;
        ++sourceIndex;
    }
    return destination;
}
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

There are a few things I would improve:

  • Clearly separate the three distinct phases:
    1. Skip until the first index in the set
    2. Copy/delete until we reached the last index
    3. Copy the remainder until the end of the container is reached.
  • Have an outer loop that loops over the entries of set.
  • Use *foo++ syntax.
  • Use auto return type deduction.
  • Name things after their purpose, not what type they are. So instead of set, name it indices.

With this, the code would look like:

template <class T, class IdxT> 
auto remove_indices(std::vector<T>& container, const std::set<IdxT>& indices)
{
    // Exit early if there is nothing to do.
    if (indices.empty())
        return container.end();

    auto destination = container.begin();
    auto source = container.begin();
    auto idx_it = indices.begin();

    // Skip until we reach the first index.
    std::advance(destination, *idx_it);
    std::advance(source, *idx_it + 1);

    // Delete all the elements at the given indices.
    while(++idx_it != indices.end()) {
        auto nextDelete = container.begin() + *idx_it;
        while(source < nextDelete)
            *destination++ = std::move(*source++);
        source++;
    }

    // Copy the remainder until the end of the container.
    while (source != container.end())
        *destination++ = std::move(*source++);

    return destination;
}

Also consider adding a test suite. And you might want to generalize this further to remove elements from other random access container types (for example, std::deque), and have it take the indices in other container types as well, as a std::set is quite an inefficient way to store a few integers.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.