указатель на вектор в индексе против итератора - PullRequest
Новая
       19

указатель на вектор в индексе против итератора

3 голосов
/ 31 октября 2011

У меня есть vector myvec , который я использую в своем коде для хранения списка объектов в памяти. Я сохраняю указатель на текущий объект в этом векторе "normal" C , используя 

Object* pObj = &myvec[index];

Это все работает нормально, если ... myvec не становится достаточно большим, чтобы перемещаться во время push_back , когда pObj становится недействительным - векторы гарантируют, что данные последовательны следовательно, они не прилагают никаких усилий, чтобы сохранить вектор в одной и той же ячейке памяти.

Я могу зарезервировать достаточно места для myvec, чтобы предотвратить это, но мне не нравится это решение.

Я мог бы сохранить индекс выбранной позиции myvec, и когда мне нужно его использовать, просто получи к нему прямой доступ, но это дорогостоящее изменение моего кода.

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

Object* pObj = &myvec[index];

чем-то вроде 

vector<Object>::iterator = myvec.begin()+index;

Каковы последствия этого?

Это выполнимо?

Каков стандартный шаблон для сохранения указателей на векторные позиции?

Приветствия

Ответы [ 3 ]

3 голосов
/ 31 октября 2011

Нет ... при использовании итератора у вас точно такая же проблема.Если векторное перераспределение выполняется, то все итераторы становятся недействительными, и для них используется неопределенное поведение.

Единственное решение, которое устойчиво к перераспределению с std::vector, использует целочисленный индекс.

Использованиенапример, std::list все по-другому, но есть и другие компромиссы эффективности, так что это действительно зависит от того, что вам нужно сделать.

Другой вариант - создать свой собственный класс «интеллектуального индекса», в котором хранятсяссылка на вектор и индекс.Таким образом, вы могли бы просто обойти один «указатель» (и вы могли бы реализовать для него семантику указателя), но код не страдал бы от рисков перераспределения.

3 голосов
/ 31 октября 2011

Итераторы (потенциально) аннулируются любым, что может изменить размер вектора (например, push_back).

Вы можете, однако, создать свой собственный класс итератора, в котором хранится вектор и индекс, который будет стабильным для всех операций, изменяющих размер вектора: 

#include <iterator>
#include <algorithm>
#include <iostream>
#include <vector>

namespace stable {

template <class T, class Dist=ptrdiff_t, class Ptr = T*, class Ref = T&>
class iterator : public std::iterator<std::random_access_iterator_tag, T, Dist, Ptr, Ref>
{
    T &container_;
    size_t index_;
public:
    iterator(T &container, size_t index) : container_(container), index_(index) {}

    iterator operator++() { ++index_; return *this; }
    iterator operator++(int) { iterator temp(*this); ++index_; return temp; }
    iterator operator--() { --index_; return *this; }
    iterator operator--(int) { stable_itertor temp(*this); --index_; return temp; }
    iterator operator+(Dist offset) { return iterator(container_, index_ + offset); }
    iterator operator-(Dist offset) { return iterator(container_, index_ - offset); }

    bool operator!=(iterator const &other) const { return index_ != other.index_; }
    bool operator==(iterator const &other) const { return index_ == other.index_; }
    bool operator<(iterator const &other) const { return index_ < other.index_; }
    bool operator>(iterator const &other) const { return index_ > other.index_; }

    typename T::value_type &operator *() { return container_[index_]; }
    typename T::value_type &operator[](size_t index) { return container_[index_ + index]; }
};

template <class T>
iterator<T> begin(T &container) { return iterator<T>(container, 0); }

template <class T>
iterator<T> end(T &container) { return iterator<T>(container, container.size()); }

}

#ifdef TEST
int main() { 

    std::vector<int> data;

    // add some data to the container:
    for (int i=0; i<10; i++)
        data.push_back(i);

    // get iterators to the beginning/end:
    stable::iterator<std::vector<int> > b = stable::begin(data);
    stable::iterator<std::vector<int> > e = stable::end(data);

    // add enough more data that the container will (probably) be resized:
    for (int i=10; i<10000; i++)
        data.push_back(i);

    // Use the previously-obtained iterators:
    std::copy(b, e, std::ostream_iterator<int>(std::cout, "\n"));

    // These iterators also support most pointer-like operations:
    std::cout << *(b+125) << "\n";
    std::cout << b[150] << "\n";

    return 0;
}
#endif

Поскольку мы не можем встроить это как вложенный класс внутри контейнера, как обычный класс итератора, для объявления / определения объекта этого типа требуется немного другой синтаксис; вместо обычного std::vector<int>::iterator whatever; мы должны использовать stable::iterator<std::vector<int> > whatever;. Аналогично, чтобы получить начало контейнера, мы используем stable::begin(container).

Есть один момент, который может быть немного удивительным (по крайней мере, на первый взгляд): когда вы получаете stable::end(container), это дает вам конец контейнера в это время . Как показано в приведенном выше тестовом коде, если позже вы добавите больше элементов в контейнер, полученный ранее итератор будет , а не , скорректированный с учетом нового конца контейнера - он сохранит положение, которое он имел, когда вы получил его (т. е. позиция, в которой был концом контейнера в то время, но не больше).

2 голосов
/ 31 октября 2011

Нет, итераторы становятся недействительными после роста вектора.

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

...