проверка, указывает ли указатель в массиве

Question

Могу ли я проверить, указывает ли данный указатель на объект в массиве, заданном его границами?

template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
    return begin <= p && p < end;
}

Или вызовет сравнение указателя неопределенное поведение, если p указывает за пределыиз массива?В таком случае, как мне решить проблему?Это работает с пустыми указателями?Или это невозможно решить?

Answer 1

Хотя сравнение действительно только для указателей в массиве и «один за концом», допустимо использовать набор или карту с указателем в качестве ключа, который использует std::less<T*>

В 1996 году было большое обсуждение этого вопроса по comp.std.c ++

Answer 2

Прямо из документации MSDN :

Два указателя разных типов нельзя сравнивать, если:

• Один тип является производным типа классаиз другого типа.
• По крайней мере один из указателей явно преобразован (приведен) в тип void *.(Другой указатель неявно преобразуется в тип void * для преобразования.)

Таким образом, void* можно сравнить с чем-либо еще (включая другой void*).Но даст ли сравнение значимые результаты?

Если два указателя указывают на элементы одного и того же массива или один элемент за концом массива, указатель на объект с более высоким индексом сравнивается выше,Сравнение указателей гарантировано действительным только в том случае, если указатели ссылаются на объекты в одном и том же массиве или на местоположение за концом массива.

Похоже, что нет.Если вы уже не знаете , что вы сравниваете элементы внутри массива (или просто мимо него), то сравнение не обязательно будет значимым.

Однако существуетРешение: STL предоставляет std::less<> и std::greater<>, которые будут работать с любым типом указателя и будут давать действительные результаты во всех случаях:

if (std::less<T*>()(p, begin)) {
    // p is out of bounds
}

Обновление:

Ответ на на этот вопрос дает то же самое предположение (std::less), а также цитирует стандарт.

Answer 3

Единственно правильный способ сделать это - такой подход.

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));
}

Answer 4

Стандарт C ++ не определяет, что происходит, когда вы сравниваете указатели с объектами, которые не находятся в одном и том же массиве, следовательно, с неопределенным поведением.Однако стандарт C ++ - не единственный стандарт, которому должна соответствовать ваша платформа.Другие стандарты, такие как POSIX, определяют вещи, которые стандарт C ++ оставляет как неопределенное поведение.На платформах с виртуальным адресным пространством, таких как Linux и Win32 / 64, вы можете сравнивать любые указатели, не вызывая неопределенного поведения.

Answer 5

сравнения типов указателей не обязательно приводят к общему порядку.std :: less / std :: большее_equal, однако.Так что ...

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);
}

будет работать.

Answer 6

Не могли бы вы сделать это с std::distance, т.е. ваша проблема фактически сводится к:

return distance(begin, p) >= 0 && distance(begin, p) < distance(begin, end);

Учитывая, что этот итератор произвольного доступа (указатель) передается, он должен сводиться к некоторому указателюарифметика, а не сравнение указателей?(Я предполагаю, что конец действительно является концом, а не последним элементом в массиве, если последний затем изменить меньше, чем на <=).

Я мог бы быть далеко от цели ...