Реализация стека на C++ с исключениями


Ценю ваши мысли и отзывы...

Стек.ч

//  Stack implementation
//  Push/Pop - Last In First Out
//

#pragma once

#include <memory>

template<class T>
class CStack
{

public:
    enum { DEFAULT_SIZE = 5 };

    CStack();
    CStack(const CStack& rhs);
    CStack(CStack&& rhs);
    CStack& operator=(const CStack& rhs);
    CStack& operator=(CStack&& rhs);
    ~CStack();  

    bool Empty() const;

    void Pop();
    bool Push(const T& t);
    const T& Top() const;
    T& Top();

private:
    bool Grow();

private:
    std::allocator<T> m_Allocator;
    T* m_pBase;
    int m_iCapacity;
    int m_iSize;
};

template<class T>
CStack<T>::CStack()
    : m_iCapacity(DEFAULT_SIZE)
    , m_iSize(0)
    , m_pBase(nullptr)
{
    //  allocate some memory for out stack
    try {
        m_pBase = m_Allocator.allocate(DEFAULT_SIZE);
    } catch (const std::bad_alloc& e) {
        //  do some error logging
        std::cerr << "Allocation Failed: " << e.what() << std::endl;
        //  rethrow exeception so client of this class can also handle it in whatever way they choose
        throw;
    }
}

template<class T>
CStack<T>::CStack(const CStack& rhs)
{
    try {
        //  allocate enough memory to hold stack
        m_pBase = m_Allocator.allocate(rhs.m_iCapacity);
    } catch (const std::bad_alloc& e) {
        //  do some error logging
        std::cerr << "Allocation Failed: " << e.what() << std::endl;
        //  rethrow exeception so client of this class can also handle it in whatever way they choose
        throw;
    }

    //  copy across the stack
    //  this performs a deep copy
    for (int i = 0; i < rhs.m_iSize; ++i) {
        //  copy across the T that is in the corresponding place
        m_Allocator.construct(m_pBase + i, *(rhs.m_pBase + i));
    }

    //  copy across size and capacity
    m_iCapacity = rhs.m_iCapacity;
    m_iSize = rhs.m_iSize;
}

template<class T>
CStack<T>::CStack(CStack&& rhs)
    : m_pBase(std::move(rhs.m_pBase))
    , m_iCapacity(rhs.m_iCapacity)
    , m_iSize(rhs.m_iSize)
{
    rhs.m_iCapacity = 0;
    rhs.m_iSize = 0;
    rhs.m_pBase = nullptr;
}

template<class T>
CStack<T>& CStack<T>::operator=(const CStack& rhs)
{
    //  check for self-assignment
    if (this == &rhs) {
        return *this;
    }

    //  perform copy-swap idiom
    //  create deep copy
    CStack<T> copy(rhs);

    //  swap 
    std::swap(m_pBase, copy.m_pBase);
    std::swap(m_iCapacity, copy.m_iCapacity);
    std::swap(m_iSize, copy.m_iSize);

    //  copy will be destructed when this function exits
    return *this;
}


template<class T>
CStack<T>& CStack<T>::operator=(CStack&& rhs)
{
    //  check for self move
    if (this == &rhs) {
        return *this;
    }

    //  take ownership of lhs memory
    T* pOldBase = m_pBase;
    int m_iOldCapacity = m_iCapacity;
    int iOldSize = m_iSize;

    //  move across ownership of rhs memory to lhs
    m_pBase = std::move(rhs.m_pBase);
    m_iCapacity = rhs.m_iCapacity;
    m_iSize = rhs.m_iSize;

    //  make sure rhs points to null
    rhs.m_pBase = nullptr;
    rhs.m_iCapacity = 0;
    rhs.m_iSize = 0;

    //  now that lhs points to rhs
    //  destruct old lhs
    for (int i = 0; i < iOldSize; ++i) {
        m_Allocator.destroy(pOldBase + i);
    }

    m_Allocator.deallocate(pOldBase, m_iOldCapacity);

    return *this;
}

template<class T>
CStack<T>::~CStack()
{
    //  check for valid pointer
    //  stack could have been moved-from
    //  and so the pointer will be null
    if (m_pBase) {
        //  destory any objects on the stack
        for (int i = 0; i < m_iSize; ++i) {
            m_Allocator.destroy(m_pBase + i);
        }

        //  deallocate any memory
        m_Allocator.deallocate(m_pBase, m_iCapacity);
    }
}

//  no op on an empty stack
//  use Empty() to check if stack is empty
template<class T>
void CStack<T>::Pop()
{
    //  destroy the top element
    m_Allocator.destroy(m_pBase + (m_iSize - 1));

    //  reduce the size of the stack
    --m_iSize;
}

template<class T>
bool CStack<T>::Push(const T& t)
{
    if (!m_pBase) return false;

    //  does the stack need to grow
    if ((m_iSize + 1) > m_iCapacity) {
        //  increase the size of the stack
        if (!Grow()) {
            return false;
        }
    }

    //  increase the size to include new element
    ++m_iSize;

    //  construct the pushed object in the allocated memory
    m_Allocator.construct(m_pBase + (m_iSize - 1), t);

    return true;
}

//  returns a const reference to the top element in the stack
//  it is up to the caller to make sure stack is non-empty using Empty() function
template<class T>
const T& CStack<T>::Top() const
{
    return *(m_pBase + (m_iSize - 1));
}

//  returns a const reference to the top element in the stack
//  it is up to the caller to make sure stack is non-empty using Empty() function
template<class T>
T& CStack<T>::Top()
{
    return *(m_pBase + (m_iSize - 1));
}

//  checks size of stack and returns true (if empty) or false 
template<class T>
bool CStack<T>::Empty() const
{
    return m_iSize <= 0;
}

//  increases the size of the stack by allocating a larger block of memory
//  and copying the stacks elements to it.
template<class T>
bool CStack<T>::Grow()
{
    //  not that stack should ever grow this big but just incase
    //  avoid overflow
    if (m_iCapacity >= (std::numeric_limits<int>::max() / 3)) {
        return false;
    }

    //  create a new stack twice the size
    int iNewCapacity = m_iCapacity * 2;

    T* pTempBase = nullptr;
    try {
        //  allocate some unintialised memory
        pTempBase = m_Allocator.allocate(iNewCapacity);
    } catch (const std::bad_alloc& e) {
        //  do some error logging
        std::cerr << "Allocation Failed: " << e.what() << std::endl;
        //  rethrow exeception so client of this class can also handle it in whatever way they choose
        throw;
    }

    for (int i = 0; i < m_iSize; ++i) {
        //  construct a copy in place in new allocation block
        m_Allocator.construct(pTempBase + i, *(m_pBase + i));
    }

    //  now that we have a exact copy of the stack
    //  swap pointers
    std::swap(m_pBase, pTempBase);

    //  deconstruct each object in the original stack
    for (int i = 0; i < m_iSize; ++i) {
        //  construct a copy in place in new allocation
        m_Allocator.destroy(pTempBase + i);
    }

    //  deallocate memory
    m_Allocator.deallocate(pTempBase, m_iCapacity);

    //  set the new capcity
    m_iCapacity = iNewCapacity;

    return true;
}

Код можно найти на Гитхабе

Обновленная версия с кодом рецензирования добавлен новый репозиторий

Некоторые из моих собственных заметок, чтобы помочь вам понять мой выбор..

Я оставил его, чтобы пользователь моего стека, чтобы проверить, если стек пуст, прежде чем пытаться поп-элемент. Это как стл это делает. Интересно услышать ваши мысли. Может быть, исключение лучше, когда поп на пустой стек пытался?

Pop() не возвращает ничего. Вы используете Top() и Pop() чтобы удалить элемент из стека. Опять в стиле STL.

Я с помощью распределителя, чтобы избежать лишних вызовов конструкторов в пустые ячейки стека. Не получится ли другой способ добиться этого. Считаю пустой стек из 5 элементов. Без выделения блок неинициализированное памяти, конструктор типа T назвали бы 5 раз.

Я перебросок исключений мой стек производит. Лучше просто зайти в сообщение cerr и потреблять исключение (не выдали)?

Общественный Resize функция принимает размер лучше Grow()? Кто-то, возможно, захотите, чтобы уменьшить объем памяти, занимаемой стеком вручную.



1195
14
задан 14 марта 2018 в 04:03 Источник Поделиться
Комментарии
3 ответа

Я хотел, чтобы имена методов начинаются с маленькой буквы, чтобы отличить их от определенных типов пользователей. Но это я.

Пару мелочей:

template<class T>
CStack<T>& CStack<T>::operator=(const CStack& rhs)
{
// check for self-assignment
if (this == &rhs) {
return *this;
}

Вы используете копирование и замена фразеологизма. Это работает для самостоятельного назначения.

Я бы не стал делать проверку самостоятельное назначение, так как это pessimizing стандартного варианта использования в попытке оптимизировать для очень нестандартных вариантов использования.

Хотя потенциал для самостоятельного назначения существует (и ваш оператор должен работать для самостоятельного назначения), в истинное назначение жизни чрезвычайно редкое. Таким образом, ваш пессимизации в приведенный выше код выполняется на миллиарды миллиардов раз, когда он не нужен, по сравнению с один раз это поможет (конечно проверить, если мое предположение верно в коде). Но стандартные контейнеры не выполнив проверку.

Ваши перемещения операторов выгляжу нормально - хотя вы, вероятно, следует пометить их noexcept.

Но как двигаться операторы могут быть легко реализованы через операции своп.

Простой способ записи этих трех операторов:

template<class T>
CStack<T>::CStack(CStack&& rhs) noexcept
: m_pBase(nulllptr)
, m_iCapacity(0)
, m_iSize(0)
{
swap(rhs);
}
template<class T>
CStack<T>& CStack<T>::operator=(CStack const& rhs)
{
CStack<T> copy(rhs);
swap(copy);
return *this;
}
template<class T>
CStack<T>& CStack<T>::operator=(CStack&& rhs) noexcept
{
swap(rhs);
return *this;
}
template<class T>
void CStack<T>::swap(CStack<T>& other) noexcept
{
using std::swap;
swap(m_pBase, other.m_pBase);
swap(m_iCapacity, other.m_iCapacity);
swap(m_iSize, other.m_iSize);
}

Теперь если мы посмотрим на операторы присваивания. Мы можем оптимизировать их вместе в одно задание, которое работает как для перемещения и копирования.

template<class T>
CStack<T>::CStack(CStack&& rhs) noexcept
: m_pBase(nulllptr)
, m_iCapacity(0)
, m_iSize(0)
{
swap(rhs);
}
template<class T>
CStack<T>& CStack<T>::operator=(CStack rhs) noexcept
{
// Notice the parameter is a value
// If called with a r-value the parameter is move constructed (if it has one).
// If called with a value or reference (or has no move constructor) the parameter is copy constructed

// The original copy assignment had an internal copy but that
// is taken care of by the parameter above.

// Both copy/move assignment are identical for the last part.
swap(rhs);
return *this;
}
template<class T>
void CStack<T>::swap(CStack<T>& other) noexcept
{
using std::swap;
swap(m_pBase, other.m_pBase);
swap(m_iCapacity, other.m_iCapacity);
swap(m_iSize, other.m_iSize);
}

Только что заметил еще одну вещь :-)

Следите за неудачу во время строительства. Если это произойдет, деструктор не вызывается.

// Say you manage to create the first 4 of 8 copies.
// Then the 5th copy fails and throws.

for (int i = 0; i < rhs.m_iSize; ++i) {
// copy across the T that is in the corresponding place
m_Allocator.construct(m_pBase + i, *(rhs.m_pBase + i));
}

// In this situation you leak 4 objects and m_pBase pointer.
// You should probably do this construction inside a try block
// and make sure you undo any objects on failure.

Я многое из этого в моей статье на векторы.

http://lokiastari.com/blog/2016/02/27/vector/

10
ответ дан 14 марта 2018 в 05:03 Источник Поделиться

std::allocator_traits Это лучший способ, чтобы взаимодействовать с распределителем. Он предлагает по умолчанию создать и уничтожить, если распределитель не делает этого сам.

using alloc_traits = std::allocator_traits<std::allocator<T>>;

Если вы хотите быть полностью распределитель-известно, что вы должны также подготовиться к любой фантазии указатель, что выделения может использовать.

using pointer = alloc_traits::pointer;
using ptr_traits = std::pointer_traits<pointer>;

Вы также должны быть готовы распространить распределитель по мере необходимости на копирование и перемещение.

Предпочитаю std::size_t и std::ptrdiff_t при работе с размерами и смещениями.

При копировании для роста, вы должны сделать шаги:

for (int i = 0; i < m_iSize; ++i) {
// construct a copy in place in new allocation block
alloc_traits::construct(m_Allocator, pTempBase + i, std::move(*(m_pBase + i)));
}

Обеспечить движение вариант для толчка.

template<class T>
bool CStack<T>::Push(T&& t)
{
if (!m_pBase) return false;

// does the stack need to grow
if ((m_iSize + 1) > m_iCapacity) {
// increase the size of the stack
if (!Grow()) {
return false;
}
}

// increase the size to include new element
++m_iSize;

// construct the pushed object in the allocated memory
alloc_traits::construct(m_Allocator, m_pBase + (m_iSize - 1), std::move(t));

return true;
}

Со всеми раз вы копируете вставлены комментарии там обязательно будут ошибки в них, когда вы забыли обновить их (например, не-const Top()). Чтобы избежать этого, предпочитают хранить комментарии к минимуму, если нужно объяснить используемый алгоритм.

12
ответ дан 14 марта 2018 в 05:03 Источник Поделиться

Ну, есть много, чтобы улучшить:


  1. Вы игнорируете правила стандартные-библиотеки. Что делает (повторно)использовать, особенно используя шаблоны, практически невозможно, а значит, каждый должен узнать, что интерфейс.

  2. Кто-то использует ваш код не может сделать ничего полезного с DEFAULT_SIZEтаким образом, что реализация-деталь не должна подвергаться.

  3. Ваш класс не может быть статически построены, и по умолчанию-конструктор может бросить. Изменить его так, по умолчанию-конструктор не нужно выделять память.

  4. В связи с вышесказанным, переходя из инстанции оставить переехать из экземпляра в зомби-состояние достижимо только таким образом. Я не уверен, что вполне квалифицируется как "допустимый, но не указано", но это лучшее, что вы можете сделать, если любое допустимое государственных нужд динамически выделенную память и ваш переезд-конструктор должен не бросать, ведь что бы сделать его почти бесполезно.

  5. Вам не кажется TryPush() более подходящее название, учитывая, он может потерпеть без исключения? Я держала в ваш именования схему, хотя она является внешней по отношению к с++.

  6. Если вы не знаете всех своих потенциальных элемент-типа не выиграют от переезда-Инг, а также обеспечит переход-вариант выше.

  7. Рассмотреть вопрос об осуществлении template <class... ARGS> bool try_emplace(ARGS... args) и сделать пуш-вариантов делегировать это. Что приводит к меньше повторений и больше эффективности.

  8. Не хранить std::allocator<T>-члены. Что напрасно раздувает свой класс, вы можете просто создать экземпляр по требованию без затрат там, где это необходимо.

  9. Вход и выход должны только быть сделано, когда программист запрашивает его. Делать это самостоятельно, будь то ошибка или что, если нет конкретного запроса, серьезно уменьшает возможности повторного использования.

  10. Вы действительно должны реализовать friend void swap(CStack&, CStack&) noexcept и использовать там, где это уместно (например, с помощью копирования и замены для Move-конструктор и Move-цессии). Опираясь на std::swap() для пользователей работает, но неэффективно, и вы напишете в своей реализации, по крайней мере, один раз в любом случае.

  11. Вы знаете, что вы полагаетесь на элемент-тип быть легко скопированы? Вы должны двигаться, где допускается для большей эффективности, и защиты от копирования исключение.

6
ответ дан 15 марта 2018 в 05:03 Источник Поделиться