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