ArrayList HashMap TreeSet HashSet LinkedList TreeMap
本次作业Xiao哥的初衷是用C++实现JAVA的STL，关于原本JAVA的STL，大家可以参见 JAVA STL
但注意JAVA和C++有很大不同，所以只能说把JAVA中函数的功能在表面上实现了。就像英语中有些意思中文无法表达，中文的有些意思英文无法表达一样。所以请不要有“我实现了JAVA的STL”这种想法。我们这里注重的是数据结构的使用，STL只是一个包装而已。
先说下非常重要的一点：因为这里的所有集合类都是模板类，所以所有方法的实现都必须在.h文件中写好，不能把实现放到.cpp文件中去。我和小胖在.h文件里面把大括号{}在每个函数后面都打好了，就是警告大家别把实现放到别的地方去。至于原因可能是这样，有兴趣的同学可以看下：
模板类的编译过程和普通类不同，是“碰到一个，生成一个“，比如发现程序中有个vector<int>，才会去对vector专门生成一个int版本的代码，而如果你只include了函数声明，没有函数的实现，而C++又是单文件编译的，那么函数实现的代码就没有被生成出来！因此，必须把声明和实现的代码都放到库文件中去。
关于迭代器也必须说下：我们这里只实现最“弱”的迭代器，就是说在一个迭代器的生命周期里，我们不允许用别的方法对集合进行操作（比如用集合类的方法把迭代器的下一个元素删除）。所以在实现迭代器的时候不用考虑外界的影响。 迭代器的操作和C++中不同，有必要说下：
我们考虑把集合类的所有元素按规定的顺序列成一个数组，然后迭代器就像一个指针从前往后扫。最开始迭代器在第一个元素之前，next操作返回第一个元素的引用，同时迭代器往后移动一格。直到迭代器的最后一格元素，这时hasNext()返回false，遍历结束。当调用remove方法时，前面必须紧跟一个next方法，这时remove方法会集合类中把前面那个next()方法返回的元素删除（如果集合类是数组或者链表，那么后面的元素会前移占掉被删除元素的位置），因此，不允许连续调用两个remove()方法。
对每个集合的遍历都能由迭代器实现，有些集合对遍历的顺序有要求，在库文件中有注释，请仔细阅读。
所有类都有拷贝构造，复制操作符，和析构函数，大家注意，因为空间是动态申请的，所以请认真地手动编写这些函数，不能依靠编译器的自动生成。
我们在模板构造函数里前加了个explicit，这样做的目的是防止出现自动类型转换（不加问题也不大）。
支持了const的集合创建，iterator分成了两个Iterator和ConstIterator，ConstIterator没有remove操作，有关“提取元素引用”的方法都重载了const和非const的版本，区别就在返回的是正常引用或者常量引用，他们会发现这两个函数的“外貌”（函数名，参数）一样，一个后面跟了const，一个没跟。当你对一个const的集合对象调用get时，就会调用那个const的版本，当你对一个正常集合对象调用get时，会调用非const的版本。
因为const的关系使得函数变得多了一些，因此删去了一些无关紧要的函数（比如那些能由别的函数简单组合得到的函数），希望注重数据结构的使用而不是STL库的功能。
注意，所有get方法返回引用，而不是一个值，这样做的目的是让操作更加简化。可以通过get()返回的引用直接调用元素的域或者方法。 对于Set来说，如果返回一个正常引用让用户能修改内容的话，就会破坏类的内部结构，因此在这里的迭代器我们只返回const引用。
我们在Utility.h中给出了两个异常，有兴趣的同学可以实现抛出异常的代码，获得加分。如果一个函数可能抛出异常，会在注释中写出。 另外在Utility.h中也给出了一些函数（比较重要的如addAll)，这些函数由小胖特别附赠，可能会对大家有帮助。
Author: Htx,zjj
本次大作业的目的是让大家能熟练地掌握本学期所学的几种数据结构：队列、Hash表、平衡树，使用它们去实现在JAVA标准库中的一些集合类Set,Map,List。在我们的压缩包中，将会给出6个库文件，分别是
还有一个比较特殊的文件是utility，这个文件中包含了一些会用到的子类（两个异常类和map的entry），还有一些可能会对大家有帮助的方法，是由一个很萌的助教提供的。在这些库文件中，我们给出了每个类的“接口”（公共方法），而大家所要做的，就是去写出这些类的私有域，并给出这些类的是实现。每个库文件都给出了非常详尽的注释，包括了每个类用什么数据结构实现，每个方法的用途和细节，参考的时间复杂度。还有要注意的是，因为模板类的关系，必须把实现和库文件放在一起。关于原本JAVA的STL，大家可以参见JAVA STL
很多人见到我就喜欢说“大作业咋写啊？坑爹啊！”这种话，显然是没经过思考说的，就像“你今天饭吃过没？”一样。如何做这个大作业，显然不是你平时走走路随便想想就知道的，但只要你静下心坐到电脑前，好好地看看那些库文件，就会发现本次大作业的思路其实是非常清晰的，本次大作业，其实就是你实现了某个数据结构，然后用一个类将其包装起来，仅此而已。如果上学期仔细学习了C++中的vector类的实现的话，一切会非常清楚。我的建议是先实现最简单的arraylist类，之后的五个类都基本是换汤不换药了，我还是希望大家不要看我下面写的东西，认真地阅读我们写的注释，结合所学的知识，这个大作业应该没啥难度。在下面，我将给出一个如何去完成一个类的一种“思考模式”，还有关于这个大作业的实现中可能会遇到的一些问题。
首先，不要马上开始动手写，一段时间的纵观全局是必须的。我们必须把这个库文件总体浏览一遍，在看的时候动脑子：我需要什么东西去实现这个接口？就拿Arraylist来说，首先我知道我肯定需要一个数组去维护所存储的数据，那么与它相关的，有这个数组的长度等等信息。然后我们发现有一个方法叫做ensureCapacity，即如果元素各种超过容量的话，这个类会自动扩容。因此立刻想到：这个数组得去动态申请，还得准备一个扩容的方法。就这样，慢慢地我的脑子里就知道了我们需要那些私有域和私有方法。
有了谱之后就可以开始实现私有域了和私有方法了，在这里我的建议是，一旦把某个接口方法需要的私有域实现了，就立刻去把这个公有方法给实现了，这样你能最快地发现你私有域实现的问题，同时一边实现私有域和公有域，会让你发现你还需要一些什么东西，或者你可能会发现一开始完全想错了，没关系，重头再来。
综上，你先要知道你需要什么东西，并马上在私有域中去实现它，在实现的过程中再去发现你还需要什么东西，慢慢地这个类就完整了。
首先大家最关心的可能就是迭代器了。首先要说明的是，C++中的内部类和JAVA中的不太一样，这个内部类并不是被“包”在它的外部对象里面的，C++的内部类和它的外部类是相互独立的，因此，当你构造一个ArrayList::Iterator的时候，要给这个迭代器对象传递一个外部类的指针（this指针），换句话说，就是让这个迭代器对象知道自己是对应于哪个arraylist对象。这点请大家注意，还有可能会有同学考虑如果两个迭代器同时作用于一个集合类会不会出问题，这里大家不用考虑这么多，我们假设这种情况不存在。
还有就是迭代器所谓的remove()方法，一句话：删掉最近一次next()方法返回的元素，也就是说，在没有用过next()方法时就remove返回异常，连续两次调用remove也返回异常。因此大家应该想到了，在一些比较复杂的集合类中，如hashset，存下上次next()返回元素所在位置的指针会省下不少事情。
关于迭代器遍历顺序的问题，每个库文件里有写了，请大家自行查阅。
大家可能会异常的知识掌握的不够，没关系，这里给出如何抛出一个异常和抓取一个异常最简单的代码： 下面的代码抛出了异常：
void add(int index, E element)
{
if (index < 0 || index > length)
{ throw IndexOutOfBound(); }
}
下面的代码有捕获异常的能力：
try
{
TreeSet<int> ss;
for (int i = 0;i < 10;i++) { ss.add(i); }
TreeSet<int>::Iterator iter = ss.iterator();
cout << iter.next() << endl;
iter.remove();
iter.remove();
}
catch(...)
{
cout << "ERROR CATCHED" << endl;
}
如何程序正常结束，则没有异常抛出，如果有异常将会输出ERROR CATCHED
所有类都有拷贝构造，复制操作符，和析构函数，大家注意，因为空间是动态申请的，所以请认真地手动编写这些函数，不能依靠编译器的自动生成。 我们在模板构造函数里前加了个explicit，这样做的目的是防止出现自动类型转换（不加问题也不大）。
答：模板类的编译过程和普通类不同，是“碰到一个，生成一个”，比如发现程序中有个vector<int>，才会去对vector专门生成一个int版本的代码，而如果你只include了函数声明，没有函数的 实现，而C++又是单文件编译的，那么函数实现的代码就没有被生成出来！因此，必须把声明和实现的代码都放到库文件中去。
答：注意JAVA和C++有很大不同，所以只能说把JAVA中函数的功能在表面上实现了。就像英语中有些意思中文无法表达，中文的有些意思英文无法表达一样。所以请不要有“我实现了JAVA的STL”这种想法。我们这里注重的是数据结构的使用，STL只是一个包装而已。
答：不要认为一个容器类和它的迭代器类是有附属关系的，要知道他们两个只是名字空间上有附属关系，别的地方时独立的，如：假如你arraylist有一个私有域叫做int len;你的arraylist::iterator里面是不能直接调用这个len变量的，这两个类是完全独立的。那么如何解决这个问题呢？只需要在arraylist::iterator里面开一个私有域arrayList *arr，在iterator()方法里，构造一个迭代器的时候把this指针赋给这个arr，然后在迭代器里，就可以通过这个arr去修改这个迭代器所对应的arraylist了。
答：很多人不知道map是何物。我就举个例子吧，map里面存的就是一个一个的键-值对，就拿我们班来举例子，我们可以搞一个学号（键）-人名（值）对Map<int,string> ACMclass，里面存的就是
1-LCC 2-msh 3-ec 4-pure
这样，然后，我们可以向这个map询问某个键对应的值是什么，或者某个值存不存在，这些方法。很多人发现treeset和treemap在实现的时候几乎一摸一样，这是对的，因为treemap<K,V>模糊点说就是treeset<Entry<K,V> ，除了一个键只能对应一个值。