3

Eu estava respondendo um problema de implementação do std::stack. Foi fácil, porém eu não podia usar minha primeira idéia: o std::vector (substiuiu para sempre os ponteiros dinâmicos). O meu código é:

template <class T> class stack
{
    T* data;
    unsigned size_;

    public:
    stack() : size_(0){}
    stack(T initializer, unsigned times)
    {
        size_ = times;
        data = new T[times];
        for(int i = 0; i < times; i++) data[i] = initializer;
    }

    void push(T data_)
    {
        size_++;
        data = new T[size_];
        data[size_-1] = data_;
    }
    void pop()
    {
        size_--;
        data = new T[size_];
    }
    T top() const
    {
        return data[size_-1];
    }
    void clear()
    {
        for(unsigned i = 0; i < size_; i++)
        {
            data[i] = 0;
        }
    }
    bool empty() const
    {
        bool ret = true;
        for(unsigned i = 0; i < size_; i++)
        {
            if(data[i] != 0)
            {
                ret = false;
                break;
            }
        }
        return ret;
    }
    unsigned size() const
    {
        return size_;
    }
    void resize(unsigned newsize)
    {
        size_ = newsize;
        data = new T[size_];
    }
};

Resolvi testar com um inteiro; e funcionou. Porém, fiz um de tamanho 2 e resolvi testar o método pop.

int main()
{
    stack<unsigned> A;
    A.push(10);
    A.push(2);
    std::cout << A.top() << "\n";
    A.pop();
    std::cout << A.top();
}

Aí, o método top devolve lixo. O que eu estou fazendo de errado?

3
  • 3
    Você está alocando um vetor novo a cada push, e não está copiando os valores. Também não está liberando a memória. E também está misturando o tamanho do pilha com a capacidade dela com os elementos zerados. Acho que é isso :-) Commented 20/04/2014 às 19:57
  • Concordo com @C.E.Gesser. E não se esqueça de criar um destrutor ~stack() para sua classe. Pois, mesmo que você desaloque direitinho em push() e pop(), você também deve tratar de liberar a memória no destrutor.
    – Lucas Lima
    Commented 20/04/2014 às 20:31
  • @C.E.Gesser Você pode colocar isso na resposta e "arrumar" para mim? Eu tenho os problemas, porém não tenho as respostas :(.
    – user2692
    Commented 20/04/2014 às 22:05

2 Respostas 2

6

O primeiro ponto que podemos melhorar é sua alocação de memória. Alocar e desalocar a cada operação funciona, mas não é eficiente. Uma boa solução é alocar um bloco maior que o necessário inicialmente, e fazer novas alocações somente quando ele está cheio, assim como é feito no std::vector. Para isso precisamos adicionar um campo capacidade à pilha:

T *m_data;
std::size_t m_size;
std::size_t m_capacity;

Inicialize tudo com null e zeros. O push e o pop podem ficar assim então:

void push(const T &value) {
  if (m_capacity == 0) {
    m_capacity = 1; //Capacidade mínima
    m_data = new T[1];
  }
  else if (m_size == m_capacity) {
    T *old = m_data; //Guarda ponteiro
    m_capacity *= 2; //Dobra capacidade
    m_data = new T[m_capacity]; //Aloca novo array
    std::copy(old, old+m_size_, m_data); //Copia dados
    delete[] old; //Libera array antigo
  }
  m_data[m_size] = value; //Guarda novo valor
  ++ m_size; //Incrementa tamanho
}

void pop() {
  --m_size; //Basta decrementar o tamanho
}

Não é preciso desalocar no pop, pois quando houver um novo push ele vai aproveitar o array antigo. Mas você pode criar uma função trim para eliminar o espaço desnecessário.

void trim(const T &value) {
  if (m_capacity == m_size) {
    return;
  }
  T *old = m_data; //Guarda ponteiro
  if (m_size == 0) {
    m_data = NULL; //Para tamanho zero o array é nulo
  }
  else {
    m_data = new T[m_size]; //Aloca novo array
    std::copy(old, old+m_size_, m_data); //Copia dados
  }
  m_capacity = m_size; //Guarda novo valor de capacidade
  delete[] old; //Libera array antigo
}

Não se deve esquecer obviamente de deletar o array no destrutor. Um construtor de cópia e operador de atribuição também se fazem necessários, e se estiver já com c++11 pode fazer o construtor e o operador de atribuição de movimentação também.

O outro ponto são as suas funções clear e empty. Elas colocam o valor zero na pilha, e checam a quantidade desse valor. Dessa forma você não tem como diferenciar uma pilha vazia de uma cheia de zeros. No clearvocê deve apenas zerar o m_size e no empty basta checar se ele é zero.

void clear() {
  m_size = 0;
}

bool empty() {
  return m_size == 0;
}

Agora só bastaria adicionar funções de acesso aos elementos por índice que praticamente teria-se uma reimplementação de std::vector para tipos simples. Para ser completa seria necessário alocar a memória do array de forma crua e construir e destruir os objetos manualmente (placement contructor e chamada explícita ao destrutor) para que objetos não sejam criados antes da hora nem continuem existindo depois do necessário.

2
  • 1
    Vale ressaltar que para uma reimplementação de std::vector que siga o padrão seria necessário fazer diversas modificações para que, entre outras coisas, o destrutor do valor do tipo T removido do container na função pop fosse chamado. Essas modificações porem tornariam o código mais complexo e por isso entendo o motivo de terem sido deixados de lado nesta resposta. Commented 24/04/2014 às 13:20
  • 1
    @TiagoGomes Certamente, vou ressaltar esse ponto na última frase. Commented 24/04/2014 às 13:25
0

Com a ajuda do @C.E.Gesser, eu arrumei (esqueci como fazia o resize corretamente), arrumei o código. Ficou como o seguinte:

#include <iostream>
#include <algorithm>
template <class T> class stack
{
    T* data;
    unsigned size_;

    public:
    stack() : size_(0){}
    stack(T initializer, unsigned times)
    {
        size_ = times;
        data = new T[times];
        for(int i = 0; i < times; i++) data[i] = initializer;
    }

    void push(T data_)
    {
        T* temp = new T[size_ + 1];
        std::copy(data, data+size_, temp);
        size_++;
        data = new T[size_];
        std::copy(temp, temp+size_, data);
        data[size_-1] = data_;
    }
    void pop()
    {
        T* temp = new T[size_-1];
        std::copy(data, data+(size_-1), temp);
        size_--;
        data = new T[size_];
        std::copy(temp, temp+size_, data);
    }
    T top() const
    {
        return data[size_-1];
    }
    void clear()
    {
        for(unsigned i = 0; i < size_; i++)
        {
            data[i] = 0;
        }
    }
    bool empty() const
    {
        bool ret = true;
        for(unsigned i = 0; i < size_; i++)
        {
            if(data[i] != 0)
            {
                ret = false;
                break;
            }
        }
        return ret;
    }
    unsigned size() const
    {
        return size_;
    }
    void resize(unsigned newsize)
    {
        size_ = newsize;
        data = new T[size_];
    }
};

int main()
{
    stack<unsigned> A;
    A.push(10);
    A.push(2);
    std::cout << A.top() << "\n";
    A.pop();
    std::cout << A.top();
}
3
  • Melhorou um pouco, mas ainda está estranho o seu clear e o empty. E podemos melhorar o desempenho do push evitando fazer realocação a cada operação. Amanhã quando eu tiver acesso ao meu computador publico uma resposta complet. Commented 21/04/2014 às 2:11
  • 1
    O jeito como você realoca o espaço para os elementos também esta estranho e gastando mais memória que o necessário. Você aloca um novo vetor com o tamanho novo, copia os elementos antigos para ele, aloca novamente um vetor com o tamanho novo e copia a copia que você tinha feito para este novo, esta última alocação e cópia não são necessarios. Alem disso você não esta desalocando a memória utilizada. Commented 21/04/2014 às 17:46
  • @TiagoGomes Qualquer resposta é bem vinda.
    – user2692
    Commented 21/04/2014 às 18:52

Você deve fazer log-in para responder a esta pergunta.