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

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

出力

（サイズ変更を伴う）追加は正常に機能し、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;
}

今は動作します。

EDIT2

reallocate()beta * nで2回呼び出すことはできません。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が呼び出されると、例外がスローされます。

OP編集後

私が言及した問題は、編集によっていくつかの方法で解決されますが、まだ欠陥があります： 常にrelocate内reallocateで呼び出されます。データは要素を保持するため、そこにあるデータの2倍のデータを読み取ることになります。これはアクセス違反を引き起こす可能性があるため、これが存在する限り、コードは安全ではないと見なす必要があります。代わりに、copyメソッドはそこにある量（n個の要素）だけを読み取る必要があります。もちろん、これは当然のことながら、nは常に配列内の正しい数の要素を保持しているため、が呼び出される前に変更してはなりません。beta * nsize = 2 * nnreallocate

于 2012-07-31T13:52:35.100 に答える