§23.1.2.8 в стандарте заявляет, что операции вставки/удаления на множестве/карте не будут аннулировать любые итераторы для этих объектов (кроме итераторов, указывающих на удаленный элемент).
Теперь рассмотрим следующую ситуацию: вы хотите реализовать граф с уникально нумерованными узлами, где каждый node имеет фиксированное число (скажем, 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 (см. ответы/комментарии), но в любом случае по этим строкам)
Это хорошо, потому что таким образом вы можете вставлять и удалять узлы без аннулирования согласованности структуры (при условии, что вы отслеживаете удаления и удаляете удаленный итератор из каждого массива node).
Но скажем, вы также захотите сохранить "недопустимое" или "несуществующее" значение соседа. Не волнуйтесь, мы можем просто использовать nodes.end()
... или можем ли мы? Есть ли какая-то гарантия того, что nodes.end()
в 8 утра будет таким же, как nodes.end()
в 10 вечера после zillion вставки/удаления? То есть, могу ли я безопасно ==
сравнить итератор, полученный как параметр, в 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
?
И если это тоже не сработает, что я могу сделать, чтобы оставить место для недопустимого значения соседа?