CS158 数据结构（荣誉）课程项目

内容概要

本学期大作业要求同学们完成三个任务：

1. vector (10 pts)
2. deque (10 pts)
3. map / B+ tree (15 pts)

实现代码的接口框架与头文件，助教已经给出，同学们需要给出补充完成，给出完整的实现。

同学们需要在每个任务的截止日期前，完成相应任务的实现，并提交到 OJ 上。助教会在截止日期后一段时间内安排 Code Review。

注意：对于每个任务，在 OJ 上通过测试数据可获得 80% 的分数，Code Review 占 20% 的分数。

关于本地测试，请点击“如何测试你的代码”。

关于在线评测，OJ 暂未搭建好，搭建好之后会告知大家提交方式。

关于迟交惩罚，请点击“迟交惩罚”

发布时间 & 截止时间

1. vector: 发布时间：第二周周四(3月12日)；截止时间：第五周周三(4月1日) 22:00
2. deque: 待定
3. map / B+ tree: 待定

请大家严格把握好时间！建议尽早开工尽早完成！

文件说明

以 vector 为例，在 vector 文件夹下分别有数据和接口文件。

• 其中 vector.hpp 是你仅需要实现的文件，也是最终提交的代码。

• exceptions.hpp 与 utility.hpp 是两个辅助文件**(不可修改)**，提供了异常处理类与 pair 类，你可以在你的代码中自由使用。

• data 文件夹中有多组测试数据，分别位于各个文件夹中。其中标有 "memcheck" 的数据是用来进行内存泄漏检查的。

任务说明

vector

补充完成一个 vector 类，你需要实现的接口有：

• 构造函数，析构函数
• 重载赋值运算
• 下标访问
• front(), back(), empty(), size(), clear()
• insert, erase
• push_back(), pop_back()
• 迭代器及其相关操作

测试数据比较宽松，请大家放心写代码。

deque

待补充

map

待补充

B+ tree

待补充

如何测试你的代码？

以 vector 为例，若要在本地测试，请将你的代码 vector.hpp、相应测试点下的 cpp 文件 code.cpp 和 class-bint.hpp, class-integer.hpp, class-matrix.hpp, utility.hpp, exceptions.hpp 放在同一个目录下编译运行。

若要检测内存泄漏，请使用 valgrind。

评测及提交方式

评测采用 OJ 在线评测的方式，请在 OJ 上用学号注册账号，在 problem 中找到相应题目，提交你的代码。

OJ 地址：暂无

迟交惩罚

如有特殊情况不能在截止时间前完成提交，请主动提前联系助教，否则按迟交处理。

在截止时间后第一天内提交，扣一分；在第二天内提交，扣两分……在第 i 天内提交，扣 i 分，扣完为止。