模板化有序向量和 std::set

Question

所以我想要一个接口，可以按顺序存储一些数字并有效地对它们执行一些操作。在实践中，排序向量对于小尺寸表现非常好，但对于理论性能和更大实例的性能，我还需要一个变体，它使用类似 std::set 的东西在 O(log n) 时间内执行插入和擦除。

这里是向量变化的一些实现：

#include <vector>
#include <algorithm>

class Numbers {
public:
    template<class ForwardIt>
    void unguarded_insert(ForwardIt it, int val) { vec.insert(it, val); }

    auto lower(int val) { return std::lower_bound(vec.begin(), vec.end(), val); }
    
    template<class ForwardIt>
    void unguarded_replace(ForwardIt it, int val) { *it = val; }

    template<class ForwardIt>
    auto erase_elements(ForwardIt first, ForwardIt last) { return vec.erase(first, last); }
    
private:
    std::vector<int> vec;
};

请注意，对于插入和替换它，调用者确保它们位于正确的位置。例如，调用者可能想删除 20 到 50 之间的所有元素并插入 30。因此可以调用 lower_bound，替换第一个元素并删除剩余范围。

我不想将整个界面写两次，而是想要一个使用容器类型作为模板参数的模板化解决方案。但是，我运行遇到了诸如 lower_bound 是某些容器的成员函数和其他容器的自由函数之类的问题。 std::set 也不能真正在迭代器上插入和替换，因为顺序被不必要地检查了（对吧？）。

那么有什么方法可以解决这些问题，或者有其他方法可以解决我的问题吗？该解决方案不应在任何一个容器上做不必要的工作，只是为了让它在两个容器上都能工作。

Answer 1

您可能不需要多次实现所有成员函数，但对于某些成员函数，您需要以不同的方式实现。

首先，检查 lower_bound 成员函数是否存在的类型特征

template<class T>
struct has_lower_bound_member_func {
    struct no {};

    template<class U = T>  // on SFINAE match: `auto` is the type of the iterator
    static auto check(int) -> 
        decltype(std::declval<U>().lower_bound(
            std::declval<typename U::value_type>()));

    static no check(long); // No lower_bound found, the type is `no`

    // if the type is *not* `no`, the container has a lower_bound member function
    static constexpr bool value = not std::is_same_v<decltype(check(0)), no>;
};

template<class T>
inline constexpr bool has_lower_bound_member_func_v = 
                          has_lower_bound_member_func<T>::value;

检查迭代器是否为 const_iterator:

的类型特征

template<class It>
struct is_const_iterator {
    using pointer = typename std::iterator_traits<It>::pointer; 

    static const bool value = std::is_const_v<std::remove_pointer_t<pointer>>;
};

template<class T>
inline constexpr bool is_const_iterator_v = is_const_iterator<T>::value;

以下是如何使用这些特征（以及您添加的任何未来特征）的几个示例。您可以对其他需要特别注意的成员函数使用类似的技术：

template<class C>
class Numbers {
public:
    using value_type = typename C::value_type;

    template<class T = C>
    auto lower(const value_type& val) {

        if constexpr (has_lower_bound_member_func_v<T>) {
            // a std::set<> will use this
            return data.lower_bound(val);

        } else {
            // a std::vector<> will use this
            return std::lower_bound(data.begin(), data.end(), val);
        }
    }

    template<class ForwardIt>
    auto replace(ForwardIt it, const value_type& val) {
        if constexpr(is_const_iterator_v<ForwardIt>) {

            // move the object out of the container by moving its node
            // out of the set and reinsert if afterwards:

            auto node_handle = data.extract(it);
            node_handle.value() = val;
            return data.insert(std::move(node_handle));

            // or, if "it" is likely pointing close to the old value:
            // return data.insert(it, std::move(node_handle));

        } else {            
            *it = val; // not a const_iterator, assign directly
            // You probably need to sort here:
            std::sort(data.begin(), data.end());
            it = std::lower_bound(data.begin(), data.end(), val);
            // ... or do a clever std::rotate() to get it in place.
            return it;
        }
    }
    
private:
    C data;
};

模板化有序向量和 std::set

Templating ordered vector and std::set

c++

templates

stl

stdvector

stdset