问题描述:

The question might sound a bit ridiculus, but maybe it's possible.

First some information:

I'm creating a chunk management system for a voxel terrain engine.

Each chunk has to be able to access each of its 6 neighbour chunks. So every chunk contains a pointer to his 6 neighbours. That's the reason why the memory location of a chunk cannot change. In the moment my setup looks like this:

ChunkMap chunks; // unordered_map of chunks

ChunkSet createdChunks; // set of pointers to unordered_map entries

ChunkSet generatedChunks; // set of pointers to unordered_map entries

vector<Chunk*> renderedChunks;

Since an unordered_map changes the location of its entrys this leads to errors because the pointers to the chunk neighbours are accessing the wrong location.

Summary:

The datatype should

  • have a persistent memory adress
  • support adding and removing an unknown count of entries
  • be as efficient as possible

Thanks in advance!

网友答案:

Having persistant memory location AND dynamic size will not both happen for the same type (at least not any of the std:: containers).

You three main choices:

  1. Limit the number of elements from start (perhaps to a LARGE amount)
  2. Store the pointer to objects rather than objects in your storage [that way, the object itself has a fixed address from allocation, even if the location where the pointer is stored changes].
  3. Create your own container that allocates "lumps" of storage [of some reasonable, preferrably fixed, size], such as a linked list or vector of lumps, and store data. If the size is big enough [a few thousand elements], then the overhead will be minimal.

Efficiency for any container is really dependent on what operations you are doing - inserting and deleting is not efficient in std::vector, but walking across all elements is. Inserting and deleting is good in std::list, but walking from element to element involves pointer chasing, which is not very good for efficiency. std::map is really efficient for looking up based on some key, and insert/remove is relatively efficient, but walking across all is similar to std::list. The std::unordered_map is a bit like std::vector for insert [when it grows too big, it re-allocates the whole table], but very fast for finding a specific element.

相关阅读:
Top