Proposal（第?次作业，动态多维数组）

nine-point-eight-p commented 2 years ago

题目描述

通过模板实现一个动态多维数组类（MultiDimArray）。其初始化时创建一个空数组，方式如下：

MultiDimArray<int,3> arr_1({2,3,4}); // int型的三维数组，尺寸为2*3*4
MultiDimArray<float,1> arr_2({7}); // float型的一维数组，尺寸为7

和普通数组一样，动态多维数组使用方括号加下标的方式来访问元素，如：

MultiDimArray<int,3> arr_3({2,3,4});
int a = arr_3[0][1][2];
arr_3[0][1][2] += 1;
const MultiDimArray<int,3> arr_4({1,2,3});
int b = arr_4[0][1][2];
// arr_4[0][1][2] += 1; // 错误，不能更改const数组的元素

动态多维数组支持拷贝和移动。在这个过程中，数组的维数保持不变，但是数组的尺寸可以改变（所谓“动态”），即每个维度的“大小”可以变化。例如，一个三维数组的初始尺寸是$3 \times 3 \times 3$，虽然不能将其改成四维数组或二维数组，但是可以把它的尺寸改为$2 \times 3 \times 4$。如：

MultiDimArray<int,3> arr_5({2,3,4});
MultiDimArray<int,3> arr_6 = arr_5; // 正确，arr_6是arr_5的一个副本
// MultiDimArray<int,4> arr_7 = arr_5; // 错误，维数不同不能复制或移动
MultiDimArray<int,3> arr_8({3,3,3});
arr_8 = std::move(arr_5); // 正确，arr_8尺寸变为2*3*4

备注

知识点：模板（非类型模板参数，特化）、运算符重载、拷贝与移动
不太能确定任务的难度和工作量，不过有调整空间，可以再做增减。
也不是很能确定应该给一些什么铺垫（代码？提示？）……

hzhwcmhf commented 2 years ago

我觉得int的模板参数和特化，可以在题目开头先给个简单例子，比如说实现求阶乘，然后让同学们用这个再来做题目这个难度本身就比较高了，可以不要加const，+=之类的操作，复制和移动可以保留另外函数参数里用initializer_list好像课上也没讲？能有其他办法代替吗（比如vector?)

麻烦先按这个思路细化一下？

nine-point-eight-p commented 2 years ago

题目描述

关于阶乘的小例子

C++的模板是一个强大的存在~~（指报错很多）~~。比如，我们可以使用模板推导，在编译时进行一些计算。例如以下计算阶乘的程序：

#include <iostream>

template <int k>
struct Factorial {
    static const int value = k * Factorial<k-1>::value;
};

template <>
struct Factorial<0> {
    static const int value = 1;
};

int main()
{
    std::cout << Factorial<10>::value << std::endl; 
    return 0;
}

在一些编辑器中（比如vscode），当你把光标悬停在Factoral<10>::value上时，你会发现已经能看到计算的结果了，因为这并不是程序运行时得到的结果，而是在编译期获得的结果。

借助以上模板推导的思路，让我们来通过模板实现一个动态多维数组类（MultiDimArray）。

初始化

动态多维数组有两个最基本的属性：数据类型、维数。这两个属性通过模板参数确定。而数组具体的“尺寸”（或者说大小、容量）是可以改变的，具体来说就是数组在对应维数上的“大小”发生改变。

其初始化时创建一个空数组，方式如下：

using std::vector;
vector<int> init_1 = {2,3,4};
MultiDimArray<int,3> arr_1(init_1); // int型的三维数组，尺寸为2*3*4
vector<int> init_2 = {7};
MultiDimArray<float,1> arr_2(init_2); // float型的一维数组，尺寸为7

保证初始化时所用vector的大小和动态多维数组指定的维数一致。

拷贝和移动

动态多维数组支持拷贝和移动。在这个过程中，数组的维数保持不变，但是数组的尺寸可以改变（所谓“动态”），即每个维度的“大小”可以变化。例如，一个三维数组的初始尺寸是$3 \times 3 \times 3$，虽然不能将其改成四维数组或二维数组，但是可以把它的尺寸改为$2 \times 3 \times 4$。如：

using std::vector;
vector<int> init_3 = {2,3,4};
MultiDimArray<int,3> arr_3(init_3);
MultiDimArray<int,3> arr_4 = arr_3; // 正确，arr_4是arr_3的一个副本
// MultiDimArray<int,4> arr_5 = arr_3; // 错误，维数不同不能复制或移动
vector<int> init_6 = {3,3,3};
MultiDimArray<int,3> arr_6(init_6);
arr_6 = std::move(arr_5); // 正确，arr_6尺寸变为2*3*4

当然，你的动态多维数组可不能出现内存泄露的状况。

需要完成的任务

请编写multidimarray.hpp，在其中完成MultiDimArray类的实现。测试时给定main.cpp。

备注

知识点：模板（非类型模板参数，特化）、拷贝与移动
不知道这样会不会好一点……总之只是想让同学们尝试一下。
其实用什么东西初始化倒是无所谓，不过不管怎么样都要借助一些stl，大概第5/6次作业比较合适吧……

hzhwcmhf commented 2 years ago

题目没有问题，测试准备怎么测试？是否有部分分？

nine-point-eight-p commented 2 years ago

上次说“可以不要加const，+=之类的操作”，不过我在想是不是应该保留元素访问（也就是重载[ ]）？要不然好像也不是很好检测……

hzhwcmhf commented 2 years ago

元素访问肯定需要，这个是重点

nine-point-eight-p commented 2 years ago

题目描述

关于阶乘的小例子

C++的模板是一个强大的存在~~（指报错很多）~~。比如，我们可以使用模板推导，在编译时进行一些计算。例如以下计算阶乘的程序：

#include <iostream>

template <int k>
struct Factorial {
    static const int value = k * Factorial<k-1>::value;
};

template <>
struct Factorial<0> {
    static const int value = 1;
};

int main()
{
    std::cout << Factorial<10>::value << std::endl; 
    return 0;
}

在一些编辑器中（比如vscode），当你把光标悬停在Factorial<10>::value上时，你会发现已经能看到计算的结果了，因为这并不是程序运行时得到的结果，而是在编译期获得的结果。

借助以上模板推导的思路，让我们来通过模板实现一个动态多维数组类（MultiDimArray）。

初始化

动态多维数组有两个最基本的属性：数据类型、维数。这两个属性通过模板参数确定。而数组具体的“尺寸”（或者说大小、容量）是可以改变的，具体来说就是数组在对应维数上的“大小”发生改变。

其初始化时创建一个空数组，方式如下：

using std::vector;
vector<int> init_1 = {2,3,4};
MultiDimArray<int,3> arr_1(init_1); // int型的三维数组，尺寸为2*3*4
vector<int> init_2 = {7};
MultiDimArray<float,1> arr_2(init_2); // float型的一维数组，尺寸为7

保证初始化时所用vector的大小和动态多维数组指定的维数一致。

拷贝和移动

动态多维数组支持拷贝和移动。在这个过程中，数组的维数保持不变，但是数组的尺寸可以改变（所谓“动态”），即每个维度的“大小”可以变化。例如，一个三维数组的初始尺寸是$3 \times 3 \times 3$，虽然不能将其改成四维数组或二维数组，但是可以把它的尺寸改为$2 \times 3 \times 4$。如：

using std::vector;
vector<int> init_3 = {2,3,4};
MultiDimArray<int,3> arr_3(init_3);
MultiDimArray<int,3> arr_4 = arr_3; // 正确，arr_4是arr_3的一个副本
// MultiDimArray<int,4> arr_5 = arr_3; // 错误，维数不同不能复制或移动
vector<int> init_6 = {3,3,3};
MultiDimArray<int,3> arr_6(init_6);
arr_6 = std::move(arr_5); // 正确，arr_6尺寸变为2*3*4

当然，你的动态多维数组可不能出现内存泄露的状况。

元素的访问

和普通数组一样，使用方括号加下标进行访问，可以读写。如：

int a = arr_6[0][1][2];
arr_6[0][1][2] = 1024;

需要完成的任务

请编写multidimarray.hpp，在其中完成MultiDimArray类的实现。测试时给定main.cpp，每一个测试点只检测某一维数的数组。

输入格式

注意：每个测试点的维数$k$和数据类型TestDataType都是确定的。

第一行包括一个整数$n$，表示初始需要创建的数组个数。所有的操作均在这些数组及其之间进行。

接下来$n$行，每行包含$k$个整数$a_1,\dots,a_k$。其中$k$是已知的，即为本测试点所要检测的“维数”；$a_i$表示第$i$维的初始大小。

第$n+2$行包括一个整数$m$，表示接下来将要对元素进行的操作数。

接下来$m$行，每行为一个操作。每行第一个均是字符。其格式如下：

C+两个整数$i,j$：将第$i$个初始创建的数组拷贝到第$j$个初始创建的数组。
M+两个整数$i,j$：将第$i$个初始创建的数组移动到第$j$个初始创建的数组。
A+整数$i$+$k$个整数$a_1,\dots,a_k$+TestDataType类型数据p：将第$i$个初始创建的数组在$[a_1]\dots[a_k]$位置的元素赋值为p。
G+整数$i$+$k$个整数$a_1,\dots,a_k$：输出第$i$个初始创建的数组在$[a_1]\dots[a_k]$位置的元素。

输出格式

若有$b$个G指令（见输入格式部分），则前$b$行一行一个TestDataType类型数据。

其后，按创建顺序输出$n$个初始所创建的数组。

输出顺序为：对于任一数组，设下标为$[a_1]\dots[a_k]$，初值为$a_1=\dots=a_k=0$，按$\overline{a_1 \dots a_k}$递增顺序输出。（可参见样例）
输出格式为：若数组最后一维大小为$l$，则每输出$l$个数据换一行。

备注

知识点：模板（非类型模板参数，特化）、拷贝与移动
评测时可以使用多个测试用main.cpp么？因为这个数组的维数应该必须是constexpr。
为了检测内存泄漏，会有一个专门的类把要测试的数据类型（应该都是内置类型）封装起来，以便计数。
如果有部分分也是好的，但我不太知道怎么控制部分的“界限”并设计相应的测试手段（而且大家也都会朝着满分做……）

hzhwcmhf commented 2 years ago

可以多个main 参考https://github.com/JianGuanTHU/UOJ_Offline/tree/master/data/37/1 建议部分分就是通过main中包含的接口功能数量来控制

请将完整题面、数据（包括数据生成文件）、judger和答案程序，自行测试通过。完成之后发到邮箱 huangfei382@163.com。对于编写judger有问题可在小教员群（或找助教）讨论

JianGuanTHU / UOJ_Offline