CODEWITHSUNDEEP
c++boostdata-structuresstlcontainers
static_rtti
static_rtti

Reputation: 56232

C++ "vector" with elements of variable size

For a very specific application, I'd like to use a container with elements of variable size and contiguous in memory. The rationale is that access will be mostly sequential, so having all the data in the same linear data structure should help caching behavior.

Of course random access will be impossible, but the data structure should be dynamically-sized with a vector-style push_back method.

Does a container like this exist? How is it called?

Edit to address Arne Mertz' comment:

The structure I want to represent is a graph. The container would contain the list of nodes with for each node the list of edges, probably represented as a list of pointers to other (previous) nodes.

struct Node {
  //various fixed size fields about the node itself
  ...

  unsigned short n_edges;
  Node * edges[n_edges]; // schematically
};

Upvotes: 1

Views: 2761

Answers (4)

EvilTeach
EvilTeach

Reputation: 28837

Implement a class with a chunk of dynamic memory. Write a function to push a variable length structure on the end of the chunk. put the offset of the chunk in a vector to give you easy iteration of the chunk, and random access of the chunk.

When the dynamic memory area becomes full, reallocate it larger and copy the old chunks data into it.

Rinse Repeat.

Upvotes: 0

Enigma
Enigma

Reputation: 1717

you could create a std::vector<char> v combined with a std::list<size_t> l. v will act as a growable char buffer and l will contain the offsets to your objects.

Now you need to write your own push_back which inserts the current offset into the std::list and copies the object at location: &v[offset] (remember to increase v beforehand).

template <class T>
void push_back(T t)
{
    size_t vectorSize = v.size());
    size_t objectSize = sizeof(T);

    l.pushback(vectorSize);

    v.reserve(vectorSize + objectSize);
    st::memcpy(&v[vectorSize], &t, objectSize);
}

Upvotes: 2

user877329
user877329

Reputation: 6200

One way of solving this is to use an internal void pointer. Then, each element is stored in that memory. Each element begins with its size. Iterating over the container would increment a byte pointer by the size of current element. If you want random access, you can use a directory containing pointers to all elements.

Upvotes: 1

Jan Herrmann
Jan Herrmann

Reputation: 2767

What about Boost Intrusive singly linked list. You need to implement your own allocation yourself. You can simply allocate a large area (of type char[]) and create your objects inside this area with increasing addresses (don't forget alignment). If your area is full you can simply create a further one. But you have to do all allocation for your own and manage object lifetime. In addition you can use a std::vector as a supporting structure for O(1) access.

Upvotes: 1

Related Questions