在C++中实现不可变数据结构的提示搜索

Question

我想知道如何在C++（或C）中实现不可变数据结构。我正在寻找有关此主题的书籍、论文或相对简单且有文档记录的实现，但目前还没有找到，所以我决定寻求提示。 感谢您提前的回答。

- fokenrute

---

也许您正在寻找持久数据结构（http://en.wikipedia.org/wiki/Persistent_data_structure）？如果是这样，您还可以查看一下.NET中的不可变集合以获取其他提示（http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx）。 - Sergey Teplyakov

我不知道你是否还在寻找答案，但是看看Rich Hickey如何使用Java在Clojure中实现不可变数据结构是一个好主意。 - Dzung Nguyen

Answer 1

我认为你可以从其他语言中获取一些想法。例如，在Java和C#中，不可变性是通过以下方式实现的。我们不创建“mutators”（更改对象状态的函数），而是创建返回新的“changed”实例的函数：

class Foo
{
public:
  Foo(int i)
   : i_(i)
   {}

   int GetI() const {return i_;}
   Foo SetI(int i) const {return Foo(i);}
private:
   const int i_;
};

- Sergey Teplyakov

---

这正是我所说的“不可变”的意思，但我正在寻找关于如何高效实现不可变集合（例如Clojure集合）的提示，尤其是如何共享结构的一部分以避免不必要的复制。 - fokenrute

@fokenrute 我认为这才是真正的问题，即共享不可变结构的部分。在垃圾收集语言中，这非常简单明了。 - Ghita

Answer 2

您可以像这样将对象声明为const：

const std::string x("我的常量字符串");

这是使用const关键字使对象不可变的常见方式。

如果您知道有一个对象，您不希望允许对其进行任何更改，并且这应该是该对象的每个实例行为的一部分，则可以创建具有所有const成员的对象。

class Immutable
{
   public:
   Immutable() :z(10), y(20) 
   {

   }

   Immutable(int zVal, int yVal) : z(zVal), y(yVal) 
   {

   }

   int getZ() const;
   int getY() const;

   private:
   const int z;
   const int y;
};

请注意，您必须在初始化列表中设置const成员的值。（无论如何，最好都遵循最佳实践使用初始化列表）

- RC.

Answer 3

提示：声明一个结构体如下所示：struct。

struct Immutable
{
private:
    Immutable& operator =(const Immutable& other);
};

这将锁定赋值运算符。现在确保结构体没有public或mutable成员变量，并且所有公共方法都是const：

public:
    int get_quux() const;
    void foo(int bar) const;

你拥有的是一个非常接近不可变类型的东西。当然，C++中缺乏sealed/final关键字意味着某人仍然可以从你的类型派生出一个不太不可变的类型。

- Frédéric Hamidi

---

Immutable并不意味着不可复制。您无需担心对象被复制。 - RC.

你说得完全正确，我们只需要关注被分配的对象。回答已相应更新。感谢您的提醒。 - Frédéric Hamidi

Answer 4

我在Github上发现了一个名为gorgone的项目，其中包含了基于Rich Hickey在Clojure中的Java实现的PersistentVector的C++实现以及基于Phil Bagwell最近的工作的RRBVector。

该项目的维护者已不再继续维护，但我会接手。请查看我的分支：https://github.com/sandover/gorgone。

- sandover

Answer 5

我非常推荐这篇文章Immutable C++ stack - thoughts and performance，其中的代码审查和答案真的很棒！

此外，如果想要在C++中开始使用持久化数据结构或函数式数据结构，可以阅读这篇文章Functional Data Structures in C++: Lists。

- Lihang Li

Answer 6

const 是你的好朋友 - 所有数据成员都是 const 的对象很难被改变。

- Steve Townsend

Answer 7

看一下Phoenix Framework.

Phoenix将FP的概念进一步扩展到C++。简而言之，该框架开启了FP技术，如Lambda（未命名函数）和Currying（部分函数求值）。

因此，它超越了简单的不可变结构，但我假设这是您要走的方向。

- Robert Harvey

---

它是否也允许结构共享？ - CMCDragonkai

Answer 8

这取决于你所说的“不可变数据结构”的含义。

如果你指的是一种类型，其中该类型的变量不能被分配或修改，那么请参见其他答案（删除赋值运算符的访问权限，使用const，或仅具有引用或const数据成员）。

如果你指的是一种类型，其中该类型的值不能被修改，例如像Java、C#或Python字符串一样，但该类型的变量仍然可以被分配，那么就更加棘手了。你最好的帮助可能是使用boost::intrusive_ptr来管理内部可变状态。之所以选择intrusive_ptr而不是例如shared_ptr，是因为intrusive_ptr允许更多的优化，其中一个对于例如“不可变字符串”非常关键，即从文字构造这样的东西时根本没有动态分配。

我不知道在C++中有任何通用框架来实现后者的“不可变数据结构”。

所以，看起来你提出了一个很好的想法！ :-)

- Cheers and hth. - Alf