C++
C++ 中的函数式编程
C + + 是一种 multiparadigm 的系统级的语言,它提供高级别抽象的非常低 (通常为零) 运行时成本。 通常与 c + + 相关联的范式包括程序、 面向对象和泛型编程。 因为 c + + 提供了高级编程的优秀工具,甚至函数式编程是相当合理的。
由功能风格的编程中,我不是编程是严格功能,只是它是在 c + + 的功能构建基块使用方便很多。 这篇文章将重点的最重要功能的编程构造之一:具有值而不是身份的工作。 我将讨论 c + + 一直使用的值,然后显示新的 c + + 11 标准将使用此支持的扩展的大力支持。 最后,我将介绍使用永恒不变的数据结构的维护的速度,同时提供长期享有函数式编程语言的保护而 c + + 闻名的一种方法。
值 vs。 身份
让我首先解释一下我所使用的值,而不是身份的意思。 1、 2、 3 等简单值很容易识别。 我还可以说 1、 2 和 3 是恒定的整数值。 这将是多余的然而,因为所有的值都是实际上常量,它们本身的值永远不会改变 (1,即始终是 1 和 1 将永远不会是 2)。 另一方面,与身份相关的值可能会更改 (x 可能现在,等于 1,但它可以晚些时候等于 2)。
不幸的是,它是容易混淆的值和值类型。 值类型周围的价值,而不是通过引用传递。 虽然我想在这里集中值和不使用或将它们复制中所涉及的机制,是非常有用的看看如何值类型走部分方式保存的身份与价值观念。
中的代码图 1 演示简单的值类型的使用。
图 1 使用值类型
void Foo()
{
for (int x = 0; x < 10; ++x)
{
// Call Bar, passing the value of x and not the identity
Bar(x);
}
}
void Bar(int y)
{
// Display the value of y
cout << y << " ";
// Change the value that the identity y refers to
// Note: This will not affect the value that the variable x refers to
y = y + 1;
}
// Outputs:
// 0 1 2 3 4 5 6 7 8 9
只有一个小变化,变量 y 可以成为一个引用类型 — — 的急剧变化之间的关系的 x 和 y,如中所示图 2。
图 2 使用引用类型
void Foo()
{
for (int x = 0; x < 10; ++x)
{
// Call Bar, passing the identity of x
Bar(x);
}
}
void Bar(int& y)
{
// Display the value of y
cout << y << " ";
// Change the value that the identity y refers to
// Note: This will affect the variable x
y = y + 1;
}
// Outputs:
// 0 2 4 6 8
作为图 3 所示,c + + 还提供 const 修饰符,程序员可以防止对变量进行更改,从而进一步保留值的概念。 (作为大部分的事情,在 c + +,然而,有至少一种要打败这种保护。 有关详细信息,查找 const_cast,其目的是为使用较旧的代码,并不是"const 正确。")
图 3 const 修饰符
void Foo()
{
for (int x = 0; x < 10; ++x)
{
// Call Bar, passing the identity of x,
// yet the value of x will be protected by the const
Bar(x);
}
}
void Bar(const int& y)
{
// Use the value of y
cout << y << " ";
// Attempt to change the value of what the identity y refers to
y = y + 1; // This line will not compile because y is const!
}
注意在图 3 的虽然 y 通过引用传递的 y 的值受在编译时 const 修饰符。 这给 c + + 程序员使用它们的值,而不是他们的身份同时传递大型对象的有效方法。
用 const 修饰符,c + + 有类似功能最好的编程语言中的永恒不变的数据类型。 然而,这些永恒不变的数据类型的处理是困难的。 此外,制作深 (全部) 拷贝的大型对象的每个小小的改变不是有效的。 尽管如此,它应明确标准 c + + 一直使用的值 (即使它不是一个很单纯的概念) 的一个概念。
请注意对值类型的支持延伸到用户定义的类型,通过复制构造函数和赋值运算符。 C + + 复制构造函数和赋值运算符允许用户定义的类型,以使该对象的深层副本。 请记住,在 c + + 复制构造函数时可以实施,使浅表副本,你要确保值语义将被保留。
C + + 11-函数式编程的支持
C + + 11-函数式编程带来一些新的工具。 也许最重要的是,c + + 现在已对表达式 (也称为封闭或匿名函数) 的支持。 也不允许您编写代码的方式,不会被实际之前。 此功能是通过函子,但较少的实际使用功能强大的以前可用。 (实际上,c + + 也不写匿名函子在幕后。)图 4 显示了如何使用已改善我们的代码使用一个简单的示例使用 c + + 标准库 (STL)。
图 4 使用表达式
void Foo()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for_each(begin(v), end(v), [](int i) {
cout << i << " ";
});
}
// Outputs:
// 1 2 3
在这种情况下,for_each 函数适用于每个元素的一个向量的 lambda。 这是重要的是要注意 c + + 表达式有被设计得使用的内联时可能 ; 因此也不能跑快手工代码。
虽然 c + + 是现在已经使用的众多命令式语言之一,使 c + + 也不特别的是 (类似于功能的编程语言) 他们可以保留使用值而不是身份的概念。 虽然功能的编程语言实现这一点使变量不可变的 c + + 是通过提供捕获的控制权。 请考虑使用图 5 中的代码。
通过引用捕获的图 5
void Foo()
{
int a[3] = { 11, 12, 13 };
vector<function<void(void)>> vf;
// Store lambdas to print each element of an array
int ctr;
for (ctr = 0; ctr < 3; ++ctr) {
vf.push_back([&]() {
cout << "a[" << ctr << "] = " << a[ctr] << endl;
});
}
// Run each lambda
for_each(begin(vf), end(vf), [](function<void(void)> f) {
f();
});
}
// Outputs:
// a[3] = -858993460
// a[3] = -858993460
// a[3] = -858993460
在此代码中,一切都被捕获的引用,即是在其他语言中使用的标准行为。 通过引用尚未捕获复杂化的事情,除非被捕获的变量是永恒不变。 如果你是新到使用表达式,您可能期望从代码下面的输出:
a[0] = 11
a[1] = 12
a[2] = 13
然而,这不是你得到的输出 — — 和程序甚至可能会崩溃。 这是因为变量 ctr 捕获的引用,所以所有的表达式使用的 ctr 最终值 (就是 3,所作出的值 for 循环来结束),然后访问它越界数组。
它也是值得关注的要保持活用外面的 lambda 的 ctr 变量 for 循环,ctr 变量的声明已被取消的 for 循环。 虽然某些语言消除需要提升到适当范围内的值类型的变量,这真的不能解决问题,这是 lambda 需要使用价值的点击率,而不是身份的变量的中心。 (有变通方法涉及显式复制到一个临时变量的其他语言。 不过,这使得它有点清楚,什么,这是容易产生错误,因为原始变量还捕获,因此仍可供使用。)
作为图 6 所示,c + + 提供了一种简单的语法允许的 lambda 的捕获、 保留使用值的概念,很容易控制。
图 6 c + + 语法用于控制 Lambda 捕获
[] | 不捕捉任何东西 (完全是我想要在第一次的 lambda 示例中) |
[&] | 通过参考捕获的一切 (传统 lambda 的行为,虽然不符合函数式编程值重点) |
[=] | 捕捉一切按值 (虽然这会保留值的概念,它限制使用 ; 的用处 此外,可以是昂贵复制大型对象) |
[& ctr] | 捕获只 ctr,并捕获 ctr 通过引用 |
[中心] | 捕获只 ctr,并捕获 ctr 值 |
[&,ctr] | 通过参考捕获由值和其他一切 ctr |
[=、 & v] | 按值捕获由引用和其他一切 v |
[&,ctr1,ctr2] | 通过引用捕获 ctr1 和 ctr2 的价值和其他一切 |
显然从图 6 程序员有 lambda 如何捕获的变量和值的完全控制权。 不过,尽管这会保留使用值的概念,它没有使处理复杂的数据结构作为有效的值。
永恒不变的数据类型
缺少的是一些功能的编程语言都有的高效永恒不变的数据结构。 这些语言便利是有效的即使非常大,因为它们共享公用数据的永恒不变的数据结构。 在 c + + 的共享数据中创建数据结构是微不足道 — — 您只是动态地分配数据和每个数据结构已指向数据的指针。 不幸的是,它是更难管理共享变量的生存期 (为此,垃圾回收器变得流行)。 幸运的是,c + + 11 提供了优雅的解决方案共享变量 std::shared_ptr 模板类中,通过使用中所示图 7。
图 7 共享变量
void Foo()
{
// Create a shared int
// (dynamically allocates an integer
// and provides automatic reference counting)
auto sharedInt = make_shared<int>(123);
// Share the integer with a secondShare
// (increments the reference count)
shared_ptr<int> secondShare(sharedInt);
// Release the pointer to the first integer
// (decrements the reference count)
sharedInt = nullptr;
// Verify the shared int is still alive
cout << "secondShare = " << *secondShare << endl;
// Shared int is automatically de-allocated
// as secondShare falls out of scope and the reference
// count falls to zero
}
// Outputs:
// secondShare = 123
中的代码图 7 说明了 std::shared_ptr 和其 helper 函数 std::make_shared 的简单用法。 使用 std::shared_ptr,它可以更轻松,而不必担心泄漏内存 (只要避免循环引用) 的数据结构之间共享数据。 请注意 std::shared_ptr 提供了基本的线程安全保证,运行快,因为它使用了一种无锁的设计。 但是,请记住,基本的线程安全保证,std::shared_ptr 提供了不会自动扩展到它指向的对象。 不过,std::shared_ptr 保证它不会减少它指向的对象的线程安全保障。 不可变对象本身就提供强有力的线程安全的保证,因为一旦他们正在创建它们永远不会改变。 (实际上,他们永远不会更改可观察到的方式,其中包括,除其他外,适当的线程安全保证。)因此,用不可变对象使用 std::shared_ptr 时,结合维护不可变对象的强线程安全保证。
我现在可以轻松地创建一个简单的不可变的类可能会共享的数据,如中所示图 8。
图 8 不变类的数据共享
class Immutable
{
private:
// Use a normal double, copying is cheap
double d_;
// Use a shared string, because strings can be very large
std::shared_ptr<std::string const> s_;
public:
// Default constructor
Immutable()
: d_(0.0),
s_(std::make_shared<std::string const>(""))
{}
// Constructor taking a string
Immutable(const double d, const string& s)
: d_(d),
s_(std::make_shared<std::string const>(s))
{}
// Move constructor
Immutable(Immutable&& other)
: s_()
{
using std::swap;
swap(d_, other.d_);
swap(s_, other.s_);
}
// Move assignment operator
Immutable& operator=(Immutable&& other)
{
swap(d_, other.d_);
swap(s_, other.s_);
return *this;
}
// Use default copy constructor and assignment operator
// Getter Functions
double GetD() const
{
// Return a copy because double is small (8 bytes)
return d_;
}
const std::string& GetS() const
{
// Return a const reference because string can be very large
return *s_;
}
// "Setter" Functions (always return a new object)
Immutable SetD(double d) const
{
Immutable newObject(*this);
newObject.d_ = d;
return newObject;
}
Immutable SetS(const std::string& s) const
{
Immutable newObject(*this);
newObject.s_ = std::make_shared<std::string const>(s);
return newObject;
}
};
中的代码图 8 是有点长,但大多数都是样板代码构造函数和赋值运算符。 最后两个功能是使该对象不可变的关键。 请注意,集和 SetD 方法返回一个新的对象,叶原始对象保持不变。 (同时包括集和 SetD 方法成员是方便,它有点谎言的工具,因为他们不实际改变原始对象。 一个更清洁的解决方案,请参阅在 ImmutableVector 数字 9 和 10。)图 11 显示的永恒不变的类中的行动。
图 9 使用智能 ImmutableVector 模板类
template <class ImmutableVector>
void DisplayImmutableVector(const char* name, const ImmutableVector& v)
{
using namespace std;
cout << name << ".Size() = " << v.Size()
<< ", " << name << "[] = { ";
for (size_t ctr = 0; ctr < v.Size(); ++ctr) {
cout << v[ctr] << " ";
}
cout << "}" << endl;
}
void ImmutableVectorTest1()
{
// Create an ImmutableVector with a branching size of four
ImmutableVector<int, 4> v;
// Another ImmutableVector (we will take a copy of v at element 6)
ImmutableVector<int, 4> aCopyOfV;
// Push 16 values into the vector (this will create a two level tree).
// Note that the vector is being assigned to itself.
The
// move constructor insures this is not very expensive, but
// if a copy was made at any point the copy would remain
// unchanged, but continue to share the applicable data with
// the current version.
for (int ctr = 0; ctr < 10; ++ctr) {
v = AppendValue(v, ctr);
if (ctr == 6) aCopyOfV = v;
}
// Display the contents of the vectors
DisplayImmutableVector("v", v);
DisplayImmutableVector("aCopyOfV", aCopyOfV);
}
// Outputs:
// v.Size() = 10, v[] = { 0 1 2 3 4 5 6 7 8 9 }
// aCopyOfV.Size() = 7, aCopyOfV[] = { 0 1 2 3 4 5 6 }
图 10 对 ImmutableVector 进行操作的方法
void ImmutableVectorTest2()
{
ImmutableVector<int, 4> v;
v = AppendValue(v, 1);
v = AppendValue(v, 2);
v = AppendValue(v, 3);
int oldValue = v.Back();
auto v1 = TruncateValue(v);
auto v2 = SubstituteValueAtIndex(v, 0, 3);
auto v3 = GenerateFrom(v, [](ImmutableVector<int, 4>::MutableVector& v) {
v[0] = 4;
v[1] = 5;
v[2] = 6;
v.PushBack(7);
v.PushBack(8);
});
auto v4 = GenerateFrom(v3, [](ImmutableVector<int, 4>::MutableVector& v4) {
using namespace std;
cout << "Change v4 by calling PopBack:" << endl;
cout << "x = v4.PopBack()" << endl;
int x = v4.PopBack();
cout << "x == " << x << endl;
cout << endl;
});
// Display the contents of the vectors
DisplayImmutableVector("v", v);
DisplayImmutableVector("v1", v1);
DisplayImmutableVector("v2", v2);
DisplayImmutableVector("v3", v3);
DisplayImmutableVector("v4", v4);
}
// Outputs:
// Change v4 by calling PopBack:
// x = v4.PopBack()
// x == 8
//
// Resulting ImmutableVectors:
// v.Size() = 3, v[] = { 1 2 3 }
// v1.Size() = 2, v1[] = { 1 2 }
// v2.Size() = 3, v2[] = { 3 2 1 }
// v3.Size() = 5, v3[] = { 4 5 6 7 8 }
// v4.Size() = 4, v4[] = { 4 5 6 7 }
图 11 中行动的永恒不变的类
using namespace std;
void Foo()
{
// Create an immutable object
double d1 = 1.1;
string s1 = "Hello World";
Immutable a(d1, s1);
// Create a copy of the immutable object, share the data
Immutable b(a);
// Create a new immutable object
// by changing an existing immutable object
// (Note the new object is returned)
string s2 = "Hello Other";
Immutable c = a.SetS(s2);
// Display the contents of each object
cout << "a.GetD() = " << a.GetD() << ", "
<< "a.GetS() = " << a.GetS()
<< " [address = " << &(a.GetS()) << "]" << endl;
cout << "b.GetD() = " << b.GetD() << ", "
<< "b.GetS() = " << b.GetS()
<< " [address = " << &(b.GetS()) << "]" << endl;
cout << "c.GetD() = " << c.GetD() << ", "
<< "c.GetS() = " << c.GetS()
<< " [address = " << &(c.GetS()) << "]" << endl;
}
// Outputs:
// a.GetD() = 1.1, a.GetS() = Hello World [address = 008354BC]
// b.GetD() = 1.1, b.GetS() = Hello World [address = 008354BC]
// c.GetD() = 1.1, c.GetS() = Hello Other [address = 008355B4]
请注意,对象 b 共享相同的字符串对象 (两个字符串是在相同的地址)。 添加附加字段相关联的 xyz 是微不足道的。 尽管此代码是好的很多一点难扩展到容器,当你在高效率。 例如,天真 ImmutableVector 可能会保持共享指针表示数组中的每个元素的列表。 当的天真不可变矢量发生更改时,整个阵列的共享指针将需要重复时,招致额外成本作为数组中的每个这样的元素将需要其引用计数将递增。
有一种技术,不过,这将允许共享其数据的大多数,并尽量避免重复的数据结构。 这种技术使用某种形式的一棵树,规定只有直接受更改的节点的重复。 图 12显示智能的 ImmutableVector 和 ImmutableVector 天真的比较。
图 12 比较天真和智能 ImmutableVectors
此树技术很好地扩展:随着的元素数目的增长,最小化的树,需要重复的百分比。 此外,通过调整的分支的因素 (因此,每个节点有两个以上的儿童),您可以实现平衡的内存开销和节点重复使用。
我开发了一个智能的 ImmutableVector 模板类,可以从下载 archive.msdn.microsoft.com/mag201208CPP。 图 9 演示如何使用我的 ImmutableVector 类。 (如上文所述,以使用户能够永恒不变的更清晰的 ImmutableVector 性质,ImmutableVector 使用静态成员函数生成新版本的所有行动。)
对于只读操作,像常规矢量可以多使用向量。 (注意此示例中,我还没实现迭代器,但这样做时应相当微不足道。对于写入操作,在 AppendValue 和 TruncateValue 的静态方法返回新的 ImmutableVector,从而保留原始对象。 Unfortu-怕羞,这并不是合理的数组下标运算符,所以我做了只读数组下标运算符 (即返回常量引用),并提供一个 SubstituteValueAtIndex 的静态方法。 它会不错,但是,为了能够使一大批在单独的代码块中使用数组下标运算符的修改。 为此,ImmutableVector 提供了 GenerateFrom 的静态方法,采用 lambda (或任何其他函)。 Lambda 反过来将对 MutableVector 的引用作为参数,它允许 lambda 可以自如的改变像正常的 std::vector 的临时 MutableVector 工作。 中的示例图 10 显示为运行在 ImmutableVector 上的各种方法。
美的 GenerateFrom 静态方法是可以同时将导致不可变的对象,可以安全地共享写势在必行的方式内它, 的代码。 请注意在从生成的静态方法防止未经授权的访问对底层 ImmutableVector 通过禁用传入 lambda 尽快 lambda 退出的 MutableVector。 请注意以及 ImmutableVector 的同时提供了强大的线程安全保障,其助手类 MutableVector 不 (和目的是仅适用于本地内 lambda,不传递到其他线程)。 这样,只有极少甚至重组发生在临时的树,给出很好的性能提升,我的实现还优化了更改方法内的多个更改。
结束语
这篇文章为您提供了只是在 c + + 代码中,您就可以使用-函数式编程的味道。 此外,c + + 11 功能,如使用带触摸功能式编程不管用的范式。
David Cravey 是 Visual c + + MVP 喜欢编程在 c + + 也许有点太多了。 你会发现他在 c + + 的本地用户组和大学介绍。 在白天,他喜欢在 NCR,通过在得克萨斯州沃斯堡 TEKsystems 工作。
衷心感谢以下技术专家对本文的审阅:乔瓦尼 · Dicanio,斯蒂芬 · t。 Lavavej,天使埃尔南德斯马托斯阿尔夫体育 施泰因巴赫和大卫 · 威尔金森