Первое, что приходит на ум при этом, - это определить собственный итератор, который объединяет другой итератор и работает с последовательностью 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, но следуйте simple heuristi c, вы также можете сделать 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);