La mise en œuvre de Vector en C++
J'ai récemment écrit une implémentation de la STL Vecteur comme un exercice de programmation. Le programme compile mais je reçois une erreur étrange en disant:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Je n'ai jamais eu cette erreur avant et ne suis pas sûr exactement ce que devrait être changé dans ma mise en œuvre pour le faire fonctionner correctement.
Quelqu'un peut jeter un oeil sur mon code et voir si quelque chose vous saute au visage comme erronées dans ce cas précis? Désolé je ne peux pas être plus précis, je ne suis pas sûr de savoir où chercher moi-même, merci d'avance.
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;
template <class T>
class Vector
{
public:
typedef T * iterator;
Vector();
Vector(unsigned int size);
Vector(unsigned int size, const T & initial);
Vector(const Vector<T> & v);
~Vector();
unsigned int capacity() const;
unsigned int size() const;
bool empty() const;
iterator begin();
iterator end();
T & front();
T & back();
void push_back(const T & value);
void pop_back();
void reserve(unsigned int capacity);
void resize(unsigned int size);
T & operator[](unsigned int index);
Vector<T> & operator=(const Vector<T> &);
private:
unsigned int my_size;
unsigned int my_capacity;
T * buffer;
};
//Your code goes here ...
template<class T>
Vector<T>::Vector()
{
my_capacity = 0;
my_size = 0;
buffer = 0;
}
template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
my_size = v.my_size;
my_capacity = v.my_capacity;
buffer = new T[my_size];
for (int i = 0; i < my_size; i++)
buffer[i] = v.buffer[i];
}
template<class T>
Vector<T>::Vector(unsigned int size)
{
my_capacity = size;
my_size = size;
buffer = new T[size];
}
template<class T>
Vector<T>::Vector(unsigned int size, const T & initial)
{
my_size-size;
my_capacity = size;
buffer = new T [size];
for (int i = 0; i < size; i++)
buffer[i] = initial;
T();
}
template<class T>
Vector<T> & Vector<T>::operator = (const Vector<T> & v)
{
delete[ ] buffer;
my_size = v.my_size;
my_capacity = v.my_capacity;
buffer = new T [my_size];
for (int i = 0; i < my_size; i++)
buffer[i] = v.buffer[i];
return *this;
}
template<class T>
typename Vector<T>::iterator Vector<T>::begin()
{
return buffer;
}
template<class T>
typename Vector<T>::iterator Vector<T>::end()
{
return buffer + size();
}
template<class T>
T& Vector<T>::Vector<T>::front()
{
return buffer[0];
}
template<class T>
T& Vector<T>::Vector<T>::back()
{
return buffer[size - 1];
}
template<class T>
void Vector<T>::push_back(const T & v)
{
if (my_size >= my_capacity)
reserve(my_capacity +5);
buffer [my_size++] = v;
}
template<class T>
void Vector<T>::pop_back()
{
my_size--;
}
template<class T>
void Vector<T>::reserve(unsigned int capacity)
{
if(buffer == 0)
{
my_size = 0;
my_capacity = 0;
}
T * buffer = new T [capacity];
assert(buffer);
copy (buffer, buffer + my_size, buffer);
my_capacity = capacity;
delete[] buffer;
buffer = buffer;
}
template<class T>
unsigned int Vector<T>::size()const//
{
return my_size;
}
template<class T>
void Vector<T>::resize(unsigned int size)
{
reserve(size);
size = size;
}
template<class T>
T& Vector<T>::operator[](unsigned int index)
{
return buffer[index];
}
template<class T>
unsigned int Vector<T>::capacity()const
{
return my_capacity;
}
template<class T>
Vector<T>::~Vector()
{
delete[]buffer;
}
int main()
{
Vector<int> v;
v.reserve(2);
assert(v.capacity() == 2);
Vector<string> v1(2);
assert(v1.capacity() == 2);
assert(v1.size() == 2);
assert(v1[0] == "");
assert(v1[1] == "");
v1[0] = "hi";
assert(v1[0] == "hi");
Vector<int> v2(2, 7);
assert(v2[1] == 7);
Vector<int> v10(v2);
assert(v10[1] == 7);
Vector<string> v3(2, "hello");
assert(v3.size() == 2);
assert(v3.capacity() == 2);
assert(v3[0] == "hello");
assert(v3[1] == "hello");
v3.resize(1);
assert(v3.size() == 1);
assert(v3[0] == "hello");
Vector<string> v4 = v3;
assert(v4.size() == 1);
assert(v4[0] == v3[0]);
v3[0] = "test";
assert(v4[0] != v3[0]);
assert(v4[0] == "hello");
v3.pop_back();
assert(v3.size() == 0);
Vector<int> v5(7, 9);
Vector<int>::iterator it = v5.begin();
while (it != v5.end())
{
assert(*it == 9);
++it;
}
Vector<int> v6;
v6.push_back(100);
assert(v6.size() == 1);
assert(v6[0] == 100);
v6.push_back(101);
assert(v6.size() == 2);
assert(v6[0] == 100);
v6.push_back(101);
cout << "SUCCESS\n";
}
Vous devez exécuter votre programme avec un débogueur de sorte que vous pouvez voir où cette exception est levée.
cplusplus.com/reference/std/new/bad_alloc
vous pouvez affiner la ligne dans main() après qui vous obtenez le message d'erreur?
Je vous suggère de créer un test unitaire pour au moins chaque méthode.
sur
cplusplus.com/reference/std/new/bad_alloc
vous pouvez affiner la ligne dans main() après qui vous obtenez le message d'erreur?
Je vous suggère de créer un test unitaire pour au moins chaque méthode.
sur
Vector<T>::Vector(unsigned int size, const T & initial)
Quoi que T()
vous avez là-bas ?
OriginalL'auteur UndefinedReference | 2011-03-01
Vous devez vous connecter pour publier un commentaire.
Voici le code source complet, mis à jour à partir de votre source:
return buffer[size-1];
devrait êtrereturn buffer[my_size-1];
dans leT& Vector<T>::back()
méthode.pop_back
devrait assurez-vous de libérer toutes les ressources de ce dernier élément a été d'avoir, sinon, vous êtes doom à une fuite de mémoire. Fairebuffer[my_size]->~T(); --my_size;
OriginalL'auteur Phu Ta
Peut-être de cette faute de frappe?
Il y a aussi un
size = size;
dansresize
qui devrait sans doute êtremy_size = size;
. Etbuffer = buffer;
dansreserve
qui devrait êtrethis->buffer = buffer;
.OriginalL'auteur Mark Ransom
Votre "réserve" est cassé. Utiliser un autre nom de variable pour le tampon local.
OriginalL'auteur Erik
Outre le besoin de réparer votre
reserve
fonction, votre constructeur par copie et de copie à l'affectation de l'opérateur ont un problème intéressant:Cela permettra de définir la capacité de t1 égale à la capacité (variable) de t2, mais la capacité réelle de t1 sera la taille de t2; Ainsi, comme vous commencer à pousser des éléments dans le vecteur après le constructeur par copie/cession-opérateur, vous aurez un problème de dépassement de mémoire tampon.
Vous avez besoin de la modifier pour
OU (si vous voulez lui permettre de redimensionner un petit tableau)
OriginalL'auteur Zac Howland
Ce code ne compile pas pour moi. Clang plaint de ce que la ligne 114 (la mise en œuvre de back() ) attendu "taille" d'être appelé.
Je pense que la ligne était destiné à être "tampon de retour[size() -1];"
Il donne également des mises en garde au sujet de la mise en œuvre de ce constructeur:
modèle
Vecteur::Vecteur(unsigned int size, const T & initial)
La première ligne est probablement censé pour être "my_size = taille;
La dernière ligne de ce constructeur) devrait probablement être supprimé.
Ensuite, il échoue à l'assertion de la ligne 209: assert(v3.size() == 1);
Cela ouvre tout un peut de vers, mais le problème évident est de redimensionner() à la ligne: "taille = taille; ce qui est probablement censé pour être "my_size = taille;
Avec ce changement, nous avons maintenant un incident sur la ligne 121 qui est en push_back() appelée à partir de la ligne 231 "v6.push_back(100);"
C'est de ne pas en raison de problèmes dans la réserve (les). Nous créons une variable locale "tampon" avec le même nom qu'une variable membre. Nous allons changer le nom de temp_buffer. Remarque: Ne pas assert() les erreurs d'exécution. assert() est pour les erreurs de logique. Cette assert() ne peut pas échouer. la nouvelle ne sera jamais de retour 0. Il va le jeter à la place.
Après avoir fait l'évidente résout en réserve() (il y a d'autres questions), nous sommes maintenant de s'écraser dans la copie() dans la réserve (les) dans l'appel de redimensionnement() appelée à partir de lin3 208 dans main(), "v3.redimensionner(1);".
Nous voyons que la réserve est fait attribution d'un nouveau tampon lorsque nous sommes à la réduction de la capacité. C'est à la fois une perte de performances et une perte de fiabilité (allocation de mémoire peut échouer). Mais nous devons toujours pas de plantage, donc nous allons essayer d'empêcher le crash sans aborder les évidents défauts de conception.
La panne est venue parce que nous sommes la copie de tous les éléments qui existent dans le récipient dans le nouvellement allouée tableau. Ce serait correct si nous n'étions que faire lorsque nous avons besoin d'augmenter notre capacité, mais dans ce cas, nous avons plus d'éléments que notre nouvelle capacité peut contenir. Le code doit définir my_size à la nouvelle capacité si elle est supérieure à cette valeur.
Maintenant le code de test des rapports de "RÉUSSITE".
Cependant, il ya encore de nombreux problèmes avec ce code.
L'un des plus grands problèmes est que nous ne sommes pas à l'aide de la mémoire non initialisée dans l'allocation d'un tableau. Cela est requis par la norme std::vector et il a à la fois les performances et la fiabilité des avantages. Mais elle complique également le code et donc cela peut être un raccourci, on peut vivre avec, pour ce qui est évidemment un exercice intellectuel.
Constructeurs: l'Utilisation de l'initialiseur de syntaxe pour initialiser les données membres.
Avec votre constructeur de copie et de votre constructeur à partir de la valeur initiale, vous aurez à la fuite de l'allocation d'un tableau si l'un de vos boucle attributions de lancer une exception.
De l'opérateur d'affectation doit allouer un nouveau tampon de taille "my_capacity" pas "my_size" bien qu'il existe une optimisation évidente que si la taille de la main droite côté d'un objet n'est pas plus grand que le "présent" de l'objet, nous ne devrions pas être d'allouer à tous.
Si l'allocation de la nouvelle matrice échoue dans l'opérateur d'affectation, nous avons déjà supprimé de la mémoire tampon, de sorte que nous allons finalement (quand notre Vecteur objet est détruit) ont une double supprimer de la mémoire tampon et nous pouvons avoir toute l'enfer, l'apocalypse avant.
Dans push_back(), afin de soutenir les garanties de performance de la norme, nous avons besoin d'augmenter la capacité de certains fraction constante de la taille de la capacité existante. Par exemple quelque chose comme: "la réserve(my_capacity * 1.5);"
OriginalL'auteur Jon Kalb