Array kept contiguous by swapping with the last element

Question

I made a class that encapsulates the common pattern of keeping an array contiguous when an element is removed by swapping the last element into its place.

A few specific things I'm wondering about:

Is it unsafe for non-POD types (because of the memcpy)?
Is there a more efficient way to add a new object (so it doesn't have to be copied)?
Should I worry about code bloat from capacity being a template parameter (N)?

This was not written with C++11 in mind, except for a few little features supported by Visual Studio 2010 (like auto).

Edit for clarification: I'm using aligned memory instead of a simple array of T so that I have control over when the objects in the array are created and destroyed. I'm using a memcpy to avoid calling a constructor every time something is swapped.

SwapArray.h:

#ifndef INCLUDE_GUARD_78F4FE5C_3E57_44C4_9E42_2574051D5A18
#define INCLUDE_GUARD_78F4FE5C_3E57_44C4_9E42_2574051D5A18


#include <boost/type_traits/alignment_of.hpp>
#include <boost/type_traits/aligned_storage.hpp>


namespace ktc
{


// an array that keeps all its elements contiguous by swapping removed elements
// with the last element of the array.
//
// add and remove are both O(1).
template <typename T, unsigned int N>
class SwapArray
{
    public:

        SwapArray();
        ~SwapArray();

        // number of elements currently in the array.
        unsigned int size() const;
        // max size.
        unsigned int capacity() const;

        // add a value to the end.
        void add( const T& val );
        // remove the value at this index.
        void rem( unsigned int i );

        // remove all.
        void clear();

        T& operator[]( unsigned int i );
        const T& operator[]( unsigned int i ) const;

        template <typename Compare>
        void sort( Compare compare );

    private:

        typedef
            typename boost::aligned_storage
            <   N * sizeof(T),
                boost::alignment_of<T>::value
            >::type
            AlignedMem;

        // aligned for type T.
        AlignedMem m_alignedMem;

        unsigned int m_size;

        // return the data for the i-th element.
        char* memAt( unsigned int i );
        const char* memAt( unsigned int i ) const;
};


} // namespace ktc


#include "SwapArray.hpp"


#endif

SwapArray.hpp:

#include <algorithm>
#include <cstdio>
#include <new>

#include "ktcAssert.h"


namespace ktc
{


template <typename T, unsigned int N>
SwapArray<T,N>::SwapArray()
{
    static_assert( N > 0, "SwapArray can't have capacity 0" );

    m_size = 0;
}


template <typename T, unsigned int N>
SwapArray<T,N>::~SwapArray()
{
    clear();
}


template <typename T, unsigned int N>
void SwapArray<T,N>::clear()
{
    for( unsigned int i = 0; i < m_size; i++ )
        (*this)[i].~T();

    m_size = 0;
}


template <typename T, unsigned int N>
unsigned int SwapArray<T,N>::size() const
{
    return m_size;
}


template <typename T, unsigned int N>
unsigned int SwapArray<T,N>::capacity() const
{
    return N;
}


template <typename T, unsigned int N>
void SwapArray<T,N>::add( const T& val )
{
    ktcAssert( m_size < N );

    // copy it onto the end.
    new( memAt(m_size) ) T(val);
    m_size++;
}


template <typename T, unsigned int N>
void SwapArray<T,N>::rem( unsigned int i )
{
    ktcAssert( m_size > 0 );
    ktcAssert( i < m_size );

    // remove the element.
    char* r = memAt(i);
    T* rt = (T*) (r);
    rt->~T();

    // if it wasn't the last element that was removed, swap the last element
    // into its spot.
    if( i < m_size - 1 )
    {
        char* last = memAt( m_size - 1 );
        ktcAssert( last != r );
        memcpy( r, last, sizeof(T) );
    }

    m_size--;
}


template <typename T, unsigned int N>
T& SwapArray<T,N>::operator[]( unsigned int i )
{
    const auto* ct = static_cast<const SwapArray<T,N>*>( this );
    return const_cast<T&>( ct->operator[](i) );
}

template <typename T, unsigned int N>
const T& SwapArray<T,N>::operator[]( unsigned int i ) const
{
    ktcAssert( i < m_size );
    return *( (T*) memAt(i) );
}


template <typename T, unsigned int N>
char* SwapArray<T,N>::memAt( unsigned int i )
{
    auto ct = static_cast<const SwapArray<T,N>*> (this);
    return const_cast<char*> ( ct->memAt(i) );
}

template <typename T, unsigned int N>
const char* SwapArray<T,N>::memAt(unsigned int i) const
{
    ktcAssert( i < N );
    return static_cast<const char*>( m_alignedMem.address() ) + (i * sizeof(T));
}


template <typename T, unsigned int N>
template <typename Compare>
void SwapArray<T,N>::sort( Compare compare )
{
    if( size() < 2 )
        return;

    std::sort( &(*this)[0], &(*this)[size() - 1], compare );
}


} // namespace ktc

Yuushi · Accepted Answer · 2014-09-11 02:16:09Z

Firstly, to answer your questions:

Yes. memcpy makes this inherently unsafe for anything that isn't trivially copyable (which can be deduced using std::is_trivially_copyable, although this is part of C++11). Generally std::copy will use tag and will invoke memcpy when it is able to. You should always use std::copy over memcpy in C++.
Yes, by having a variant of your add function that takes an rvalue reference and invoking std::move on the value you get:

void add(T&& val)
No. See here for the specifics.

The main question I have with this class is why go through all the effort of using boost::aligned_storage for this? Using a simple std::array<T, N> (or even just T[N]) would simplify things, and the only cost you would incur is the initial default constructor calls. Given that your class isn't safe for non-trivial types anyway, the performance difference between the two is going to be something close to 0. Also, although you're calling destructors on elements that have been removed, this is only destroying the object, and not reclaiming any of the memory.

Using a std::array, you could do this without a lot of the mucking around that you have to do with ugly casts back and forth between char* and T*, without having to use placement new, and without having to manually call ~T.

Edit: As per the C++ standard:

§ 3.9.2

For any object (other than a base-class subobject) of trivially copyable type T, whether or not the object holds a valid value of type T, the underlying bytes (1.7) making up the object can be copied into an array of char or unsigned char. If the content of the array of char or unsigned char is copied back into the object, the object shall subsequently hold its original value.

The reason it is unsafe is due to the fact that it does a bit-for-bit copy of the original. If the original holds any memory allocated with new, then it will only get a copy of that pointer, and not the original - much like leaving the default copy-constructor default when you have new'ed memory is a bad idea. In this case it is even more dangerous, however. If you have a std::string as a member variable, for example, as long as that string is stack-allocated, then the default copy constructor will call the copy constructor for std::string and all will be well. This does not hold for memcpy - it will only get a copy of the pointer that the string points to, so when the original goes out of scope, you're going to get undefined behavior.

I edited my question to address your question. Also, can you explain why memcpy is unsafe here? What exactly would go wrong with an object that isn't trivially copyable? I certainly wouldn't want to use std::copy, since the point is to move, not duplicate. Also, I'm not sure what you mean about "calling destructors on elements that are out of bounds...". — KTC, Sep 11 '14 at 0:29
@KTC Sorry, I reworded the "out of bounds" part, I meant to say elements that have been removed. memcpy is unsafe as defined by the C++ standard. See my edit. — Yuushi, Sep 11 '14 at 2:09
About your edit: I'm aware of the difference between a shallow copy and a deep copy as you described, but I don't see how that's relevant to my specific case. Is there some other hidden danger you haven't mentioned? — KTC, Sep 11 '14 at 3:13
@KTC In what way is it not applicable to your case? If you're trying to store anything that isn't POD (so anything for your type T that isn't trivial), you're hitting undefined behavior. That seems pretty relevant to me. — Yuushi, Sep 11 '14 at 3:42
If there's undefined behavior, please explain why. Your example situation is different than what happens in my code (the copy source doesn't go out of scope; it becomes a bunch of unused bytes past the end of the array). Your quote from the standard says memcpy is safe for trivial types, but doesn't say anything about non-trivial types either way. — KTC, Sep 11 '14 at 3:50

firda · Answer 2 · 2014-09-11 18:35:19Z

No need to rewrite what Yuushi already mentioned, so, I will add few observations:

You seem to be creating something like boost::static_vector with one exception: your rem (remove) is like swap(at(i), back()); pop_back() - which is faster than simple erase(), but will reorder items.

I suppose that you want your objects destroyed immediatelly, therefore std::array<T,N> would not be an option.

I have only one objection about the code:

template <typename T, unsigned int N>
char* SwapArray<T,N>::memAt( unsigned int i )
{
    auto ct = static_cast<const SwapArray<T,N>*> (this);
    return const_cast<char*> ( ct->memAt(i) );
}

template <typename T, unsigned int N>
const char* SwapArray<T,N>::memAt(unsigned int i) const
{
    ktcAssert( i < N );
    return static_cast<const char*>( m_alignedMem.address() ) + (i * sizeof(T));
}

This const_cast pattern can be seen everywhere. I understand that it could be good not to duplicate big code, but in this case (when it is quite short), copy-pasting two lines and adapting would be better. I would not use const_cast here.

It is getting too long there in comments, so, I will try to give one example against the memcpy:

class example {
    int first;
    int second;
    int *which;
public:
    example(): first(1), second(2) { which = &first; }
    example(const example& src): first(src.first), second(src.second) {
        which = src.which == &src.first ? &first : &second; }
};

Now we have class that will work in std::vector but your memcpy will break it.

I see your point with the const_cast thing. I guess I just wanted to try it out since I've never used it before. And, yeah, maybe I'll just go with boost::static_vector if my version turns out not to be safe. — KTC, Sep 11 '14 at 0:34
Can't argue with that example. I accepted the other answer, though it's not complete without yours. — KTC, Sep 12 '14 at 2:10

asked	4 months ago
viewed	143 times
active	4 months ago

current community

your communities

more stack exchange communities

Array kept contiguous by swapping with the last element

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ array or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Array kept contiguous by swapping with the last element

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ array or ask your own question.

Related

Hot Network Questions