new int [] throws 'Violation d'accès' exception

Question

J'ai travaillé sur la classe Vector personnalisée. Tout fonctionne parfaitement sur le compilateur Microsoft, mais quand je l'essaye sur Borland, j'obtiens une erreur vraiment étrange. Borland lève l'exception à l'intérieur de la fonction d'insertion; Exactement lors de l'appel du constructeur de copie "Vector temp (* this);" au

"array_ = new int [rhs.size_];" ligne

void Vector::insert(int value, unsigned position) throw(SubscriptError) 
{ 
    check_bounds(position); 
    Vector temp(*this); 
    int tmpSize= size_; 
    temp.size_++; 
    size_++; 
    for (unsigned int i=tmpSize; i > position; i--) 
    { 
     temp[i] = temp[i-1]; 
    } 
    temp[position] = value; 

    //array_= temp.array_; 
    for(unsigned int i = 0; i < size_; i++) 
    { 
     array_[i]= temp.array_[i]; 
    } 
} 

et voici mon constructeur de copie;

Vector::Vector(const Vector& rhs) 
{ 
    array_ = new int[rhs.size_]; 
    size_ = rhs.size_; 
    for(unsigned int i = 0; i < rhs.size_; i++) 
    { 
     array_[i] = rhs.array_[i]; 
    } 
} 

et enfin c'est le main();

std::cout << "push_back 5 integers:\n"; 
for (int i = 0; i < 5; i++) 
{ 
    a.push_back(i); 
    Print(a); 
} 

std::cout << "insert(99, 3):\n"; 
a.insert(99, 3); 
Print(a); 
std::cout << "insert(98, 0):\n"; 
a.insert(98, 0); 
Print(a); 
std::cout << "insert(97, 6):\n"; 
a.insert(97, 6); 
Print(a); 

La chose étrange est premier appel d'insertion (a.insert (99, 3)) fonctionne très bien, il se bloque quand il vient au deuxième appel (a.insert (98, 0))

Voici le fichier en-tête complet

namespace CS170 
{ 
    class SubscriptError 
    { 
    public: 
     SubscriptError(int Subscript) : subscript_(Subscript) {}; 
     int GetSubscript(void) const { return subscript_; } 

    private: 
    int subscript_; 
    }; 

class Vector 
{ 
public: 

    static const int NO_INDEX = -1; 

    struct SortResult 
    { 
     unsigned compares; 
     unsigned swaps; 
    }; 

    // Default constructor 
    Vector(void); 

    // Destructor 
    ~Vector(); 

    // Copy constructor 
    Vector(const Vector& rhs); 

    // Constructor to create a Vector from an array 
    Vector(const int array[], unsigned size); 

    // Adds a node to the front of the list 
    void push_back(int value); 

    // Adds a node to the end of the list 
    void push_front(int value); 

    // Removes the last element. Does nothing if empty. 
    void pop_back(void); 

    // Removes the first element. Does nothing if empty. 
    void pop_front(void); 

    // Inserts a new node at the specified position. Causes an 
    // abort() if the position is invalid. (Calls check_bounds) 
    void insert(int value, unsigned position) throw(SubscriptError); 

    // Removes an element with the specified value (first occurrence) 
    void remove(int value); 

    // Deletes the underlying array and sets size_ to 0 
    void clear(void); 

    // Return true if the vector is empty, otherwise, false 
    bool empty(void) const; 

    // Assignment operator 
    Vector& operator=(const Vector& rhs); 

    // Concatenates a vector onto the end of this vector. 
    Vector& operator+=(const Vector& rhs); 

    // Concatenates two Vectors. 
    Vector operator+(const Vector& rhs) const; 

    // Subscript operators. 
    int operator[](unsigned index) const throw(SubscriptError); 
    int& operator[](unsigned index) throw(SubscriptError); 

    // Returns the number of elements in the vector. 
    unsigned size(void) const; 

    // Returns the size of the underlying array 
    unsigned capacity(void) const; 

    // The number of memory allocations that have occurred 
    unsigned allocations(void) const; 

    // This searches the vector using a binary search instead 
    // of a linear search. The data must be sorted. Returns 
    // the index. If not found, returns CS170::Vector::NO_INDEX. 
    // DO NOT SORT THE DATA IN THIS FUNCTION!!  
    int bsearch(int value) const; 

    // Sorts the elements using a selection sort. 
    // Returns the number of swaps/comparisons that occurred. 
    SortResult selection_sort(void); 

    // Sorts the elements using a bubble_sort. 
    // Returns the number of swaps/comparisons that occurred. 
    SortResult bubble_sort(void); 

    void swap(int &a, int& b); 

    void swapv(Vector &other); 

    void reverse(void); 

    bool operator==(const Vector& rhs) const; 

    void shrink_to_fit(void); 

private: 
    int *array_;  // The dynamically allocated array 
    unsigned size_;  // The number of elements in the array 
    unsigned capacity_; // The allocated size of the array 
    unsigned allocs_; // Number of allocations (resizes) 

    // Private methods... 
    void check_bounds(unsigned index) const throw(SubscriptError); 
    void grow(void); 

    // Other private methods... 
}; 

    }// namespace CS170 

     #endif // VECTOR_H 

Answer 1

Vous ne redimensionnez pas (de manière visible) array_ à l'intérieur de insert(). Cela signifie que vous allez toujours écrire un élément après la fin de sa mémoire allouée.

La copie de l'ensemble de la matrice (deux fois) permet une insertion très coûteuse. Qu'est-ce que vous essayez de réaliser qui ne peut pas être fait en std::vector?

Answer 2

à mon avis, mal est fait lorsque vous appelez la insert() pour la première fois. Lorsque vous insérez un élément, vous devez également augmenter les octets alloués à votre membre array_. Vous augmentez simplement le size_, mais qu'en est-il de l'augmentation de la taille réelle array_?

Par exemple, quelque chose comme ci-dessous se passe dans votre insert():

int size = 5; 
int *p = new int[size]; 
// ... populate p[i] (i = 0 to i = size - 1) 
size ++; 
p[size - 1] = VALUE; // oops ... incremented 'size' but before that reallocate to 'p' 

Après avoir appelé, d'abord insérer votre pile sera déjà corrompu. Donc c'est la 2ème fois que ça plante. Juste vérifier avec des modifications de code.

On remarque,

• Je pense que vous pouvez écrire insert(), plus optimisé. Je ne me sens pas besoin de copier le plein Vector<> en temporaire.
• Essayez également d'allouer plus de nombre d'octets à array_ que le besoin réel. Afin de ne pas devoir réallouer plusieurs fois
• Essayez de voir le code source de vector depuis STL pour une meilleure efficacité.

Answer 3

Dans votre fonction d'insertion, vous n'allouez pas de mémoire pour l'élément nouvellement inséré et après la première insertion, la copie ctr essaie de lire la mémoire non allouée sur la ligne où elle lève l'exception. La solution consisterait à allouer initialement plus de mémoire (c'est pourquoi la capacité est utilisée pour les implémentations vectorielles typiques) ou à augmenter le tableau alloué sur chaque insertion. Vous devez implémenter la réallocation sur les deux solutions, mais dans la première, elle sera appelée moins souvent.