我看到有人在讨论在 C 语言中实现垃圾回收,但是有些人认为由于 C 是弱类型语言,这是不可能的。我想知道如何在 C++ 中实现垃圾回收。
我想要一些关于如何实现垃圾回收的通用思路。非常感谢!
这是我朋友告诉我的一个 Bloomberg 面试题。他那时表现很差。我们想知道您对此的想法。
我看到有人在讨论在 C 语言中实现垃圾回收,但是有些人认为由于 C 是弱类型语言,这是不可能的。我想知道如何在 C++ 中实现垃圾回收。
我想要一些关于如何实现垃圾回收的通用思路。非常感谢!
这是我朋友告诉我的一个 Bloomberg 面试题。他那时表现很差。我们想知道您对此的想法。
对于C和C ++中的垃圾回收,存在以下几个困难点:
指针可以强制转换为整数,反之亦然。这意味着我可能有一块只能通过将整数强制转换为指针,然后取消引用它来访问的内存块。 垃圾回收器必须小心,以免认为一个块是不可达的,而实际上它仍然可以被访问。
指针不是不透明的。 许多垃圾收集器(如停止并复制收集器)喜欢移动内存块或紧缩它们以节省空间。 由于您可以显式地查看C和C ++中的指针值,因此正确实现可能会很困难。 如果有人正在使用类型转换进行某些棘手的操作,并且您移动了内存块,则必须确保正确更新整数。
内存管理可以明确进行。 任何垃圾收集器都需要考虑用户可以随时显式释放内存块。
在C++中,分配/释放和对象构建/销毁是分开的。 可以分配一块足够容纳对象的内存块,而不必实际在其中构建任何对象。 一个好的垃圾收集器需要知道,在回收内存时,是否调用可能分配在其中的任何对象的析构函数。 对于标准库容器尤其如此,它们经常使用std :: allocator
以出于效率原因利用这种技巧。
内存可以从不同区域分配。 C和C ++可以从内置自由存储(malloc / free或new / delete)或通过mmap
或其他系统调用从操作系统中获得内存,并且在C ++中,可以使用get_temporary_buffer
或return_temporary_buffer
从中获取内存。 程序还可能从某些第三方库获取内存。 一个好的垃圾回收器需要能够跟踪这些其他池中内存的引用,并且(可能)要负责清理它们。
指针可以指向对象或数组的中间位置。在许多像Java这样的垃圾回收语言中,对象引用总是指向对象的起始位置。而在C和C++中,指针可以指向数组的中间位置,而在C++中,如果使用了多重继承,则可以指向对象的中间位置。这会极大地复杂化检测什么东西仍然是可达的逻辑。
简而言之,为C或C++构建垃圾回收器非常困难。大多数在C和C++中进行垃圾回收的库都采取了非常保守的方法,并且从技术上讲是不可行的-它们假设您不会将指针转换为整数,将其写入磁盘,然后在以后的某个时间点将其加载回来。他们还假设内存中任何大小为指针的值都可能是指针,因此有时会拒绝释放不可达的内存,因为有一定的机会存在指向它的指针。
正如其他人所指出的,Boehm GC确实对C和C++进行垃圾回收,但受到上述限制。
有趣的是,C++11包括一些新的库函数,允许程序员标记内存区域作为可到达和不可到达,以期望未来的垃圾回收工作。使用这种信息可能有可能在将来构建一个真正优秀的C++11垃圾回收器。但与此同时,您需要非常小心,不要违反上述规则。
intptr_t x = rand(); intptr_t y = ((intptr_t)p)^x; /* 丢弃p,然后过一段时间 */; use_the_ptr((char*)(x^y));
。你需要用户的一些合作。 - Steve Jessopchar* pCharArray = new char[128];
// do some stuff with characters
delete [] pCharArray;
std::vector<char> charArray;
// do some stuff with characters
从实际编码角度来看,彭博社的面试问题常常与实际情况不符。像大多数面试官一样,他们主要关注您的思维方式和沟通能力,而不是真正的解决方案。
boost::scoped_array
通过不可复制来实现更安全,但由于同样的原因,它无法在STL容器中使用。基于性能考虑,这将是我使用 std::vector
的 Boost 替代方案。 - AJG85你可以阅读关于shared_ptr结构体的内容。
它实现了一个简单的引用计数垃圾回收器。
如果你想要一个真正的垃圾回收器,你可以重载new运算符。
创建一个类似于shared_ptr的结构体,称之为Object。
这将包装新创建的对象。现在通过重载其运算符,你可以控制GC。
现在你只需要实现其中的一种GC算法即可。