1

我写了一个未绑定的数组，来练习一些 C++。但是 popBack 方法不能正常工作。我只是要粘贴我的代码，我希望它不会太多。代码使用 gcc (MacPorts gcc47 4.7.1_1) 4.7.1 编译。我会很感激一些帮助。谢谢 ：）

unbound_array.hpp

#ifndef _unbound_array_h_
#define _unbound_array_h_

#include <iostream>

namespace datastructures
{

template <typename T>
class UnboundArray {

private:
    int beta;
    int alpha;
    int w;
    int n;

    //T data[];
    T *data;

    auto reallocate(const int size) -> void;

public:
    UnboundArray(): beta(2) {
        alpha = 4;
        w = 1;
        n = 0;
        data = new T[w];
    }

//  void pushBack(T& element);
    auto pushBack(T element) -> void;
    auto popBack() -> T;
    auto operator [](const int& b) -> T&;
};  

    template <typename T>
    auto UnboundArray<T>::pushBack(T element) -> void {
        if (n == w) {
            reallocate(beta * n);
        }
        data[n] = element;
        n++;
   }

    template <typename T>
    auto UnboundArray<T>::popBack() -> T {
        n = (n == 0) ? 0 : (n - 1);
        if ((alpha * n <= w) && n > 0) {
            reallocate(beta * n);
        }
        return data[n];
    }

    template <typename T>
    auto UnboundArray<T>::operator [](const int& b) -> T&{
        return data[b];
    }

    template <typename T>
    auto UnboundArray<T>::reallocate(const int size) -> void {
        int idx = n;
        w = size;
        T *array = new T[w];
        for (int i = 0; i < idx; ++i) array[i] = data[i];
        delete[] data;
        data = array;
        std::cout << "Reallocation. #elements: " << (n + 1) 
        << " new size of UnboundArray: " << w << std::endl;
    }

} // datastructures
#endif

测试.cpp

#include <iostream>
#include "unbound_array.hpp"


using namespace datastructures;

int main() {
    int num = 25;

    std::cout << "Test of datastructures" <<std::endl;
    UnboundArray<int> a;
    for (int i = 0; i < num; ++i) {
        std::cout << "Adding "<< i <<" to UnboundArray." << std::endl;
        a.pushBack(i);
    }

    for (int i = 0; i < num; ++i) {
        std::cout << "array[" << i << "] = "<< a[i] << std::endl;
    }

    for (int i = 0; i < num; ++i) {
        std::cout << "Popping " << a.popBack() << std::endl;
    }

    return 0;
}

输出

添加（调整大小）效果很好，operator[] 也可以。只是 popBack 困扰我。

Popping 24
Popping 23
Popping 22
Popping 21
Popping 20
Popping 19
Popping 18
Popping 17
Popping 16
Popping 15
Popping 14
Popping 13
Popping 12
Popping 11
Popping 10
Popping 9
Reallocation. #elements: 9 new size of UnboundArray: 16
Popping 8
Popping 7
Popping 6
Popping 5
Reallocation. #elements: 5 new size of UnboundArray: 8
Popping 3
Popping 3
Reallocation. #elements: 3 new size of UnboundArray: 4
Popping 556531726
Reallocation. #elements: 2 new size of UnboundArray: 2
Popping -268435456
Popping 0

编辑

我在重新分配中更改了代码。

template <typename T>
auto UnboundArray<T>::reallocate(const int size) -> void {
    w = size;
    T *array = new T[w];
    for (int i = 0; i < w; ++i) array[i] = data[i];
    delete[] data;
    data = array;
    std::cout << "Reallocation. #elements: " << (n + 1)
    << " new size of UnboundArray: " << w << std::endl;
}

现在可以了。

编辑2

reallocate()不能用 调用两次beta * n，popBack()必须是w / beta。 popBack()现在返回 return data[--n]。该数组未分配malloc(). 功能就在那里，我将添加一些检查，但仅此而已。谢谢你。

template <typename T, size_t ALPHA, size_t BETA>
auto UnboundArray<T, ALPHA, BETA>::pushBack(T& element) -> void {
        if (n == w) {
                reallocate(BETA * n);
        }
        data[n++] = element;
}

template <typename T, size_t ALPHA, size_t BETA>
auto UnboundArray<T, ALPHA, BETA>::popBack() -> T {
        if ((ALPHA * n <= w) && n > 0) {
                reallocate(w / BETA);
        }
        T ret = data[--n];
        data[n] = 0;
        return ret;
}

template <typename T, size_t ALPHA, size_t BETA>
auto UnboundArray<T, ALPHA, BETA>::operator[](const int& b) -> T& {
        return data[b];
}

template <typename T, size_t ALPHA, size_t BETA>
auto UnboundArray<T, ALPHA, BETA>::reallocate(const int size) -> void {
        w = size;
        T* array = (T*) malloc(sizeof(T) * w);
        for (int i = 0; i < n; i++) array[i] = data[i];
        free(data);
        data = array;
        std::cout << "Reallocation. #elements: " << n << " new max size of UnboundArray: " << w << std::endl;
}
4

1 回答 1

4

您popBack减小了数组的大小，可能会重新定位，它会使用缩小的大小进行复制，然后尝试读取旧大小的最后一个元素（未复制）。我建议您将 popBack 更改为：

template <typename T>
    auto UnboundArray<T>::popBack() -> T {
        n = (n == 0) ? 0 : (n - 1);
        T result = data[n];
        if ((alpha * n <= w) && n > 0) {
            reallocate(beta * n);
        }
        return result;
    }

当在空数组上调用 popBack 时，我也会抛出异常。

在 OPs 编辑之后

我提到的问题在某种程度上通过编辑解决了，但仍然存在缺陷： reallocate总是beta * n在 reallocate 中使用 so调用size = 2 * n。由于数据将保存n元素，因此最终读取的数据量将是那里的两倍。这可能会触发访问冲突，因此只要存在这种情况，您就应该认为您的代码是不安全的。相反，复制方法应该只读取那里的内容（n 个元素）。reallocate当然，这是理所当然的，n 总是在数组中保存正确数量的元素，因此在调用之前不能更改它。

于 2012-07-31T13:52:35.100 回答