mercredi 20 juillet 2022

C++ How can I move or swap pair

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