0

Good whatever part of the day you're reading this!

I've been trying to implement my own version of an std::deque-like container. I thought it would be possible to use templates to customise the size and type of the inner array 'blocks', but I can't seem to get the syntax right. Or at least I think what I'm doing is somehow possible.

template<typename T, int ChunkSize>
class ChunkList
{
public:
  ChunkList()
  {
    T first[ChunkSize] = new T[ChunkSize]; 
    // error: array must be initialized with a brace-enclosed initializer

    m_ChunkPointers.push_back(first);
  }

private:
  // store pointers to the chunks
  std::vector<T[]> m_ChunkPointers;
};

int main()
{
  ChunkList<int, 4> cl = new ChunkList<int, 4>();
}

// compiled with g++ on a windows x64 machine

I found a Stack Overflow answer relating to the brace-enclosed initializer but I don't know how to initialize those with the template syntax.

The only other solution I can think is is using something like malloc(sizeof(T) * ChunkSize) and then casting that to an T[] or something.

Either way any help/advice would be greatly appreciated, always happy to learn new things!

PS: Even if there is a way more efficient solution I'd still like to know if there is a way to make templates behave the way I intend to here, or rather why this isn't valid.

Tieske
  • 55
  • 1
  • 1
  • 8
  • `T first[ChunkSize] = new T[ChunkSize];` - that looks wrong on multiple levels. The right hand side returns a `T*` that you are trying to assign to an array. This cannot work – UnholySheep Jan 13 '23 at 22:52
  • That's not what dynamic array allocation looks like: you can see an example in these docs on the [new expression](https://en.cppreference.com/w/cpp/language/new). Just write `T *first = new T[ChunkSize];` And store `T*` in your vector. And, actually consider using `unique_ptr` instead of raw pointers in the first place. – Useless Jan 13 '23 at 22:52
  • Note: If `T` has no default constructor it's much harder to make an array of them. When you make an array, all of the items in the array spring into existence and that means their constructor must be called. If the constructors all take arguments someone has to provide those arguments. and that someone is a brace-enclosed list. – user4581301 Jan 13 '23 at 22:53
  • `ChunkList cl = new ChunkList();` also cannot compile for the same reason. This code feels like a misunderstanding of what `new` does in C++ (and how to properly create objects) – UnholySheep Jan 13 '23 at 22:53
  • It's hard to even start explaining why this is wrong. C-style arrays just can't be used this way. Casting anything will only make things more broken. – Yksisarvinen Jan 13 '23 at 22:56
  • You could use `typedef T (Chunk)[ChunkSize]; Chunk* c = new Chunk;` I think – Mooing Duck Jan 13 '23 at 22:56
  • @Yksisarvinen: He could also do `T (*first)[ChunkSize] = static_cast(new T[ChunkSize]);` I think, which would be correct, but super weird. Indexing would be uninuitive, he'd' have to use `(*first)[index]` – Mooing Duck Jan 13 '23 at 22:57
  • @MooingDuck Neither of these work: https://godbolt.org/z/fdG8sG6zj. C-style arrays don't follow logical rules. – Yksisarvinen Jan 13 '23 at 22:59
  • I am surprised that the typedef doesn't work. The second one would work with reinterpret_cast, but that's dangerous :/ – Mooing Duck Jan 14 '23 at 02:30

2 Answers2

2

You are already using std::vector why not a proper container for the chunks too?!?

template<typename T, int ChunkSize>
struct ChunkList {
  ChunkList() : m_Chunks(1) {}
private:
  std::vector<std::array<T,ChunkSize>> m_Chunks;
};

// store pointers to the chunks - You do not want to store pointers, you want to store arrays. You attempted to store them on the heap, but that complication is totally unnecessary, because they are of fixed size and std::vector does already manage its elements in dynamically allocated memory.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • Thanks for the quick reply, I've gotten it to work now! My intention with storing pointers inside a vector was to avoid the performance hit when the vector needs to relocate. From what I understand a vector stores its items contiguously and when it runs out of space in memory will relocate itself, which is why I thought of storing the pointers instead of the arrays themselves. Please correct me if I'm misunderstanding something! – Tieske Jan 14 '23 at 20:07
  • @Tieske in that case you can use a `std::vector>`. THough nested vectors often perform very poor. Consider that the advantage of vector (and array) are memory locality. By storing vectors (or pointers) in the vector you add a level of indirection which has a cost too. If you reserve upfront enough space the vector does not have to reallocate. Having said that, if you do care about performance, you need to measure and compare the different approaches. I also depends on the use case scenarios – 463035818_is_not_an_ai Jan 16 '23 at 08:57
  • I intended this to be used for an ECS, storing all components of the same type inside a container like this since itteration speed is important I thought it best for the memory to be mostly contiguous, but entities get spawned and destroyed regularly so expanding wouldn't be a performance heavy task is what I thought, I have yet to run any test – Tieske Jan 16 '23 at 13:18
1

We have a few problems here.

1: In main you wrote ChunkList<int, 4> cl = new ChunkList<int, 4>(); This will not work because new will return a ChunkList* not a ChunkList you need to write ChunkList<int, 4>* cl = new ChunkList<int, 4>(); or ChunkList<int, 4> cl{}; depending on the hact if you need an object or a pointer to an object

2:std::vector<T[]> m_ChunkPointers; declares a vector of empty arrays. I think you menat to write std::vector<T*> m_ChunkPointers; storeing pointers (to the start of the arrays.)

3: T first[ChunkSize] = new T[ChunkSize]; needs to be T *first = new T[ChunkSize];

You mixed together the T x[N]; sintax and the T*x=new T[N]; syntax. the first will create an array on the stack the second will create one array, living until the end of the function on the heap, living until you detete it.

Note: Welcome to C++. In C++ the variables the object themself, not referances/pointers. You need to manage the lifetimes of the objects living in the heep. If you don't want to delete every object you used I suggest to take a look on unique_ptr and shared_ptr

Botond Horváth
  • 929
  • 2
  • 15