For an excersize, I write a class to contain elements. They are sorted using std::lower_bound before being inserted. Inserting duplicate items will silently fail.

I have this very strange bug that's causing stack frame corruption and I don't know why. I conclude it's this class because if I replace the container with std::vector instead of with my custom class, it works fine.

Can someone go over this code and see if they see anything wrong with it?

SortedList.hpp

// ----------------------------------------------------------------------------
// GOLSortedList.hpp
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// include files

#include <iostream>

namespace GOL {

template <class T>
class SortedList
{
public:

    typedef T* iterator;
    typedef const T* const_iterator;

    /*!
     * @brief Default constructor
     */
    SortedList();

    /*!
     * @brief Constructs a sorted list with a specified pre-allocated chunk of memory
     * @param preallocate The amount of memory in sizeof(T) to allocate
     */
    SortedList( std::size_t preallocate );

    /*!
     * @brief Copy constructor
     */
    SortedList( const SortedList<T>& that );

    /*!
     * @brief Default destructor
     */
    ~SortedList();

    /*!
     * @brief Inserts an item into the sorted list
     * Will perform a binary search of all existing items in the list to
     * determine where to insert
     * @param item The item to insert
     */
    void insert( const T& item );

    /*!
     * @brief Erases an item from the list, shifting all data above it down
     * No memory re-allocation occurs during this process
     * @exception If the specified index in the list is out of bounds, an
     * exception is thrown.
     * @param index Index of the item to erase
     */
    void erase( std::size_t index );

    /*!
     * @brief Erases an item from the list, shifting all data above it down
     * No memory re-allocation occurs during this process
     * @param it The item to erase
     */
    void erase( iterator it );

    /*!
     * @brief Searches the list for the specified item
     * The complexity of the search is O(log(n)) (successive approximation).
     * If the item wasn't found, an iterator pointing at @a end() is returned.
     * @param item The item to look for
     * @return An iterator pointing to the item if it exists
     */
    iterator find( const T& item );

    /*!
     * @brief Clears the content of the list without de-allocating any memory
     */
    void clear();

    /*!
     * @brief Resizes the list and forces re-allocation of memory
     * @param size The size to re-allocate
     */
    void resize( std::size_t size );

    /*!
     * @brief Returns a pointer to the beginning of the data in the list
     * @return An iterator to the beginning of the data
     */
    iterator begin();

    /*!
     * @brief Returns a const pointer to the beginning of the data in the list
     * @return A const iterator to the beginning of the data
     */
    const_iterator begin() const;

    /*!
     * @brief Returns a pointer to the end of the data in the list
     * @return An iterator to the end of the data
     */
    iterator end();

    /*!
     * @brief Returns a const pointer to the end of the data in the list
     * @return A const iterator to the end of the data
     */
    const_iterator end() const;

    /*!
     * @brief Returns the size of the list (how many items are currently inserted)
     * @return The size of the list
     */
    std::size_t size();

    /*!
     * @brief Returns the amount of memory the list has allocated
     * @return The allocated size of the list
     */
    std::size_t allocatedSize();

    /*!
     * @brief Returns a reference to the specified item in the list
     * @exception If the specified index in the list is out of bounds, an
     * exception is thrown.
     * @param index The index of the item
     * @return A reference to the specified item
     */
    T& at( std::size_t index );

    /*!
     * @brief Returns a reference to the specified item in the list
     * @exception If the specified position in the list is out of bounds, an
     * exception is thrown.
     * @param index The index of the item
     * @return A reference to the specified item
     */
    const T& at( std::size_t index ) const;

    /*!
     * @brief Overload assignment operator
     */
    const SortedList<T>& operator=( const SortedList<T>& that );

    /*!
     * @brief Overload subscript operator
     * @note If _DEBUG is defined, this function calls @a at. If _DEBUG is not
     * defined, this function returns the data directly without bounds checking
     */
    T& operator[]( std::size_t index );

    /*!
     * @brief Overload const subscript operator
     * @note If _DEBUG is defined, this function calls @a at. If _DEBUG is not
     * defined, this function returns the data directly without bounds checking
     */
    const T& operator[]( std::size_t index ) const;

private:

    T*              m_Data;
    std::size_t     m_UsedSize;
    std::size_t     m_AllocatedSize;
};

} // namespace GOL

SortedList.cpp

// ----------------------------------------------------------------------------
// GOLSortedList.hxx
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// include files

#include <GOLSortedList.hpp>

#include <Exception.hpp>
#include <sstream>
#include <algorithm>

namespace GOL {

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::SortedList() :
    m_Data(0),
    m_UsedSize(0),
    m_AllocatedSize(0)
{
}

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::SortedList( std::size_t preallocate ) :
    m_Data(0),
    m_UsedSize(0),
    m_AllocatedSize(0)
{
    m_Data = new T[preallocate];
    for( std::size_t n = 0; n != preallocate; ++n )
        m_Data[n] = T();
    m_UsedSize = preallocate;
    m_AllocatedSize = preallocate;
}

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::SortedList( const SortedList<T>& that ) :
    m_Data(0),
    m_UsedSize(0),
    m_AllocatedSize(0)
{
    *this = that;
}

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::~SortedList()
{
    if( m_Data )
        delete[] m_Data;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::insert( const T& item )
{

    // get insert position
    std::size_t insertPos = std::lower_bound( m_Data, m_Data+m_UsedSize, item ) - m_Data;
    if( insertPos != m_UsedSize )
        if( m_Data[insertPos] == item )
            return;

    // re-allocate if necessary
    if( m_UsedSize == m_AllocatedSize )
    {
        T* temp = new T[m_UsedSize+1];
        for( std::size_t n = 0; n != insertPos; ++n )
            temp[n] = m_Data[n];
        for( std::size_t n = insertPos; n != m_UsedSize; ++n )
            temp[n+1] = m_Data[n];
        if( m_Data )
            delete[] m_Data;
        m_Data = temp;
        m_Data[insertPos] = item;
        ++m_AllocatedSize;
        ++m_UsedSize;

    // insert item without re-allocating
    }else
    {
        ++m_UsedSize;
        for( std::size_t n = m_UsedSize; n > insertPos; --n )
            m_Data[n] = m_Data[n-1];
        m_Data[insertPos] = item;
    }
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::erase( std::size_t pos )
{
    if( pos >= m_UsedSize )
    {
        std::stringstream ss; ss << "[SortedList::erase] Error: Index out of bounds: " << pos << ", actual list size: " << m_UsedSize;
        throw Exception( ss.str() );
    }

    // shift top part of list down, overwriting value to erase
    for( std::size_t n = pos+1; n != m_UsedSize; ++n )
        m_Data[n-1] = m_Data[n];
    if( m_UsedSize > 0 )
        --m_UsedSize;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::erase( SortedList<T>::iterator it )
{
    // shift top part of list down, overwriting value to erase
    for( iterator n = it+1; n != this->end(); ++n )
        *(n-1) = *n;
    if( m_UsedSize > 0 )
        --m_UsedSize;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::iterator SortedList<T>::find( const T& item )
{
    iterator foundPos = std::lower_bound( m_Data, m_Data+m_UsedSize, item );
    if( foundPos == m_Data+m_UsedSize )
        return foundPos;
    if( *foundPos != item )
        foundPos = m_Data+m_UsedSize;
    return foundPos;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::clear()
{
    m_UsedSize = 0;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::resize( std::size_t size )
{
    T* temp = new T[size];
    if( m_UsedSize > size )
        m_UsedSize = size;
    for( std::size_t n = 0; n != m_UsedSize; ++n )
        temp[n] = m_Data[n];
    for( std::size_t n = m_UsedSize; n < size; ++n )
        temp[n] = T();
    if( m_Data )
        delete[] m_Data;
    m_Data = temp;
    m_AllocatedSize = size;
    m_UsedSize = size;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::iterator SortedList<T>::begin()
{
    return m_Data;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::const_iterator SortedList<T>::begin() const
{
    return m_Data;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::iterator SortedList<T>::end()
{
    return (m_Data+m_UsedSize);
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::const_iterator SortedList<T>::end() const
{
    return (m_Data+m_UsedSize);
}

// ----------------------------------------------------------------------------
template <class T>
std::size_t SortedList<T>::size()
{
    return m_UsedSize;
}

// ----------------------------------------------------------------------------
template <class T>
std::size_t SortedList<T>::allocatedSize()
{
    return m_AllocatedSize;
}

// ----------------------------------------------------------------------------
template <class T>
T& SortedList<T>::at( std::size_t index )
{
    if( index >= m_UsedSize )
    {
        std::stringstream ss; ss << "[SortedList::operator[]] Error: Index out of bounds: " << index << ", actual list size: " << m_UsedSize;
        throw Exception( ss.str() );
    }
    return m_Data[index];
}

// ----------------------------------------------------------------------------
template <class T>
const T& SortedList<T>::at( std::size_t index ) const
{
    if( index >= m_UsedSize )
    {
        std::stringstream ss; ss << "[SortedList::operator[]] Error: Index out of bounds: " << index << ", actual list size: " << m_UsedSize;
        throw Exception( ss.str() );
    }
    return m_Data[index];
}

// ----------------------------------------------------------------------------
template <class T>
const SortedList<T>& SortedList<T>::operator=( const SortedList<T>& that )
{
    if( this == &that )
        return *this;

    // don't re-allocate if size of "this" is equal or greater than "that"
    // just copy data across
    if( m_AllocatedSize >= that.m_AllocatedSize )
    {
        for( std::size_t n = 0; n != that.m_UsedSize; ++n )
            m_Data[n] = that.m_Data[n];

    // re-allocate and copy data across
    }else
    {
        T* temp = new T[that.m_UsedSize];
        for( std::size_t n = 0; n != that.m_UsedSize; ++n )
            temp[n] = that.m_Data[n];
        if( m_Data )
            delete[] m_Data;
        m_Data = temp;
        m_AllocatedSize = that.m_UsedSize;
    }
    m_UsedSize = that.m_UsedSize;

    return *this;
}

// ----------------------------------------------------------------------------
template <class T>
T& SortedList<T>::operator[]( std::size_t index )
{
#ifdef _DEBUG
    return this->at(index);
#else
    return m_Data[index];
#endif
}

// ----------------------------------------------------------------------------
template <class T>
const T& SortedList<T>::operator[]( std::size_t index ) const
{
#ifdef _DEBUG
    return this->at(index);
#else
    return m_Data[index];
#endif
}

} // namespace GOL

I'm trying, believe me, but it's kind of at random.

At this point, I recommend cloning it from the repository and seeing for yourself until I have some code to go with.

dependencies: googletest

tools: premake

The following will reproduce the crash:

$ git clone https://www.github.com/TheComet93/game-of-life.git
$ cd game-of-life
$ git checkout topic
$ premake gmake
$ cd build
$ make gol Tests
$ ./../bin/debug/Tests

Thank you very much for your time.

EDIT: If you're on windows, use "premake MinGW" instead of premake "gmake". The rest would be identical, if you're using CYGWin.

The fact that you use new and delete instead of placement new and manual destruction is something of a worry to me.

You aren’t manually enforcing that an object’s destructor is called exactly the same times as its constructor.

Without going over the code in excruciating detail, it may end up coincidentally that you do have a proper pairing of constructors and destructors and this may not be a problem (though it certainly is a performance issue), but there are 3 test cases you can create to test this.

Make a loop that runs for 10 minutes or so and inserts, erases—whatever else you want to test—random:

#1: PoD types such as integers.

#2: Basic classes that keep track of the number of times they are constructed and destructed.

#3: Complex classes that perform allocations and deletions as they are created and destroyed, as well as a memory fill on the allocated data and on a local array.

If it crashes on #1 then your implementation is simply flawed, but not necessarily by a pairing of constructors and destructors. You can print the last operation performed (insert, erase, whatever) to see which method to study. In fact you can add debug prints right now and run your application as it is and see what was the last thing to be called before death.

#2 allows you to verify the pairing of constructors and destructors. If this does not work, don’t bother with #3. Rewrite the whole thing using placement new and manual destructors. Actually, why bother testing? Just do it.

If #3 fails it is because #2 failed. Objects are not being constructed and destructed consistently and they themselves are causing the stack corruption as a result. Again, placement new and manual destruction, and enforce consistency.

L. Spiro

I tried what you said, but I still can't accurately reproduce the problem.

I have a few questions regarding placement new. Could someone answer questions #1 through #3 in this code?

#include <new>
#include <iostream>

class Foo
{
public:
    Foo() { std::cout << "constructed [" << this << "]" << std::endl; }
    ~Foo() { std::cout << "destructed [" << this << "]" << std::endl; }
};

template <class T>
void destroy( void* buf, T* obj, std::size_t size )
{
    for( std::size_t n = 0; n != size; ++n )
        (obj+n)->~T();
}

int main()
{
    void* buf = ::operator new (sizeof(Foo)*2); // #1 Does this allocate memory to
                                                      // fit 2 instantiations of the class Foo
                                                      // and is this correct?

    Foo* a = new(buf) Foo[2];
    destroy( buf, a, 2 );

    a = new(buf) Foo[3]; // #2 what happens now? The buffer is only size 2.
    destroy( buf, a, 3 );

    delete buf; // #3 Is this correct and safe?
                // deleting void* is undefined, isn't it?

    return 0;
}

Thanks for the reply! This is some cool stuff I didn't know about until now. :)

Don't use array placement new, you should use scalar placement new on each element by itself.

This doesn't seem to work for me. See the following code:

#include <iostream>
#include <new>

class Foo
{
public:
    Foo() { std::cout << "constructed " << this << std::endl; }
    ~Foo() { std::cout << "destructed " << this << std::endl; }
};

template <class T>
void destroy( T* obj )
{
    obj->~T();
}

int main()
{

    Foo* buf = (Foo*) ::operator new(sizeof(Foo)*2);

    Foo* a = new (buf) Foo();
    Foo* b = new (buf) Foo();

    destroy(a);
    destroy(b);

    ::operator delete( buf );

    return 0;

}

This is the output I gayt:

constructed 0x382fd8
constructed 0x382fd8
destructed 0x382fd8
destructed 0x382fd8

Process returned 0 (0x0) 

It's allocating the second object at the first address of the first object.

Do I need to do my own book keeping? I.e.

Foo* a = new (buf+0) Foo();
Foo* b = new (buf+1) Foo();

Ah, obvious. Thanks!