Most optimal way to remove an index from an vector-like data structure without copying data in C++

Question

The problem:

I need to create a simple vector or vector-like data structure that has indexable access, for example:

arr[0] = 'a';
arr[1] = 'b';
//...
arr[25] = 'z';

From this structure, I would like to remove some index, for example index [5] The actual value at the index does not need to be erased from memory, and the values should not be copied anywhere, I just need the indexes of the data structure to re-arrange afterward, so that:

arr[0] = 'a';
//...
arr[4] = 'e';
arr[5] = 'g';
//...
arr[24] = 'z';

Is std::vector the best data structure to use in this case, and how should I properly remove the index without copying data? Please provide code.

Or is there a more optimal data structure that I can use for this?

Note, I am not intending on accessing the data in any other way except through the index, and I do not need it to be contiguously stored in memory at any time.

Answer 1

What you want is probably covered in one of these:

1. what has been proposed for std::hive

Hive is a formalisation, extension and optimization of what is typically known as a 'bucket array' container in game programming circles; similar structures exist in various incarnations across the high-performance computing, high performance trading, 3D simulation, physics simulation, robotics, server/client application and particle simulation fields.

2. std::flat_map in C++23

A flat_map is a kind of associative container that supports unique keys (contains at most one of each key value) and provides for fast retrieval of values of another type T based on the keys.

Answer 2

Since you want the indecies to be updated, then you need a sequential container: vector, list, deque, or similar. vector and deque will copy values around, but list is also slow for virtually all purposes, so none of these is a great fit at first.

Ergo, the best solution is std::vector<std::unique_ptr<Item>>. Then you get very fast accesses, but when removing elements by index, the actual items themselves are not moved, only pointers are rearranged.

Answer 3

Another range-based solution consists of:

• enumerate each element of v,
• remove(each element)_if it is_contained_in those toBeRemoved based on the key,
• and finally transform the result retaining only the value.

auto w = enumerate(v)
       | remove_if(is_contained_in(toBeRemoved), key)
       | transform(val);

Full example on Compilier Explorer.

---

I've also used BOOST_HOF_LIFT from Boost.HOF to turn std::get into an object that I can pass around, based on which I've defined key and val.

Answer 4

It is a requirement of the vector data structure that it's data is contiguous in memory, so it is not possible to remove an element without moving memory to fill the gap (other than the final element).

A vector is one of the sequence containers. A sequence container with minimal O(1) cost of element removal is a double-linked list (as implemented by std::list). A list can be efficiently accessed sequentially, but unlike a vector is O(n) for random access.

For a discussion of the time complexity of different operations on various container classes see for example https://dev.to/pratikparvati/c-stl-containers-choose-your-containers-wisely-4lc4

Each container has different performance characteristics for different operations. You need to choose one that best fits the operations you will mostly perform. If sequential access and element insertion and removal are key, a list is appropriate. If random access is more critical, it may be worth the hit of using a vector if insertion/removal are infrequent. It may be that neither is optimal in your application, but for the specific situation detailed in your question, a linked-list fits the bill.

Answer 5

What about using a view-base approach?

Here I show a solution using ranges::any_view. At the bottom of this answer is the complete working code, which shows that the vector-like entity we make up is actually pointing to the very elements of the original std::vector.

Beware, I'm not addressing performance in any way. I don't claim to know much of it, in general, and I know even less of it as related to the cost of the abstractions I'm using below.

The core of the solution is this function for dropping only one element, the one with index i, form the input range:

constexpr auto shoot =
    [](std::size_t i, auto&& range)
        -> any_view<char const&, category::random_access> {
    return concat(range | take(i), range | drop(i + 1));
};

In detail,

• given the index i of the item to be removed from the input range,
• it creates a range by takeing the first i elements from range (these are the elements before the element of index i),
• it creates a range by droping the first i + 1 elements from range (thus retaining the elements after the element of index i),
• and finally it concatenates those two ranges
• returning the resulting range as an any_view<char const&, category::random_access>, to avoid nesting more and more views for each repeated application of shoot;
• category::random_access is what allows a []-based access to the elements.

Given the above, deleting a few elements from the range is as easy as this:

auto w = shoot(3, shoot(9, shoot(10, v)));

However, if you were to call shoot(9, shoot(3, v)) you would be removing the 3rd element first, and then the 9th element of the resulting range, which means that you'd have removed the 3rd and 10th elements with respect to the original vector; this has nothing to do with the range-base approach, but just with providing a function to delete only one element.

Clearly you can build on top of that a function that eliminates all the indices from another range:

• sort the indices of elements to be removed,
• for-loop on them in reverse (for the reason explained above),
• and shoot them one by one (without using any_view we couldn't do view = shoot(n, view); because each application of shoot would change the type of the view):

constexpr auto shoot_many = [](auto&& indices, auto&& range){
    any_view<char const&, category::random_access> view{range};
    sort(indices);
    for (auto const& idx : reverse(indices)) {
        view = shoot(idx, view);
    }
    return view;
};

I have tried another solution for shoot_many, where I would basically index all the elements of the range, filter out those with index contained in indices, and finally transforming to remove the indices. Here's sketch of it:

constexpr auto shoot_many = [](auto&& indices, auto&& range){
    std::set<std::size_t> indices_(indices.begin(), indices.end()); // for easier lookup
                                                                    // (assuming they're not sorted)
    auto indexedRange = zip(range, iota(0)); // I pretty sure there's a view doing this already
    using RandomAccessViewOfChars
        = any_view<char const&, category::random_access>;
    return RandomAccessViewOfChars{
        indexedRange | filter([indices_](auto&& pair){ return indices_.contains(pair.second); })
                     | transform([](auto&& pair){ return pair.first; })};
};

This, however, doesn't work because having filter in the pipe means that we don't know the length of the resulting range until the moment we truly traverse it, which in turn means that the output I'm returning doesn't meet the compile-time requirements for a category::random_access any_view. Sad.

Anyway, here's the solution:

#include <assert.h>
#include <cstddef>
#include <functional>
#include <iostream>
#include <memory>
#include <range/v3/algorithm/sort.hpp>
#include <range/v3/range/conversion.hpp>
#include <range/v3/view/any_view.hpp>
#include <range/v3/view/concat.hpp>
#include <range/v3/view/drop.hpp>
#include <range/v3/view/iota.hpp>
#include <range/v3/view/reverse.hpp>
#include <range/v3/view/take.hpp>
#include <set>
#include <vector>

using namespace ranges;
using namespace ranges::views;

// utility to drop one element from a range and give you back a view
constexpr auto shoot =
    [](std::size_t i, auto&& range)
        -> any_view<char const&, category::random_access> {
    return concat(range | take(i), range | drop(i + 1));
};

constexpr auto shoot_many = [](auto&& indices, auto&& range){
    any_view<char const&, category::random_access> view{range};
    sort(indices);
    for (auto const& idx : reverse(indices)) {
        view = shoot(idx, view);
    }
    return view;
};


int main() {
    // this is the input
    std::vector<char> v = iota('a') | take(26) | to_vector;
    // alternavively,   = {'a', 'b', ...)

    // remove a few elements by index
    auto w = shoot_many(std::vector<int>{3, 10, 9}, v);

    for (std::size_t i = 0, j = 0; i != v.size(); ++i, ++j) {
        if (i == 10 || i == 9 || i == 3) {
            --j;
            std::cout << v[i] << ',' << '-' << std::endl;
        } else {
            std::cout << v[i] << ',' << w[j] << std::endl;

            assert( v[i] ==  w[j]);
            assert(&v[i] == &w[j]);
        }
    }
}