c++ - 二进制搜索以任意数量的字节编码的整数列表

Question

列表排序的整数被编码在uint8_t vector 中。
编码这些整数的字节数是任意的。
例如，如果我们使用3个字节对每个整数进行编码，则第一个整数在前3个字节中进行编码，第二个整数在后3个字节中进行编码，依此类推。
我想从此uint8_t vector 二进制搜索一个整数。
到目前为止，我的尝试:std::bsearch似乎是我想要的。在其中，我可以以字节为单位指定数组中每个元素的大小。但是，要实现比较器功能，我需要访问一个变量，该变量以字节为单位存储每个元素的大小。 std::bsearch是C函数，因此编译器不允许我访问存储每个元素的大小(以字节为单位)的类成员变量。全局变量有效，但是将其存储为全局变量是很丑的。std::binary_search需要一个迭代器。
我想我需要迭代器来跳过一定数量的字节。
我不知道如何做到这一点。

Answer 1

首先想到的是定义一个自定义迭代器，该迭代器包装另一个迭代器，并一次处理一系列N字节。这将使包装的迭代器易于在std::binary_search中使用，而不会被困重写它。
基本上，该实用程序将具有以下内容:

迭代器应该是随机访问

每个增量(operator++)一次处理N字节

每个减量(operator--)一次处理N字节

每个加法(operator+)一次增加N * i个字节，

每个减法(operator-)报告d / N的距离(以说明N字节和

迭代器的值类型将足够大int以便轻松保存任意值长度(例如std::int64_t或其他值)

就像是:

// Iterator that skips N entries over a byte type
template <std::size_t N, typename Iterator>
class byte_iterator
{
public:
    // Ensure that the underlying type is 'char' (or some other 'byte' type, like std::byte)
    static_assert(std::is_same<typename Iterator::value_type, unsigned char>::value, "");
 
    using value_type = std::uint64_t;
    using reference = std::uint64_t;
    using pointer = value_type*;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;

    byte_iterator() = default;

    explicit byte_iterator(Iterator underlying)
      : m_it{underlying}
    {
    }

    byte_iterator(const byte_iterator&) = default;
    byte_iterator& operator=(const byte_iterator&) = default;

    byte_iterator& operator++() {
        std::advance(m_it, N);
        return (*this);
    }

    byte_iterator operator++(int) {
        auto copy = (*this);
        std::advance(m_it, N);
        return copy;
    }

    byte_iterator& operator--() {
        std::advance(m_it, -static_cast<std::ptrdiff_t>(N));
        return (*this);
    }

    byte_iterator operator--(int) {
        auto copy = (*this);
        std::advance(m_it, -static_cast<std::ptrdiff_t>(N));
        return copy;
    }

    byte_iterator& operator+=(std::ptrdiff_t n) {
        std::advance(m_it, static_cast<std::ptrdiff_t>(N) * n);
        return (*this);
    }

    byte_iterator& operator-=(std::ptrdiff_t n) {
        std::advance(m_it, -static_cast<std::ptrdiff_t>(N) * n);
        return (*this);
    }

    value_type operator*() const {
        // build your int here
        // The question doesn't indicate endianness, so this is up to you
        // this can just be a bunch of shifts / masks to create the int
    }

    bool operator==(const byte_iterator& other) const {
       return m_it == other.m_it;
    }

    bool operator!=(const byte_iterator& other) const {
       return m_it != other.m_it;
    }

    Iterator underlying() const { return m_it; }

private:
    Iterator m_it;
};

template <typename N, typename Iter>
std::ptrdiff_t operator-(const byte_iterator<N, Iter>& lhs, const byte_iterator<N, Iter>& rhs) {
    return (lhs.underlying() - rhs.underlying()) / 3;
}

template <typename N, typename Iter>
byte_iterator<N, Iter> operator+(const byte_iterator<N, Iter>& lhs, std::ptrdiff_t rhs) {
    return byte_iterator{lhs} += rhs;
};

template <typename N, typename Iter>
byte_iterator<N, Iter> operator-(const byte_iterator<N, Iter>& lhs, std::ptrdiff_t rhs) {
    return byte_iterator{lhs} -= rhs;
};


// other necessary operators...

template <std::size_t N, typename Iterator>
byte_iterator<N, std::decay_t<Iterator>> make_byte_iterator(Iterator it) {
    return byte_iterator<n, std::decay_t<Iterator>>{it};
}

注意: N不必在编译时作为模板参数进行固定，也可以在运行时作为构造函数参数进行固定。同样， Iterator不必是模板类型；我只是以此为例，以便它可以与任何基础迭代器一起使用。实际上，您可以简单地将其设置为 char*或其他名称，以便仅在连续的字节数组上使用。
为了比较的目的，所有需要实现的就是对int的重构，这可以根据字节序从一系列8位左移和掩码中完成。

使用这样的迭代器包装器，我们可以使用 std::lower_bound进行简单的二进制搜索来找到迭代器:

// Assuming 3-byte numbers:

const auto value = 42;
auto byte_numbers = std::vector<unsigned char>{...};

// ensure we have an increment of 3 bytes, otherwise the 
// iterators will break
assert(byte_numbers.size() % 3 == 0);

auto result = std::lower_bound(
    make_byte_iterator<3>(byte_numbers.begin()),
    make_byte_iterator<3>(byte_numbers.end()), 
    value
);

result迭代器将通过 byte_iterator包含一个基础迭代器，该迭代器指向您需要检索的N字节数字的开头。如果需要基础迭代器，则可以调用 result.underlying()或者，可以在 std::binary_search中使用它来通常检测元素的存在而无需找到底层的迭代器(如问题中所述)。
注意:上面的代码未经测试-可能有两个或两个错字，但该过程应按所述进行。

编辑:另外请注意，仅当基础迭代器范围是 N的倍数时，此方法才能正确运行!如果不是，那么您将报告错误的范围，这也将导致前进的迭代器有可能超过 end迭代器，这将是未定义的行为。在以这种方式包装迭代器之前，首先检查边界很重要。
编辑2:如果N字节整数可以超过 int64_t之类的较大值，但是遵循简单的试探法，您还可以将迭代器的 value_type设为自定义的 arbitrary_int类型，该类型具有明确的比较运算符。例如:

template <std::size_t N>
class arbitrary_int {
public:
    arbitrary_int(const unsigned char* integer)
      : m_int{integer}
    {
    }

    // assuming we can lexicographically compare all bytes
    bool operator==(const arbitrary_int<N>& rhs) const {
        return std::equal(m_int, m_int + N, rhs.m_int, rhs.m_int + N);
    }
    bool operator!=(const arbitrary_int<N>& rhs) const {
        return !(*this == rhs);
    }
    bool operator<(const arbitrary_int<N>& rhs) const {
        return std::lexicographical_compare(m_int, m_int + N, rhs.m_int, rhs.m_int + N);
    }
    bool operator>(const arbitrary_int<N>& rhs) const {
        return rhs < *this;
    }
    bool operator<=(const arbitrary_int<N>& rhs) const {
        return !(rhs < *this);
    }
    bool operator>=(const arbitrary_int<N>& rhs) const {
        return !(*this < *rhs);
    }

private:
    const unsigned char* m_int;
};

在这种情况下， byte_iterator<N,Iterator>::operator*()现在将返回

return arbitrary_int<N>{m_it.operator->()}

或者，如果您使用的是c++ 20，

return std::to_address(m_it);