Найти пустой указатель в контейнере указателей MyClass? - PullRequest
Новая
       45

Найти пустой указатель в контейнере указателей MyClass?

0 голосов
/ 05 января 2019

У меня есть указатель void* p, который указывает на переменную неизвестного типа, а также контейнер std::set<MyClass*> c, заполненный указателями MyClass. Есть ли какой-нибудь способ выяснить, содержит ли c p (то есть содержит ли он указатель, который указывает на тот же адрес памяти, что и p) без ручного циклического перебора элементов в c, что не вызывает неопределенное поведение? (Обратите внимание, что я не буду разыменовывать p, если не найду его в c.)

Кроме того, я предполагаю, что приведение p к MyClass* вызовет неопределенное поведение, если p будет указывать на переменную типа данных, которая не связана, но относится к MyClass, но, возможно, это не так?

Ответы [ 3 ]

0 голосов
/ 05 января 2019

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

Если у вас есть класс, производный от другого класса (скажем, OtherClass) и MyClass, то вам нужно убедиться, что p указывает на MyClass часть, а не OtherClass. Хотя у вас не будет неопределенного поведения, вы не найдете этот предмет. 

class OtherClass { int someData; };
class WontWork : public OtherClass, public MyClass { };

auto *w = new WontWork();
c.insert(w);
void *p = w;

В этом случае вы не найдете p в наборе, поскольку значение p отличается от значения, вставленного в набор (после неявного приведения к MyClass *).

Чтобы код работал, вам нужно p указать на MyClass часть, выполнив что-то вроде: 

void *p = static_cast<MyClass *>(w);

или 

MyClass *mc = w;
p = mc;

Но тогда вы должны убедиться, что вы не используете p, как если бы он был типа OtherClass или WontWork где-нибудь в коде.

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

0 голосов
/ 06 января 2019

Я предполагаю, что приведение p к MyClass* вызовет неопределенное поведение, если [..]

Педантически правильно, что это может вызвать UB.

Но, вероятно, должно работать на практике (Радость UB).

Есть ли какой-нибудь способ выяснить, содержит ли c p [..] без циклического обхода элементов в c.

std::find_if или std::binary_search можно использовать с соответствующим предикатом, чтобы найти его за линейное время (std::set::iterator не является случайным итератором, поэтому «фальсифицирует» binary_search сложность).

Если вы можете изменить свой контейнер на:

  • std::set<MyClass*, std::less<void>>, тогда вы можете спокойно использовать std::set::find благодаря прозрачному компаратору.

  • отсортировано std::vector<MyClass*>, тогда вы можете использовать std::binary_search с правильной сложностью.

0 голосов
/ 05 января 2019

Вы можете безопасно привести void* к другому указателю, но не следует разыменовывать его. Поиск указателя в std::set<T*> не разыменовывает указатель (если не указан пользовательский предикат сравнения, который это делает).

Педантично, стандарт C ++ говорит, что просто загрузка неверного указателя - неопределенное поведение. Однако это условие для аппаратных архитектур с сегментированной адресацией (реальный режим x86), где загрузка указателя загружает часть его значения в регистр сегмента, что может вызвать аппаратную ловушку. В современных архитектурах с плоскими моделями памяти это ограничение не применяется, загрузка любого значения указателя четко определена, поскольку это всего лишь загрузка в регистр ЦП общего назначения.

Что-то вроде: 

MyClass* find(std::set<MyClass*> const& c, void* p) {
    auto found = c.find(static_cast<MyClass*>(p));
    return found != c.end() ? *found : nullptr;
}

Вы можете использовать его как: 

std::set<MyClass*> c;
void* p = ...;
if(MyClass* q = find(c, p))
   // p is found and is q
...