Reputation: 877
I'm writing a B-Tree class for databases.
struct Node {
// invariant: t - 1 <= size <= 2 * t - 1
// invariant: capacity 2 * t - 1
K *keys_ = nullptr;
// invariant: t <= size <= 2 * t
// invariant: size of children_ is size of keys_ + 1
// invariant: capacity 2 * t
std::array<std::unique_ptr<Node>, 2 * t> children_;
// number of stored keys
// invariant: except root, the number of keys is at least t - 1, at most 2 * t - 1
// invariant: except root, for non-leaf nodes, the number of children is at least t, at most 2 * t
// invariant: child_0 <= key_0 <= child_1 <= key_1 <= ... <= key_(N - 1) <= child_N
std::ptrdiff_t N_ = 0;
Node *parent_ = nullptr;
Node() : keys_(alloc_.allocate(2 * t - 1)) {
children_.fill(nullptr);
}
~Node() noexcept {
alloc_.deallocate(keys_, 2 * t - 1);
}
Node(const BTreeNodeBase &node) = delete;
Node &operator=(const BTreeNodeBase &node) = delete;
Node(BTreeNodeBase &&node) = delete;
Node &operator=(BTreeNodeBase &&node) = delete;
};
Here, alloc_
is an allocator of BTree
. Of course, value_type
of alloc_
is K
. I'm using polymorphic allocators, so that it can allocate or deallocate from memory resources from the main memory or the disk file (which will be my main use case).
keys_
is not initialized, it is just allocated as raw memory. I don't want to initialize it at constructor of Node
unless it is really necessary.
To get to the point, is it safe to insert key like node->keys[i] = K;
? The type restriction of keys is as follows:
template <typename T>
concept DiskAllocable = std::is_same_v<std::remove_cvref_t<T>, T>
&& std::is_trivially_copyable_v<T> && (sizeof(T) % alignof(T) == 0);
Other than these, there are no more restrictions. Is it safe to assign an object of type T
to uninitialized memory T*
? Or do I need more restrictions?
Upvotes: 0
Views: 83
Reputation: 12362
If you use construct_at
then you don't have any restrictions and alloc_.allocate<T>(n)
will allocate you a suitably allocated block of memory.
Upvotes: 1