C++11中的不可变的“函数式”数据结构

Question

我正在尝试为我感兴趣的一些数据结构编写实现，以用于多线程/并发场景。

很多函数式语言，几乎所有我所知道的语言，都会以不可变的方式设计它们自己的数据结构。这意味着，如果你想将一个 value 添加到 T 的实例 t1 中，你实际上会得到一个新的 T 实例，其中包含 t1 + value。

 container t;
 container s = t; //t and s refer to the same container.
 t.add(value); //this makes a copy of t, and t is the copy

我无法找到适合在C++11中实现此操作的关键字。虽然标准库中有一些关键字、语义和函数明显面向函数式方法，但这些关键字并不能真正帮助你设计新的数据结构或以不可变方式使用数据结构，例如：

• mutable 不是用于运行时的，它更像是编译器的提示，但是这个关键字并不能真正帮助你设计新的数据结构或以不可变的方式使用数据结构
• swap 不能用于临时变量，这是我遇到的一个很大的问题

我也不知道其他关键字/函数能在这种设计上提供多少帮助，swap 是其中一个离好东西最近的关键字，所以我至少可以开始写一些代码，但显然它只限于lvalue。

因此我想问：在C++11中使用函数式方法是否可能设计出不可变的数据结构？

- user2485710

---

当然可以。是什么让你觉得不可能呢？更具体地说，有哪些方面看起来很困难或不可能呢？ - user395760

你能做的最好的事情就是始终使用const限定符声明你的数据结构的实例。问题在于，与真正的函数式语言（如Haskel）相比，你不会获得太多好处。这些语言高度利用所有值都是常量的事实，并且每个表达式仅依赖于自身（而不依赖于其他状态）。无论你的数据结构的设计如何，C++都不是这种情况。你可能想要告诉编译器只允许使用类的const实例，但这是不可能的。 - leemes

@user2485710：标准保证只要没有调用非const函数，就可以同时让多个读者访问标准容器...这实际上意味着容器在任何会改变它们的地方都必须是线程安全的，但在实践中，它们不需要具有需要显式线程安全性的mutable数据字段。 - Tony Delroy

@user2485710：我看不出有什么区别...如果该类型没有提供任何公共函数来改变它（在构造之后），那么它如何以一种让函数式编程感到沮丧的方式“不真正是不可变的”？ - Tony Delroy

开始阅读：点击这里。 - Casey

Answer 1

你只需声明一个具有私有成员变量的类，并且不提供任何更改这些私有成员值的方法。这样初始化仅限于该类的构造函数。以这种方式，没有人能够更改该类的数据。在C++中创建不可变对象的工具是成员的私有可见性。

“mutable”：这是C++中最大的hack之一。我一生中只见过两个合理使用这个关键字的地方，这个关键字基本上与你正在搜索的相反。如果你在C++中搜索能够帮助你在编译时标记数据成员的关键字，那么你正在寻找“const”关键字。如果将类成员标记为常量，则只能从构造函数的INITIALIZER LIST中初始化它们，并且您不能在实例的整个生命周期中再次修改它们。这不是C++11，而是纯C++。没有魔法语言功能可提供不可变性，您只能通过编程巧妙实现。

- pasztorpisti

---

我偶尔使用“mutable”来延迟加载一个成员。 - Mooing Duck

可变对象对于惰性求值很有用。 - user2249683

@user2485710，如果你提出一个没有代码的模糊问题，那么你会得到一个没有代码的模糊答案。如果你想要更具体的建议，你需要在你的问题中更明确一些。 - Mark Ransom

我认为你已经有了一个精确的配方来创建一个不可变类，你不需要神奇的 C++11 关键字来实现。@leemes 我能想到两个合理的对可变的例子：对于常量/不可变对象的侵入式引用计数，以及一些调试计数器/变量… 在大多数情况下，对象可能并不是真正的常量，或者它的可变/非常量部分不应该是一个不可变成员，而是另一个被引用的对象。 - pasztorpisti

除了 const。 - Mooing Duck

Answer 2

Bartoz Milewski 使用C++实现了Okasaki的函数式数据结构。他非常详细地阐述了为什么函数式数据结构对于并发很重要。在那篇文章中，他解释了在并发中需要构造一个对象，然后使其不可变的必要性：

下面是需要完成的事情：线程必须以某种方式构造将要成为不可变量的数据。根据该数据的结构，这可能是一个非常简单或非常复杂的过程。然后，该数据的状态必须被冻结-不再允许进行更改。

正如其他人所说，当你想在C++中公开数据并且使其不能被更改时，你需要将你的函数签名看起来像这样：

class MutableButExposesImmutably
{
    private:
        std::string member;
    public:
        void complicatedProcess() { member = "something else"; } // mutates
        const std::string & immutableAccessToMember() const {
            return member;
        }
};

这是一个可变的数据结构示例，但您不能直接对其进行更改。

我认为您正在寻找类似于Java中“final”关键字的东西：此关键字允许您构建对象，但此后对象保持不变。

您可以在C++中实现这一点。以下代码示例已编译。请注意，在类“Immutable”中，对象“member”实际上是不可变的（与先前示例不同）：您可以构造它，但一旦构造完成，它就是不可变的。

#include <iostream>
#include <string>
using namespace std;

class Immutable
{
    private:
        const std::string member;
    public:
        Immutable(std::string a) : member(a) {}
        const std::string & immutable_member_view() const { return member; }
};


int main() {
    Immutable foo("bar");
    // your code goes here
    return 0;
}

- djhaskin987

---

Bartoz Milewski指出，C ++不是一种适合于实现持久数据结构的语言，而这通常被认为是任何良好的函数式语言的先决条件。特别是，Bartoz Milewski表示，缺乏正确的尾调用优化或垃圾回收使得在C ++中实现Okasaki的想法（这些想法被用于Clojure和其他语言中）非常脆弱。他的观点得到了Clojure的创始人Rich Hickey的认同，后者也是C ++大师，即正确的不可变的函数结构不是C ++擅长的领域。 - johnbakers

感谢@johnbakers的输入！我正在尝试在C++中实现需要这些类型结构的东西。得到反馈可能做错了是很有价值的 :) - djhaskin987

你做错了不只是这个问题，而是在C++中通常期望的适当函数式语言方式下，你真的无法这样做。请参阅此处以获取更多见解：https://github.com/BartoszMilewski/Okasaki/issues/1 在我看来，一个人不应该试图强迫一种语言去做它不擅长的事情。以设计时的那些惯用法重新思考你的C++代码，或者使用另一种语言，充分利用C++的所有优势。 - johnbakers

Java的final关键字并不会使对象变为不可变。它只是使引用不可变，就像int * const而不是int const *。这是一个很大的区别。 - Tim Seguine

Answer 3

在中，“不可变性”是通过const关键字实现的。当然，您仍然可以更改const变量，但必须有意这样做（例如在这里）。在正常情况下，编译器不会允许您这样做。如果您最担心的是以函数式风格进行操作，并且您想要一个结构，则可以像这样自己定义它：

class Immutable{
   Immutable& operator=(const Immutable& b){} // This is private, so it can't be called from outside
   const int myHiddenValue;
public:
   operator const int(){return myHiddenValue;}
   Immutable(int valueGivenUponCreation): myHiddenValue(valueGivenUponCreation){}
};

如果您定义了一个类，即使您尝试使用const_cast更改myHiddenValue，它实际上不会做任何事情，因为值在调用operator const int期间将被复制。

请注意：没有真正的理由这样做，但是嘿-这是您的愿望。

还要注意：由于指针存在于C ++中，您仍然可以通过某种指针魔法更改该值（获取对象的地址，计算偏移量等），但您无法真正帮助。 即使在使用具有指针的函数语言时，您也无法防止这种情况发生。

顺便说一句-为什么您要试图以函数方式强制自己使用C ++？我可以理解它对您来说更简单，而且您已经习惯了它，但功能编程通常不使用，因为它的缺点。 请注意，每当创建一个新对象时，您必须分配空间。 这会使最终用户感到缓慢。

- Paweł Stawarz

---

因为不可变数据结构在并发时真的非常有帮助，而且最大的优点是一切都是通过设计实现的，所以你比仅仅使用一堆互斥锁或锁定或尝试做花哨的事情更适合。 - user2485710

如果你一开始就不想改变它们，那有什么区别呢？你问题的答案是：只需编写一个接受类型为X参数并返回类型为X的函数即可。 - Paweł Stawarz

真正的不可变数据结构并不是用来限制你对数据进行更改的，假设t是T的实例，你可以随意更改t，魔法在于T的设计。从这个链接中的第一行开始：http://bartoszmilewski.com/2013/11/13/functional-data-structures-in-c-lists/ - user2485710

@user2485710 你错了。魔力在于你对 T 调用的函数，而不是 T 本身。函数式语言中没有什么神奇的东西。你只需要有类型为 const T f(const T t) 的函数，它们接受“旧”的 t 并返回一个“新”的、已更改的 t，而不会影响第一个。这就是我学习 SML 时所学到的。 - Paweł Stawarz

@user2485710 或许我只是学了错误的函数式语言（主要是Scheme/CLOS），但至少在我看过的每一种函数式语言中，如果你真的想要，你仍然可以改变状态。这意味着，如果你不注意操作，你也可以在函数式语言中编写可变数据结构。无论如何，在C++中，不可变数据结构也非常有用，因为并发已经足够困难了，没有到处都是可变数据结构。 - Voo

Answer 4

关于你的带有s和t的代码示例，你可以在C++中实现，但是“不可变性”与该问题无关，如果我正确理解了你的要求！

我使用过供应商库中操作方式与你描述相同的容器；即当它们被复制时，它们共享其内部数据，并且直到需要更改其中一个时才会复制内部数据。

请注意，在你的代码示例中，有一个要求，即如果s发生更改，则t不能更改。因此，s必须包含某种标志或引用计数，以指示t当前正在共享其数据，因此当s更改其数据时，它需要拆分副本而不仅仅是更新其数据。

因此，作为你的容器非常广泛的概述：它将由一个句柄（例如指针）指向一些数据，加上一个引用计数；并且你的更新数据的函数都需要检查引用计数来决定是否重新分配数据；你的复制构造函数和复制赋值运算符需要增加引用计数。

- M.M

---

幸运的是，复杂的部分已经完成了！std::shared_ptr - Mooing Duck