运行中内存不足时撤消C动态数据结构的变化
Undoing changes in C dynamic data structures when memory shortage occurs in the middle of operation
我正在用 C 实现一些支持各种操作的复杂数据结构。该数据结构使用了许多其他动态结构（图、AVL 树、链表）并且一切都在使用动态内存。
在做一些操作时，例如插入到我的数据结构中，显然我必须分配内存，有时会分配很多内存（因此结构会增长）。这会导致在执行某些操作的过程中内存不足（malloc() 返回 NULL）。现在，我不想终止我的程序，而是让操作的调用者知道操作失败并让调用者继续执行。
我的问题是，当操作在执行过程中由于内存分配失败而失败时，我想撤消自调用该操作以来所做的操作，撤消数据结构中的那些更改，就像这样操作从未被调用（因此将数据结构恢复到执行操作之前的状态）。我需要这个，因为我希望我的数据结构即使在操作失败时也处于有效且可用的状态，因此我可以继续使用它。
由于数据结构非常先进，我正在寻找有关在调用操作之前将动态数据结构恢复到其状态的通用方法、提示和技巧。也许您在处理此类问题方面有一些经验，听说过这个问题，或者可以就此问题或相关源代码提出一些 books/articles 的建议。
编辑：一个小的简化示例将从 C++ 中设置<>。根据 STL 文档，set::insert 即使在抛出异常时也能正常工作，因此它能够以某种方式恢复在执行 set::insert 期间所做的更改，即使集合的底层数据结构（可能是红黑树）是相当先进。
引自cplusplus.com：“如果要插入单个元素，则在发生异常时容器中不会发生任何变化（强保证）。
否则，保证容器以有效状态结束（基本保证）。"
处理此类情况的通常方法是，先干 运行 并分配整个操作所需的内存。并且实际上只有在所有分配都成功时才进行更新。
当然这可能 总是 是可能的，因为您可能必须调用其他没有 "dry run" 模式的操作，或者某些分配可能直到您实际上执行了该操作。对于这种情况，复制数据结构通常是最好的选择。同样，由于复制是只读操作，因此很容易中止和撤消。
用户可能希望避免重复和跟踪额外数据结构或干 运行s 的开销。所以这个特性可以做成一个可选的特性（可能使用#ifdef），用户可以选择反转操作或者终止整个程序。
在 C++ 中，一种常见的方法是以 "temporary" 的形式构造结果，然后交换临时值和结果。您还可以进行其他更改，这些更改不会在交换后失败。
您可能会查看 What is the copy-and-swap idiom? 以获取灵感 - 即使那是交换的特定用途，您可能不需要复制部分。
我正在用 C 实现一些支持各种操作的复杂数据结构。该数据结构使用了许多其他动态结构（图、AVL 树、链表）并且一切都在使用动态内存。
在做一些操作时，例如插入到我的数据结构中，显然我必须分配内存，有时会分配很多内存（因此结构会增长）。这会导致在执行某些操作的过程中内存不足（malloc() 返回 NULL）。现在，我不想终止我的程序，而是让操作的调用者知道操作失败并让调用者继续执行。
我的问题是，当操作在执行过程中由于内存分配失败而失败时，我想撤消自调用该操作以来所做的操作，撤消数据结构中的那些更改，就像这样操作从未被调用（因此将数据结构恢复到执行操作之前的状态）。我需要这个，因为我希望我的数据结构即使在操作失败时也处于有效且可用的状态，因此我可以继续使用它。
由于数据结构非常先进，我正在寻找有关在调用操作之前将动态数据结构恢复到其状态的通用方法、提示和技巧。也许您在处理此类问题方面有一些经验，听说过这个问题，或者可以就此问题或相关源代码提出一些 books/articles 的建议。
编辑：一个小的简化示例将从 C++ 中设置<>。根据 STL 文档，set::insert 即使在抛出异常时也能正常工作，因此它能够以某种方式恢复在执行 set::insert 期间所做的更改，即使集合的底层数据结构（可能是红黑树）是相当先进。
引自cplusplus.com：“如果要插入单个元素，则在发生异常时容器中不会发生任何变化（强保证）。 否则，保证容器以有效状态结束（基本保证）。"
处理此类情况的通常方法是，先干 运行 并分配整个操作所需的内存。并且实际上只有在所有分配都成功时才进行更新。
当然这可能 总是 是可能的，因为您可能必须调用其他没有 "dry run" 模式的操作，或者某些分配可能直到您实际上执行了该操作。对于这种情况，复制数据结构通常是最好的选择。同样，由于复制是只读操作，因此很容易中止和撤消。
用户可能希望避免重复和跟踪额外数据结构或干 运行s 的开销。所以这个特性可以做成一个可选的特性（可能使用#ifdef），用户可以选择反转操作或者终止整个程序。
在 C++ 中，一种常见的方法是以 "temporary" 的形式构造结果，然后交换临时值和结果。您还可以进行其他更改，这些更改不会在交换后失败。
您可能会查看 What is the copy-and-swap idiom? 以获取灵感 - 即使那是交换的特定用途，您可能不需要复制部分。