Можно ли проверить, указывает ли данный указатель на объект внутри массива, заданный его границами?
template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
return begin <= p && p < end;
}
Или сопоставление указателей вызывает поведение undefined, если p указывает за пределы массива? В этом случае, как я могу решить проблему? Работает ли она с указателями void? Или это невозможно решить?
Хотя сравнение действительно только для указателей внутри массива и "один за концом", допустимо использовать набор или карту с указателем в качестве ключа, который использует std::less<T*>
В 1996 году была проведена большая дискуссия на comp.std.c++
Прямо из Документация MSDN:
Два указателя разных типов не могут сравниваться, если:
- Один тип - это тип класса, полученный из другого типа.
- По крайней мере, один из указателей явно преобразован (cast), чтобы набрать void *. (Другой указатель неявно преобразован в тип void * для преобразования.)
Итак, a void* можно сравнить с чем-либо еще (включая другой void*). Но приведет ли сравнение к значимым результатам?
Если два указателя указывают на элементы тот же массив или один элемент за пределами массива, указатель на объект с более высоким индекс выше. сравнение указателей гарантируется только когда указатели ссылаются на объекты в тот же массив или местоположение мимо конца массива.
Похоже, нет. Если вы еще не знаете, что вы сравниваете элементы внутри массива (или просто мимо него), сравнение не гарантируется.
Однако существует решение: STL предоставляет std::less<> и std::greater<>, который будет работать с любым типом указателя и будет давать достоверные результаты во всех случаях:
if (std::less<T*>()(p, begin)) {
// p is out of bounds
}
Update:
Ответ на этот вопрос дает то же предложение (std::less), а также цитирует стандарт.
В стандарте С++ не указывается, что происходит, когда вы сравниваете указатели на объекты, которые не находятся в одном массиве, поэтому поведение undefined. Однако стандарт С++ не является единственным стандартом, который должна соответствовать вашей платформе. Другие стандарты, такие как POSIX, указывают на то, что стандарт С++ выходит за поведение undefined. На платформах с виртуальным адресным пространством, таким как Linux и Win32/64, вы можете сравнивать любые указатели, не вызывая поведения undefined.
Единственный правильный способ сделать это - такой подход.
template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
for (; begin != end; ++begin)
{
if (p == begin)
return true;
}
return false;
}
Очевидно, что это не работает, если T == void. Я не уверен, что два void* технически определяют диапазон или нет. Конечно, если бы у вас было Derived[n], было бы неверно сказать, что (Base*)Derived, (Base*)(Derived + n) определил допустимый диапазон, поэтому я не вижу его действительным для определения диапазона с чем-либо, кроме указателя на фактический тип элемента массива.
Приведенный ниже метод терпит неудачу, потому что неизвестно, что возвращает <, если два операнда не указывают на членов одного и того же объекта или элементов одного и того же массива. (5.9 [expr.rel]/2)
template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
return !(p < begin) && (p < end);
}
Ниже описан метод ниже, так как также не указано, что возвращает std::less<T*>::operator(), если два операнда не указывают на членов одного и того же объекта или элементов одного и того же массива.
Верно, что std::less должен быть специализирован для любого типа указателя, чтобы получить общий порядок, если встроенный < не работает, но это полезно только для использования, например, для предоставления ключа для set или map. Не гарантируется, что общий порядок не будет чередовать отдельные массивы или объекты вместе.
Например, в сегментированной архитектуре памяти смещение объекта может быть использовано для < и как наиболее значимый дифференциатор для std::less<T*> с индексом сегмента, используемым для разрыва связей. В такой системе элемент одного массива можно упорядочить между границами второго отдельного массива.
template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
return !(std::less<T*>()(p, begin)) && (std::less<T*>()(p, end));
}
Сравнение типов указателей не обязательно приводит к общему порядку. std:: less/std:: more_equal do, однако. Итак...
template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
return std::greater_equal<T*>()(p, begin) && std::less<T*>()(p, end);
}
будет работать.
Не могли бы вы сделать это с помощью std::distance, т.е. ваша проблема эффективно сводится к:
return distance(begin, p) >= 0 && distance(begin, p) < distance(begin, end);
Учитывая, что этот случайный итератор доступа (указатель) передается, он должен сводиться к некоторой арифметике указателя, а не по сравнению с сравнениями указателей? (Я предполагаю, что конец действительно завершен, а не последний элемент в массиве, если последний затем изменил значение меньше, чем на <=).
Я мог бы быть в стороне от отметки...