Assignment 1

0. 写在最前

花的时间和收获是正相关的。

我把设计分成了几个feature。

所有的要求都是Optional，请同学根据自己的时间，酌情完成。没有计分。

1. Outline

完成List的一个具体实现ArrayList，(对比于LinkedList）支持Random Access。功能上与STL的vector相似。

基本要求:

自增长和收缩 i.e. 在元素比较多的时候，填充率>20% （3 hours)

进阶要求:

• 实现迭代器 (3 hours)
• 如果我们的迭代器只做View，不操作数据，我们希望当容器发生变化时，迭代器失效. (1 hour)
• (Optional) STL 的容器，使得我们感知不到指针的存在，如果1，2实现后，ArrayList类让外部感知到指针的存在. 改进你的实现。(x hour(s))

2. 准备知识

• 继承和多态
• 指针，引用
• 迭代器 设计模式

3. 详细描述:

完成List的一个具体实现ArrayList，（对比于LinkedList）支持 Random Access. 功能上与STL的vector相似。

性能要求

1. size(), isEmpty(), get(),常数时间。
2. add()均摊常数。
3. remove()线性。

template <typename T>
class List {
    public :
        virtual int size() const = 0;
        virtual bool isEmpty() const = 0;
        virtual T get(int index) const = 0;
        virtual void add(T element) = 0;
        virtual T remove(int index) = 0;

};

基本要求: 自增长和收缩 i.e. 在元素比较多的时候，填充率>20%。

举个例子： 当调用10^6次add()再调用10^6次remove()你的实现不能占用10^6数量级的空间。

template <typename T>
class Iterator {
    public :
        /**
        * Return true if the iteration has more elements
        */
        virtual bool hasNext() = 0;
        /**
        *  Returns the next element in the iteration
        */
        virtual T next() = 0;
};

template <typename T>
class Iterable{
    public :
        virtual Iterator<T>* iterator() = 0;
};

template <typename T>
class List : public Iterable<T> {
    public :
        virtual int size() const = 0;
        virtual bool isEmpty() const = 0;
        virtual T get(int index) const = 0;
        virtual void add(T element) = 0;
        virtual T remove(int index) = 0;


};

进阶要求:

• 实现迭代器, 使得实现类可通过该测试

这里List继承了Iterable， 实现这个接口，使得我们可以通过下面code的方式遍历你实现的容器。

void iterate_through_list(List<int>& list) {
    cout << "iterate_through_list start" << endl;

    for (int i = 0; i < 10; ++i) {
        list.add(i);
    }

    Iterator<int>* iter = list.iterator();
    
    int cnt = 0;
    while (iter->hasNext()) {
        assert(list.get(cnt++) == iter->next());
    }

    delete iter;
    cout << "iterate_through_list end" << endl;
}

• 如果我们的迭代器只做View，不操作数据，我们希望当容器发生变化时，迭代器失效. 所谓只做View的意思是Iterator的操作都是不改变数据状态的。 请看下面代码:

    vector<int> vec;
   
    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
    }

    for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
        cout << *iter << endl;
        vec.push_back(11);
    }

该代码最终会导致死循环。

本次作业希望当宿主发生变化时，不允许再通过该迭代器对进行遍历.迭代的同时，容器发生了变化，迭代器抛出logic_error。

i.e.

void iterator_fast_fail_feature(List<int>& list) {
    cout << "iterator_fast_fail_feature start" << endl;

    list.add(1);
    Iterator<int>* iter = list.iterator();
    try {    
        while (iter->hasNext()) {
            iter->next();
            list.add(2);
        }
    } catch (logic_error e) {
        cout << e.what() << endl;
    }

    delete iter;

    cout << "iterator_fast_fail_feature end" << endl;
}

使得该测试正常终止。

• (Optional) STL 的容器，使得我们感知不到指针的存在，如果1，2实现后，你的ArrayList类让外部感知到指针的存在，也就是需要显式释放iter。具体地说见下例子：

void iterate_through_list(List<int>& list) {
    cout << "iterate_through_list start" << endl;

    for (int i = 0; i < 10; ++i) {
        list.add(i);
    }

    Iterator<int>* iter = list.iterator();
    
    int cnt = 0;
    while (iter->hasNext()) {
        assert(list.get(cnt++) == iter->next());
    }

    delete iter;   // focus this line
    cout << "iterate_through_list end" << endl;

}

我们仍旧要显式delete iter。 回想STL的容器，它让我们对指针的存在没有感知。根据这个要求，完善你的实现类。可修改头文件。

建议步骤

基本要求:

1. 从TA/assignment1/ArrayListBase-only-header处把头文件等拷贝到你的目录(拷贝整个文件夹)。
2. 完成ArrayList.cpp
3. 通过ArrayListTest.cpp的测试，已经写了Makefile， type make 即可。
4. 完善ArrayListTest

进阶要求(基本同上):

1. 从TA/assignment1/ArrayListWithIterator-only-header 拷贝文件夹到你的工作目录。
2. 完成ArrayList.cpp(把已经完成的内容复制过来) 余同上。

Tips:

1. 对于还不适应的同学，可再TA目录下找到对应的 *-with-skeleton. 这里已经搭好基本的骨架，只需填充几个public 的接口。
2. 强烈建议同学们不要在看到Assignment的2个小时内，查看该目录

资源:

1. http://www.cplusplus.com/reference/