本文主要是介绍C语言下的容器及泛型编程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 引言
众所周知，C++语言提供了大名鼎鼎的标准模板库（STL）作为C++语言下的编程利器受到无数青睐，而C语言下并没有提供类似的工具，使得C语言的开发变得尤为困难和专业化。Nesty框架的NCollection容器为C语言提供了一整套标准的、丰富的模板工具，用以弥补C语言在结构化编程上的弱势。之前发表的一篇文章是关于如何在C语言下进行面向对象编程的，主要介绍了NOOC的诸多特性。然而，NOOC真正的作用是为NCollection建立基础。本文还是以一些简单的代码作为例子，介绍NCollection的使用方法，通过阅读本节的内容，你将了解为什么NCollection可以大大地加快C语言下开发的效率。
2 迭代模型
作者所指的迭代模型，是指对谋一同类数据进行遍历时所使用的方法，从设计模式的角度来看，迭代模式甚至包含了访问者模式。以Nesty的开发为例，NCollection整套框架的设计都是围绕其迭代模型展开的，因为迭代模型涉及到是否能为所有容器提供一套统一的访问标准。在Nesty的容器框架下，迭代模型通常包含了两种基本形式：（1）基于索引的；（2）基于位置（Position）的。基于索引的迭代模式比较常用和易于理解，我们通常利用索引来遍历数组；基于位置的迭代模式会更加抽象一些，其工作方式类似于数组索引，在Nesty中通过定义一个Position数据结构来维持元素在各自容器中的某个“位置”。 为了方便对比，下例例举STL容器中的迭代器，以及Nesty容器定义的索引迭代模式及Position迭代模式的代码：
示例（1），索引迭代模式：
// incase MyList is a valid NList<NINT> instance
for (NINT Idx = 0; Idx < MyList.Len(); Idx++) {// extract the elementNINT Val = MyList.GetIdx(Idx); // or MyList[Idx]
}示例（2），Position迭代模式：
for (NPosition Pos = MyList.FirstPos(); Pos; Pos = MyList.Next(Pos)) {// extract the elementNINT Val = MyList.GetPos(Pos); // or MyList(Pos)
}示例（3），STL迭代器模式：
// incase my_list is a valid std::list instance
for (std::list<int>::iterator it = my_list.begin(); it != my_list.end(); it++) {// extract the elementint value = *it;
}通过观察上例，你会发觉Nesty容器所提供的Position迭代模式更加简洁，而相比之下STL容器迭代器是一个子包含的对象，每次使用都需要从list类型中解压，其语法是std::list<int>::iterator，而Position迭代模式通过调用容器的通用接口FirstPos返回一个位置信息，并不断通过Next及Prev来移动位置，并通过GetPos来从相应位置获取数据。因此，Position仅代表一个抽象的位置，好比索引（Index）代表的是一个具有具体偏移值的位置一样。
注意：为了方便阐述，上述代码使用了Nesty容器中的C++版本，C语言版本在编码结构上与其一致，但代码略有不同。
3 NCollection容器框架
NCollection是在NOOC的基础上开发的以面向对象为基础的一套容器库， 提供约20种容器工具，其类型覆盖所有通用数据结构，包括向量（NVector），列表（NList），集合（NSet），关联表（NMap）等，以下是NCollection框架的全景UML图，其中虚线框代表的是抽象类，实线框代表的是实现类：
在上图的整个框架中，有五个最为重要的容器接口：
NCollection
NCollection是框架中最顶层的基类，所有容器都派生自NCollection。对于外部而言，NCollection中所定义的操作是只读的，即只提供一个Push操作来单个插入元素；由于所有容器都有清空所有元素的操作，NCollection也提供了Empty操作用于批量删除元素。
NSeque
单词Seque是Sequence的缩写，代表序列。序列能很好地模拟先进先出（FIFO）及先进后出（FILO）等行为的数据结构。NSeque派生自接口NCollection并提供了一个Pop操作用于一次从容器中弹出一个元素，Pop操作会根据Seque的类型表现出不同的行为。例如，NSeque接口指向的是一个NQueue，则Pop表现为从队列最前端弹出元素，如果NSeque指向的是一个NStack，则Pop表现为从栈最顶端弹出元素，以此类推。NSeque的实现类有NVector，NPriorQueue，NQueue，NStack。
NList
NList是所有列表数据结构的抽象基类。列表具有队列或栈的属性，因此是从NSeque派生而来，但除此之外，列表通常还能以高效的速度（通常表现为常数级操作）从前/后、中间插入/删除元素。列表是最为常用的数据结构，尽管有时候向量（NVector）同样可以充当列表，但列表专门针对从内部插入/删除元素作了优化。对于NSeque的接口行为，NList及其所有实现类都表现为队列（FIFO）的属性。NList的实现类有NArrayList，NDeList（双端列表），NLinkedList，NStackList（栈表，行为和链表相同，但对内存碎片进行了优化）。
NSet
NSet代表的是集合。如果仅从元素存储来看，集合非常类似于列表，都是用于存储单个元素，而集合却对元素有快速查找的能力。List的查找总是基于遍历的，其时间复杂度为O(N)，而集合根据规则的不同，能够提供比列表优越得多的查找速度，例如对于哈希而言，其平均查找的效率通常为常数，而对于红黑树而言，其平均查找时间通常为O(N Log N)。当然，集合在查找速度上的优化是要付出代价的，例如其遍历、插入/删除速度不及列表，而且也无法维持列表元素的先后顺序。NSet的实现类有NHashSet，NTreeSet，NArraySet，NLinkedSet，NStackSet。
NMap
关联表（Map）是以键（Key）和值（Value）构成的二元关系集合。如同NSet一样，NMap对键拥有快速查找的能力。为了保证容器在组成上的统一，NMap继承了NCollection的接口，其接口表现为只对Key进行的操作。NMap的实现类包括：NHashMap，NTreeMap，NArrayMap，NLinkedMap，NStackMap。
4 在C语言中使用Nesty容器
C语言是一门面向过程的编程语言，然而，通过对设计方法的规范化，依然可以在C语言使用C++中类似封装，基于对象，甚至面向对象（NOOC）等的编程技术。对象包括了数据及方法的概念，因此在Nesty C的所有类型也按照类似的规则来定义。以NVector为例，NVector的数据是全大写的对象NVECTOR，而NVector的操作是一组以NVector单词开头的函数的集合，如NVectorNew，NVectorAdd，NVectorDel等，以下代码片段演示如何在C语言下进行容器编程：
// 创建NINT类型的容器对象
NVECTOR Vec = NVectorNew(NINT);
// 插入元素
NINT InsertValue = 3;
NVectorAdd(Vec, InsertValue);
// 删除元素
NINT DeleteValue = 3;
NVectorDel(Vec, DeleteValue);
// 遍历元素
NPOSITION Pos = NVectorFirstPos(Vec);
for (; Pos; Pos = NVectorNext(Vec, Pos)) {NINT Val = NVectorGetPos(Vec, Pos, NINT);
}
// 不过对于向量，可以直接使用索引迭代模式
NINT Idx = 0;
for (; Idx < Vec->Len; Idx++) {NINT Val = NvectorGetIdx(Vec, Pos, NINT);
}5 C语言与泛型编程
泛型是从C++模板引入的概念，然而C语言下实现泛型可以利用无类型指针（void *）。而类型数据从二进制的角度来探讨，不外只是一块有指定大小的内存块；由于任何类型的指针的都可以隐式转换为一个void *的地址，因此利用一个数据大小值，以及一个指向该数据头部的无类型地址（void *）即可以表达任何类型的泛型。
但是定义一个类型光知道类型的大小是不行的，类型必须具有其独特的行为，从类型数据的生存期来看，类型应该具备以下三个最为基本的行为（操作）：创建（Create），拷贝（Copy），销毁（Destroy）。以动态字符串为例，字符串的大小代表该字符串占用了多少个字符字节。在字符串创建时，需要将其初始化为指向一个有效字符串的地址，当需要拷贝字符串时，需要将字符串数据进行逐字符拷贝，当字符串不再被使用时，应该释放其占用的内存，并将字符串指针初始化为0。
因此，在Nesty的框架中，类型的大小，创建，拷贝，销毁这4个属性构成了该类型的特征签名，这一概念和C++类的构造函数，复制拷贝操作符，析构函数等是对应的。
6 泛型与Type Class
根据上一节的介绍，Nesty引入了Type Class的概念来支持C语言的泛型操作，在程序代码中由NTYPE_CLASS数据结构给出相关定义，Type Class指定了某类型相关的特性及操作，以下便是NTYPE_CLASS的定义：
typedef struct tagNTYPE_CLASS
{// type identifierNINT TypeSize;NPfnCreate FnCreate;NPfnCopy FnCopy;NPfnDestroy FnDestroy;// type functionsNPfnMatch FnMatch;NPfnCompare FnCompare;NPfnHash FnHash;NPfnPrint FnPrint;// template functionsNPfnSwap FnSwap;
} NTYPE_CLASS;
typedef tagMYDATA MYDATA;
struct tagMYDATA {NINT Value;
};// define Create behavior
void CreateMyData(NVOID * InThis, const NVOID * InOther) {MYDATA * This = (MYDATA *)InThis;MYDATA * Other = (MYDATA *)Other;if (Other) {This->Value = Other->Value;}else {This->Value = 0;}
}// define Copy behavior
void CopyMyData(NVOID * InThis, const NVOID * InOther) {MYDATA * This = (MYDATA *)InThis;MYDATA * Other = (MYDATA *)Other;NASSERT(Other); // source MUST not NULL!!!This->Value = Other->Value;
}// define Destroy behavior
void DestroyMyData(NVOID * InThis) {MYDATA * This = (MYDATA *)InThis;This->Value = 0;
}
为了方便阐述，以下先给出了NPfnCreate，NPfnCopy，及NPfnDestroy接口的定义：
typedef (*NPfnCreate)(NVOID * InThis, const NVOID * InOther);
typedef (*NPfnCopy)(NVOID * InThis, const NVOID * InOther);
typedef (*NPfnDestroy)(NVOID * InThis);MYDATA MyData, OtherData;
// create MYDATA by default construct
CreateMyData(&MyData, NULL);
// after create, MyData.Value will have the default value of 0
NASSERT(MyData.Value == 0);
// create MYDATA by copy construct, incase OtherData.Value == 3
CreateMyData(&MyData, &OtherData);
// after create, MyData.Value will have the initialized value of 3
NASSERT(MyData.Value == 3);// copy MYDATA, incase OtherData.Value == 5
CopyMyData(&MyData, &OtherData);
// after copy, MyData.Value will have the updated value of 5
NASSERT(MyData.Value == 5);// destruct MYDATA
DestroyMyData(&MyData);
// after destroy, MyData.Value will have the cleanup value of 0
NASSERT(MyData.Value == 0);typedef (*NPfnCompare)(const NVOID * InThis, const NVOID * InOther);
typedef (*NPfnMatch)(const NVOID * InThis, const NVOID * InOther);
typedef (这篇关于C语言下的容器及泛型编程的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
