任务:
在此任务中,您必须编写一个既像 C 中的常规数组又像 Python 中的列表一样工作的结构。即写一个结构
template<typename T> struct FlexArray;
那些。这是一个模板结构。它是一个固定长度的
类型元素数组,长度在构造函数中传递。默认情况下,您应该假设长度为 0。(这并不要求您在实现时仅使用经典数组)T
通过
方法访问元素 - 返回数组的索引元素。为非常量和常量结构正确编写此方法。也就是说,在常量结构上调用at(unsigned int index)
不应允许更改数组的内容,而且不能出现在at(i)
符号的左侧=
Size()方法,返回数组的当前大小。
现在到了有趣的部分。
将两个
和operator+
写成FlexArrays
,其中operator+=
的相加被认为是它们元素的串联。那些。FlexArray
。{1, 3, 5} + {2, 4} = {1, 3, 5, 2, 4}
仅当模板参数匹配时,您才能添加两个不同的
。FlexArrays
应有效地将新数组添加到当前operator +=
。FlexArray
还可以从
和数字operator*
写出operator*=
和FlexArray
,其中乘以数字k > 0
是其本身k
次的串联。那些。k
。我们可以假设{1, 2} * 3 = {1, 2, 1, 2, 1, 2}
是k
unsigned long
您需要能够从左到右和从右到左进行乘法。那些。只有 3 个选项
、FlexArray *= k
、FlexArray * k
k * FlexArray
int main() { FlexArray<int> flex(3); flex.at(0) = 1; flex.at(1) = 2; flex.at(2) = 3; std::cout << flex.Size(); // 3 auto prod = flex * 2; for (int i = 0; i < prod.Size(); ++i) { std::cout << prod.at(i) << " "; } std::cout << "\n"; // Should output 1 2 3 1 2 3 FlexArray<int> last(2); last.at(0) = 4; last.at(1) = 5; flex += last; for (int i = 0; i < flex.Size(); ++i) { std::cout << flex.at(i) << " "; } std::cout << "\n"; // Should output 1 2 3 4 5 }
所以,这些方法的实现取决于你;这里没有具体写返回类型:
FlexArray<T>::FlexArray(); FlexArray<T>::FlexArray(size_t); FlexArray<T>::at(size_t); FlexArray<T>::Size(); FlexArray<T>::operator += (const FlexArray&); FlexArray<T>::operator *= (size_t); operator+(const FlexArray<T>&, const FlexArray<T>&); operator*(const FlexArray<T>&, size_t); operator*(size_t, const FlexArray<T>&);
仅发送结构代码到系统+可能需要的#include
这是我的解决方案:
template<typename T>
struct FlexArray {
std::vector<T> vec;
FlexArray();
FlexArray(size_t n);
T& at(size_t index);
const T& at(size_t index) const;
size_t Size() const;
FlexArray& operator += (const FlexArray& another);
FlexArray& operator *= (size_t k);
};
template<typename T>
FlexArray<T>::FlexArray() : vec(0){}
template<typename T>
FlexArray<T>::FlexArray(size_t n) : vec(n) {}
template<typename T>
T& FlexArray<T>::at(size_t index) {
return vec[index];
}
template<class T>
const T& FlexArray<T>::at(size_t index) const {
return vec[index];
}
template<typename T>
size_t FlexArray<T>::Size() const{
return vec.size();
}
template<typename T>
FlexArray<T>& FlexArray<T>::operator += (const FlexArray& another) {
for (size_t i = 0; i < another.Size(); i++) {
vec.push_back(another.at(i));
}
return *this;
}
template<typename T>
FlexArray<T>& FlexArray<T>::operator *= (size_t k) {
auto copy = *this;
for (size_t i = 1; i < k; i++) {
*this += copy;
}
return *this;
}
template<typename T>
FlexArray<T> operator+(const FlexArray<T>& left, const FlexArray<T>& right) {
auto copy = left;
copy += right;
return copy;
}
template<typename T>
FlexArray<T> operator*(const FlexArray<T>& arr, size_t k) {
auto copy = arr;
copy *= k;
return copy;
}
template<typename T>
FlexArray<T> operator*(size_t k, const FlexArray<T>& arr) {
return arr * k;
}
问题是它没有通过内存测试(64 MB 限制)。我的代码给出了 100ms / 86.77Mb。
测试系统采用g++17 7.3控制。
我该如何优化? (该任务取自在线课程,我确信可以以某种方式优化代码,这不是很困难,或者我在某个地方犯了错误)
在循环中使用
push_back()
并不是将 2 个向量连接在一起的有效方法。使用 vector::insert()
代替,例如:
template<typename T>
FlexArray<T>& FlexArray<T>::operator += (const FlexArray& another) {
vec.insert(vec.end(), another.vec.begin(), another.vec.end());
return *this;
}
此外,在执行串联之前,请使用
vector::reserve()
为新大小预先分配内存,例如:
template<typename T>
FlexArray<T>& FlexArray<T>::operator *= (size_t k) {
if (k > 1) {
auto copy = *this;
vec.reserve(vec.size() * k);
for (size_t i = 1; i < k; i++) {
*this += copy;
}
}
return *this;
}
template<typename T>
FlexArray<T> operator+(const FlexArray<T>& left, const FlexArray<T>& right) {
FlexArray<T> copy;
copy.vec.reserve(left.Size() + right.Size());
copy += left;
copy += right;
return copy;
}
或者,直接操作
vector
以避免不必要的复制,例如:
template<typename T>
FlexArray<T>& FlexArray<T>::operator += (const FlexArray& another) {
size_t oldSize = vec.size();
vec.resize(oldSize + another.Size());
std::copy(another.vec.begin(), another.vec.end(), vec.begin()+oldSize);
return *this;
}
template<typename T>
FlexArray<T>& FlexArray<T>::operator *= (size_t k) {
if (k > 1) {
size_t oldSize = vec.size();
vec.resize(oldSize * k);
for(size_t i = 0; i < oldSize; ++i) {
for (size_t j = 1; j < k; ++j) {
vec[i+(oldSize*j)] = vec[i];
}
}
}
else if (k == 0) {
vec.clear();
}
return *this;
}
template<typename T>
FlexArray<T> operator+(const FlexArray<T>& left, const FlexArray<T>& right) {
FlexArray<T> copy(left.Size() + right.Size());
std::copy(left.vec.begin(), lefft.vec.end(), copy.vec.begin());
std::copy(right.vec.begin(), right.vec.end(), copy.vec.begin()+left.Size());
return copy;
}
template<typename T>
FlexArray<T> operator*(const FlexArray<T>& arr, size_t k) {
FlexArray<T> copy(arr.Size()*k);
auto iter = copy.vec.begin();
for(size_t i = 0; i < k; ++i) {
std::copy(arr.vec.begin(), arr.vec.end(), iter);
iter += arr.Size();
}
return copy;
}