二进制搜索用任意字节数编码的整数列表

Question

排序整数的列表被编码在uint8_t向量中。编码这些整数的字节数是任意的。

例如，如果我们使用3个字节来编码每个整数，那么第一个整数编码在前3个字节，第二个整数编码在后3个字节，依此类推。

我想从这个 uint8_t 向量中二进制搜索一个整数。

我目前的尝试： std::bsearch 似乎是我想要的。其中，我可以以字节为单位指定数组中每个元素的大小。但是，要实现比较器功能，我需要访问一个以字节为单位存储每个元素大小的变量。 std::bsearch 是一个 C 函数，因此编译器不允许我访问 class 成员变量，该成员变量以字节为单位存储每个元素的大小。全局变量可以，但是存为全局变量很难看...

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-byte 数字的开头。如果你需要底层迭代器，你可以调用 result.underlying()

或者，这可以在 std::binary_search 中用于检测一般元素的存在而无需找到底层迭代器（如问题中所述）。

注意：以上代码未经测试——可能有一两个错字，但该过程应该按照描述进行。

编辑： 另请注意，只有当基础迭代器范围是 N 的倍数时，这才能正常工作！如果不是，那么您将报告不正确的范围，这也将导致推进迭代器可能移动超过 end 迭代器，这将是未定义的行为。在以这种方式包装迭代器之前先检查边界很重要。

编辑 2： 如果 N-byte 整数可以超过像 int64_t 这样的大值，但遵循简单的启发式方法，您也可以使 [迭代器的 =38=] 是具有 well-defined 比较运算符的自定义 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

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

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

return std::to_address(m_it);

Answer 2

您要比较的对象存储在vector中的几个元素中。所以 std::binary_search 不能直接应用于 vector.

一种方法是应用 std::bsearch on the raw data of vector (vecter::data())，因为 std::bsearch 可以 按指定大小对数据进行分组 。所以它看起来像：

std::bsearch((void*)key_array,(void*)data_vector.data(),data_vector.size()/3,3*sizeof(uint8_t),
    [](const void *a, const void *b){return decode((uint8_t*)a)-decode((uint8_t*)b)});

二进制搜索用任意字节数编码的整数列表

Binary search a list of integers that are encoded with arbitary number of bytes

c++

binary-search