§23.1.2.8 в стандарте гласит, что операции вставки / удаления в наборе / карте не будут делать недействительными никакие итераторы для этих объектов (кроме итераторов, указывающих на удаленный элемент).
Теперь рассмотрим следующую ситуацию: вы хотите реализовать граф с узлами с уникальной нумерацией, где каждый узел имеет фиксированное число (скажем, 4) соседей. Воспользовавшись приведенным выше правилом, вы делаете это так:
class Node {
private:
// iterators to neighboring nodes
std::map<int, Node>::iterator neighbors[4];
friend class Graph;
};
class Graph {
private:
std::map<int, Node> nodes;
};
( РЕДАКТИРОВАТЬ : Буквально не так из-за неполноты Node в строке 4 (см. Ответы / комментарии), но в любом случае по этим линиям)
Это хорошо, потому что таким образом вы можете вставлять и удалять узлы, не нарушая целостность структуры (при условии, что вы отслеживаете удаления и удаляете удаленный итератор из массива каждого узла).
Но допустим, вы также хотите иметь возможность хранить «недопустимое» или «несуществующее» значение соседа. Не волнуйтесь, мы можем просто использовать nodes.end() ... или мы можем? Есть ли какая-то гарантия, что nodes.end() в 8 часов утра будет таким же, как nodes.end() в 10 часов вечера после миллионного добавления / удаления? То есть можно ли безопасно == сравнить итератор, полученный в качестве параметра, с nodes.end() в некотором методе Graph?
А если нет, будет ли это работать?
class Graph {
private:
std::map<int, Node> nodes;
std::map<int, Node>::iterator _INVALID;
public:
Graph() { _INVALID = nodes.end(); }
};
То есть я могу сохранить nodes.end() в переменной при построении, а затем использовать эту переменную всякий раз, когда я хочу установить для соседа недопустимое состояние, или сравнивать его с параметром в методе? Или же возможно, что где-нибудь ниже действительный итератор, указывающий на существующий объект, будет сравниваться равным _INVALID?
И если это тоже не сработает, что может сделать, чтобы освободить место для недопустимого значения соседа?