C++矢量实现 - 删除元素

-1

我正在实现矢量类型。我一点都不担心算法或数据结构，但我不确定删除方法。例如：C++矢量实现 - 删除元素

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

delete node; 
}

其中节点是一个指向我们在当前节点。但是，如果我删除节点，然后如何防止这种情况的发生：

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

如果currentNode是一个指针的指针会更容易些。但它不是。

来源

2012-03-14 s5s

那么C或C++？根据选择的语言，答案会有很大差异。 – 2012-03-14 15:38:09

你不能防止这个 - 甚至文档不会防止错误（或者愚蠢的用户，你只需要让他们受苦一点）... :) – Nim 2012-03-14 15:38:30

你的代码看起来像C++，而不是C。通常涉及任何链接 - 它本质上是一个类似数组的结构，而不是链接结构。通常情况下，您只需简单地销毁目标对象，然后移动目标对象以填充空洞即可删除。 – 2012-03-14 15:39:51

先退后一步。您需要定义谁拥有该向量所指向的内存。它是矢量本身，还是使用矢量的代码？一旦你定义了这个，答案会很简单 - Remove（）方法应该总是将其删除，否则永远不会。

请注意，你刚刚触及了可能的错误的表面，你回答“谁拥有它”将像其他可能的问题有所帮助：

如果复制的载体，你需要复制其中的项目，或只是指针（例如，做一个浅或深的副本
当你销毁一个载体时，你应该销毁其中的项目吗？
当你插入一个项目，你应该复制该项目，还是矢量取得它的所有权？

来源

2012-03-14 19:37:12 Dave

好吧，你不能那样做，但是对代码的一些修改可以提高安全性。添加裁判

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的

来源

2012-03-14 15:44:36 innochenti

这样做会限制'Remove'函数的用处，因为你不能调用它暂时的价值 - 例如'删除（getLastNode（））;' – interjay 2012-03-14 15:52:41

@interjay为什么？ getLastNode（）不返回指针？ :) – innochenti 2012-03-14 15:54:44

它返回一个指针（例如'Node * getLastNode（）'）。但是它返回的指针是一个临时值，不能绑定到非const引用。所以'Remove（getLastNode（））'不会编译，你需要把它写成'Node * node = getLastNode（）;除去（节点）;'。 – interjay 2012-03-14 15:58:54

这类似于 “迭代器失效”。例如，如果你有一个std::list l和一个std::list::iterator it指向那个列表，并且你调用l.erase(it)，那么迭代器it就会失效 - 即，如果你以任何方式使用它，那么你会得到未定义的行为。

因此，下面的例子中，你应该在你的删除方法的文档中包含以下内容：“指针node已失效，并且在此方法返回后可能不会使用或取消引用。

（当然，你也可以只使用std ::名单，并没有刻意去重新发明轮子）

有关迭代器失效的详细信息，请参阅：http://www.angelikalanger.com/Conferences/Slides/CppInvalidIterators-DevConnections-2002.pdf

来源

2012-03-14 15:45:46

此外什么innochenti写道。我认为你必须决定的cout << currentNode->value;期望是什么/期望的行为：

错误 - （如innochenti写道node = nullptr）
默认值 - 创建节点devault_value（其中有一些默认值，其value）和delete node;后做node=default_value

来源

2012-03-14 15:52:43 dnsmkl

它会导致用户出现一些奇怪的行为。 – innochenti 2012-03-14 15:55:43

你可以添加另一个抽象级别到你的迭代器（也就是现在的原始指针）如果你不处理原始指针，而是建立某种形式的i terator类而不是指针，则可能会使迭代器失效，从而失败控制，如果有人试图在删除迭代器后访问迭代器。

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

当然，这个指针的包装会花费一些开销（检查每个deref的指针）。所以你必须决定你想玩的安全程度。无论是其他人建议的文件还是包装以确保安全。

来源

2012-03-14 15:59:07 daramarak

C++矢量实现 - 删除元素

回答

相关问题