一组相当于某些 C++ STL 类的 Swift 标准库类

• 下载源代码 - 56.4 KB

引言

Swift已广泛用于iOS/MAC OSX软件开发，但与C++相比，Swift标准库仍缺少一些通用算法实现，如C++ STL。

背景

我开发了一套Swift泛型队列（FIFO）和栈（FILO）类，以匹配C++ STL队列和栈类的功能。

项目详情

该项目实现了一套Swift泛型类

• CSingleLinkedListNode：单链表节点类
• CSingleLinkedList：单链表
• CStack：栈（FILO）类
• CQueue：队列（FIFO）类

为达到更好的性能和内存使用效果，这些Swift队列和栈类是通过一组Swift泛型单链表节点和单链表类实现的。

单链表类CSingleLinkedList是实现队列（FIFO）和栈（FILO）类的基础类。它是单链表节点类CSingleLinkedListNode的包装类，包含数据、下一个节点的引用和一个用于循环查找算法实现的哈希值。

为避免CSingleLinkedList类中的循环，使用查找表实现了循环查找算法，该查找表存储了CSingleLinkedListNode对象的键和对象实例。为确保查找表中每个CSingleLinkedListNode对象实例的键值唯一，设计并生成了内置整数类型哈希值属性，通过对两个随机整数变量进行指数运算得到。

通过检查查找表中是否存在重复节点对象的键值来实现循环查找算法，如果在查找表中未找到重复的键值，则链表没有循环。

关注点

对于Swift编程中的C++开发者，有一些有趣的注意事项：

1. Optional，Unwrapped Optional

在C++编码世界中，指针变量赋值为null或检查null值条件非常普遍。在Swift编码中，遇到这种情况，变量必须声明为Optional以允许null值赋值，并在后续代码实现中应用Optional解包。

var tempValue : T ?  // “?” as declaration of Optional
tempValue = nil      // If not declared as Optional, compilation error here

2. Generics

Swift Generics提供了与C++模板类似的功能，因此Swift Generics使得将C++模板基础代码移植到Swift成为可能且更加容易。本文中的所有类都通过Generics实现。

3. Swift Multiple Values Function Return: Tuples

Swift编程的一个强大功能是Swift Tuples，它允许函数返回多个值。在CSingleLikedListNode类中，循环查找函数iscycled()返回三个值：一个布尔值，指示链表是否循环，以及构成链表循环的两个节点对象。

4. For Loop

Swift的for循环不如C/C++的for循环灵活或强大。Swift的for循环条件是常量、静态的，不支持C/C++那样的动态条件。对于C/C++，for循环代码如下：

    for (int i = 0; i <= (10-i); ++i)
    {
        std::cout << i << std::endl;
    }

上述C/C++代码不能直接移植到Swift的for循环，因为i < (10-i)是动态边界。其输出为0 1 2 3 4 5。

Swift的for循环代码如下：

    var i : Int = 0
    for i in 0 ...(10 - i) {
        print (i)
    }

此Swift代码段与C++代码不同，其条件边界是静态的，由(10-i)初始化为10，当i初始值为0时。其输出为0 1 2 3 4 5 6 7 8 9 10。移植到Swift的解决方案是在for循环中使用where 条件，如

    for i in 0...10 where i < (10-i) {
        print(i)
    }

或者使用 while循环，如

    var i : Int = 0
    while i <= (10-i) {
        print(i)
        i += 1
    }

对于带有递减步长的Swiftfor循环，使用泛型函数“stride”是最佳解决方案。对于C++代码：

    for (int i = 10; 0 <= i; --i)
    {
        std::cout << i << std::endl;
    }

等效的Swift代码是：

    for i in (0...10).reversed() {
        print (i)
    }

或

    for i in stride(from:10, to:0, by:-1) {
        print (i)
    }

如何运行代码

该项目是在MAC OSX上的XCode中开发的，类的测试用例是在XCode playground中开发的。GitHub上的代码库是GitHub的https://github.com/zhaohuixing/Swift-Algorithm-Library。