优化运算符重载和模板结构中的内存

问题描述 投票：0回答：1

任务：

在此任务中，您必须编写一个既像 C 中的常规数组又像 Python 中的列表一样工作的结构。即写一个结构

template<typename T>
struct FlexArray;

那些。这是一个模板结构。它是一个固定长度的

T
类型元素数组，长度在构造函数中传递。默认情况下，您应该假设长度为 0。（这并不要求您在实现时仅使用经典数组）

通过 

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控制。

我该如何优化？ （该任务取自在线课程，我确信可以以某种方式优化代码，这不是很困难，或者我在某个地方犯了错误）

c++ c++17 g++
1个回答
0
投票

在循环中使用 

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;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.