未綁定的數組 - 具有奇怪行爲的PopBack

Question

我寫了一個未綁定的數組，練習一些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 

TEST.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; 
} 

輸出

添加（含調整）正常工作，也做運營商[ ]。只是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; 
} 

它現在起作用。

EDIT2

reallocate()不能beta * n被調用兩次，在popBack()它必須是w/beta。 popBack()現在退貨退貨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; 
} 

Answer 1

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被稱爲空數組。

的有機磷農藥編輯

我提到的問題後，是由編輯解決了一些辦法，但仍有缺陷： reallocate總是調用beta * n所以內部重新分配size = 2 * n。由於數據將包含n元素，它將最終讀取的數據量是那裏的兩倍。這可能會觸發訪問違規，所以您應該認爲您的代碼只要存在就不安全。相反，複製方法應該只讀取那裏（n個元素）。當然這需要理所當然的是n總是保持數組中正確數量的元素，因此在調用reallocate之前不能更改它。