I'm writing a B-Tree class. I want to support for all four cases like std::set
, std::multiset
, std::map
, std::multimap
.
I verified that my code works correctly for first two cases. The problem is the latter two. Their declarations are like this:
template <typename T>
concept Containable = std::is_same_v<std::remove_cvref_t<T>, T>;
using index_t = std::ptrdiff_t;
template <Containable K, index_t t = 2, typename Comp = std::ranges::less,
typename Alloc = std::allocator<K>>
using BTreeSet = detail::BTreeBase<K, K, t, Comp, false, Alloc>;
template <Containable K, index_t t = 2, typename Comp = std::ranges::less,
typename Alloc = std::allocator<K>>
using BTreeMultiSet = detail::BTreeBase<K, K, t, Comp, true, Alloc>;
template <Containable K, Containable V, index_t t = 2,
typename Comp = std::ranges::less,
typename Alloc = std::allocator<std::pair<const K, V>>>
using BTreeMap = detail::BTreeBase<K, std::pair<const K, V>, t, Comp, false, Alloc>;
template <Containable K, Containable V, index_t t = 2,
typename Comp = std::ranges::less,
typename Alloc = std::allocator<std::pair<const K, V>>>
using BTreeMultiMap =
detail::BTreeBase<K, std::pair<const K, V>, t, Comp, true, Alloc>;
BTreeBase
is like this
template <Containable K, typename V, index_t t, typename Comp, bool AllowDup,
typename Alloc>
requires(t >= 2) class BTreeBase {
// ... details ...
};
For BTreeMap
the value_type
is std::pair<const K, V>
. For associative containers, changing keys via dereferencing iterators is unacceptable.
This line gives me a headache:
x->keys_[i] = std::move(y->keys_[t - 1]);
It doesn't compile. std::iter_swap
or std::swap
don't work
Here x
and y
are BTreeBase::Node
and keys_
is std::vector<value_type, Alloc>
.
Standard library containers std::map
, std::unordered_map
uses the same approach but they don't have this problem, because it is based on red-black trees and hash tables, so a node has exactly single key, so you can just move a node, not a key.
But B-Tree is a different beast. A node has many keys, and moving or swapping keys between nodes should be possible. (user still should not be allowed to change key from outside)
How can I deal with this?
Aucun commentaire:
Enregistrer un commentaire