Можете ли вы найти итератор для элемента списка, учитывая указатель на элемент?

ProgramBox

Можете ли вы найти итератор для элемента списка, учитывая указатель на элемент?

Post author:admin
Запись опубликована:28 августа, 2022
Post category:Вопросы по программированию

#c #list #iterator

#c #Список #итератор

Вопрос:

Вопрос, вероятно, не требует пояснений, но если у меня есть std::list<T> объект, существует ли какой-либо стандартный метод для получения итератора для элемента, учитывая T* значение, которое указывает на элемент?

Если T это пользовательский тип, кажется, что разыменование указателя и использование find_if выполнят эту работу, но мне это кажется неэффективным. Если вы пытаетесь найти элемент в контейнере по значению, имеет смысл, что вам нужно будет перебирать контейнер, пока вы что-то не найдете. Но если у вас есть указатель, интуитивно кажется, что должен быть более прямой метод. Мое базовое понимание заставляет меня думать, что между итератором элемента списка и его указателем должно быть какое-то отношение 1 к 1, поскольку списки в STL имеют двойную связь, но у меня действительно не так много, чтобы подтвердить это.

Я не очень хорошо знаком с итераторами C , поэтому, если кто-нибудь может объяснить, почему есть или нет способа сделать это, это было бы полезно.

редактировать: Potatoswatter предоставил хорошее решение для C 11, но мне все равно было бы интересно, были ли доступны какие-либо решения, совместимые с C 03.

1. Я не понимаю вопроса — вы спрашиваете, как найти элемент в списке, учитывая указатель на элемент, который нужно найти?

2. std::list<T> храните объекты типа T . Учитывая an std::list<T>::iterator , вы можете получить ссылку на объект, которую вы можете использовать для получения адреса объекта. Однако указатель не будет знать о месте объекта, на который он указывает в std::list .

Ответ №1:

Не существует стандартного алгоритма для поиска итератора в диапазоне, который удовлетворяет условию. find использует значение элемента, но это просто не одно и то же. find_if с помощью лямбда-выражения, которое сравнивает адреса, будет работать.

Легко написать общую версию:

 template< typename iter, typename t >
iter iterator_from_ptr( iter first, iter last, t * ptr ) {
    while ( first != last ) {
        // For C  03 compatibility, use amp;* first instead of addressof.
        if ( std::addressof( * first ) == ptr ) return first;
           first;
    }
    return last;
}

Использование: iterator_from_ptr( my_list.begin(), my_list.end(), ptr ) .

Как вы упомянули, это неэффективно, O (N), чтобы быть конкретным. Ускорение противоречит правилам C : у вас есть указатель на объект, который является членом std::list узла, и list::iterator фактически является указателем на std::list узел. Но (обычно) нет способа перейти от указателя на элемент к указателю на весь объект. (Не говоря уже о том, что мешает абстракция итератора.)

1. std::addressof не входит C 03 . Я думаю, это стоит упомянуть.

2. Спасибо за ответ Potatoswatter. Я не упоминал об этом в исходном вопросе, но в std::list<T> нем не так много элементов, но T он довольно большой, поэтому сравнение значений может стать сложным и потенциально медленным. O(N) все еще немного облом, но для моей конкретной проблемы это определенно достаточно хорошо.

3. @Matt Как указано в самом ответе, просто используйте amp;*first . Пока T не перегружает унарный operator amp; ( дрожит ), все в порядке.

Ответ №2:

std::find() <algorithm> Работает ли для вас? Он должен работать, если operator== реализован тип значения.

 #include <algorithm>
auto it = std::find(list.begin(), list.end(), *ptr);

1. Я не думаю, что он этого хочет. В списке может быть более одного элемента, равного *ptr . Ему не нужен первый, который соответствует *ptr . Ему нужен итератор, который указывает на элемент, адрес которого ptr .

2. Это стало ясно только с более поздним комментарием в другом ответе:-(

Ответ №3:

Хотя я не рекомендую приведенное ниже, эта функция выполняет то, что вы просите. Он основан на знании реализации списка, так что на самом деле это просто забавное упражнение, и на него не следует полагаться в производственном коде 🙂

 template <typename T>
typename list<T>::iterator iteratorFromPtr(T* a)
{
 auto offset = offsetof(_List_node<T>, _M_data);
 void* ptr = (void*)a;
 ptr -= offset;
 return _List_iterator<T>(static_cast<_List_node<T>*>(ptr));
}

РЕДАКТИРОВАТЬ: протестировано с помощью gcc-4.8.2.

Ответ №4:

Вам нужно будет определить / реализовать итератор в вашем классе. Я обычно использую указатель, если я не хочу реализовывать итератор.