C ++ векторная реализация - удаление элементов

Question

Я реализую векторный тип.Меня совсем не беспокоят алгоритмы или структура данных, но я не уверен насчет метода удаления.например:

bool Remove(Node* node)
{
 /* rearrange all the links and extract the node */

 delete node;
}

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

Node* currentNode = MoveToRandNode();
Remove(currentNode);
cout << currentNode->value;

Если бы currentNode был указателем на указатель, это было бы проще, но ... это не так.

Answer 1

Вы можете добавить еще один уровень абстракции для вашего итератора (который теперь является необработанным указателем). Если вы не обрабатываете необработанные указатели, но создаете какой-то класс итераторов вместо указателя, можно сделать недействительным итератор, итаким образом, он не контролируется, если кто-то пытается получить доступ к итератору после его удаления.

 class Iterator {
     Node operator*() {
       if (node) return *node; 
       else throw Something();}
   private:
     Node* node;
 }

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

Answer 2

Сделай шаг первым.Вам необходимо определить, кому «принадлежит» память, на которую указывает вектор.Это сам вектор или код, который использует вектор?Как только вы определите это, ответ будет простым - либо метод Remove () должен всегда удалять его, либо никогда.

Обратите внимание, что вы только что поцарапали поверхность возможных ошибок, и вы отвечаете «кому принадлежит"поможет решить другие возможные проблемы, такие как:

• Если вы копируете вектор, вам нужно скопировать элементы внутри него или только указатели (например, сделать мелкую или глубокую копию
• Когда вы уничтожаете вектор, должны ли вы уничтожать находящиеся в нем предметы?
• Когда вы вставляете предмет, вы должны сделать копию предмета, или вектор становится владельцем этого элемента?

Answer 3

Это похоже на «аннулирование итератора». Например, если у вас есть std::list l и std::list::iterator it, указывающие на этот список, и вы вызываете l.erase(it), то итератор it становится недействительным - то есть, если вы используете его каким-либо образом, вы получите неопределенное поведение ,

Таким образом, следуя этому примеру, вы должны включить в свою документацию метода Remove что-то вроде следующего: «указатель node недействителен и не может использоваться или разыменовываться после возврата этого метода».

(Конечно, вы также можете просто использовать std :: list и не пытаться заново изобретать колесо.)

Для получения дополнительной информации об аннулировании итератора см .: http://www.angelikalanger.com/Conferences/Slides/CppInvalidIterators-DevConnections-2002.pdf

Answer 4

Кроме того, что написал innochenti. Я думаю, что вы должны решить, что ожидается / желаемое поведение cout << currentNode->value;:

• Ошибка - (как писал innochenti node = nullptr)
• Значение по умолчанию - создать узел devault_value (который имеет некоторое значение по умолчанию для его value), а после delete node; сделать node=default_value

Answer 5

ну, вы не можете этого сделать, но некоторые модификации вашего кода могут повысить безопасность. Добавить ссылку

bool Remove(Node*& node)
{
 /* rearrange all the links and extract the node */

 delete node;
 node = nullptr;
}

проверка на nullptr

if(currentNode)
    cout << currentNode->value;

вероятно, вам нужно попробовать std :: shared_ptr