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.

CodePudding user response：

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.

CodePudding user response：

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 data structure with minimal 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 not fast 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