Geek asks and answers

Vectors and many indices

Situation: I am reading a 3D file format, which consists of blocks of geometry. Each block, in turn, has links (using indexes) to any of the blocks (similar to potentially visible collections).

The program I am developing should allow you to insert and delete blocks anywhere in the list. This means that many links will become invalid.

One workaround for this would be to convert indexes to pointers when reading a file, in order to have a vector of pointers like this:

class block;

class block
{
    std::vector<block*> a_references;

    // more data
};

std::vector<block*> a_blocks;

In my program, the user can view the reference blocks for each block of the array a_blocks. Here I want to display them as indices. When using index pointers, this means that I will need to do std::findfor each block to find its index in the array. Could this cause a lot of overhead, which I assume?

Which approach is better, and what are the performance benefits?

+3
source share
1 answer

What would I do (if I understood your question correctly): save index:

class block
{
    std::vector<std::size_t> a_references; // some indices in a_blocks

    // more data
};

std::vector<block*> a_blocks;

Then instead of deleting the element, reset it to nullptr
Add the element to the hole or to the end of the vector. Finally, you can have a smoothing function that removes holes and freezes the index.

An alternative could be:

class block
{
    std::vector<block*> a_references;
    std::vector<block*> back_references; // reference each block where `this` is in a_reference 
    std::size_t index; // index in a_blocks 

    // more data
};

, .
/

0

More articles:


All Articles