列表排序的整数被编码在uint8_t
vector 中。
编码这些整数的字节数是任意的。
例如,如果我们使用3个字节对每个整数进行编码,则第一个整数在前3个字节中进行编码,第二个整数在后3个字节中进行编码,依此类推。
我想从此uint8_t
vector 二进制搜索一个整数。
到目前为止,我的尝试:std::bsearch
似乎是我想要的。在其中,我可以以字节为单位指定数组中每个元素的大小。但是,要实现比较器功能,我需要访问一个变量,该变量以字节为单位存储每个元素的大小。 std::bsearch
是C函数,因此编译器不允许我访问存储每个元素的大小(以字节为单位)的类成员变量。全局变量有效,但是将其存储为全局变量是很丑的。std::binary_search
需要一个迭代器。
我想我需要迭代器来跳过一定数量的字节。
我不知道如何做到这一点。
最佳答案
首先想到的是定义一个自定义迭代器,该迭代器包装另一个迭代器,并一次处理一系列N
字节。这将使包装的迭代器易于在std::binary_search
中使用,而不会被困重写它。
基本上,该实用程序将具有以下内容:
operator++
)一次处理N
字节operator--
)一次处理N
字节operator+
)一次增加N * i
个字节,operator-
)报告d / N
的距离(以说明N
字节和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);
关于c++ - 二进制搜索以任意数量的字节编码的整数列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63270683/