[Lemon-user] [Lemon-devel] Array class proposal
Balázs Dezső
deba.mf at gmail.com
Thu Jul 26 20:20:58 CEST 2012
On Jul 26, 2012 6:43 PM, "Alpár Jüttner" <alpar at cs.elte.hu> wrote:
>
> Hi,
>
> > > * The way how the memory block is allocated is wrong. Sometimes
> > > (not always it crashes at the call of delete []. Does anyone
> > > know how to correctly allocate a memory block which is to be
> > > deallocated by delete []?
> > > An alternative is the use std::allocator<>, but it seems to
> > > increase the memory footprint a bit.
> >
> > I would use char array allocation and deallocation and call the
> > destructor of the items directly:
> > _array = reinterpret_cast<T*>(operator new char[size*sizeof(T)]);
> > delete[] reinterpret_cast<char*>(_array);
>
> Unfortunately is works only if T has a default constructor, so it is not
> an option.
Fix:
_array = reinterpret_cast<T*>(new char[size*sizeof(T)]);
I think, it should work, the variant implementation in LEMON works very
similarly. For which operation do you need the default constructor of T?
> > The problem is with your code that a normal p = new T[n] returns a
> > memory address for which
> > *(reinterpret_cast<int*>(reinterpret_cast<T>(p) - sizeof(T*))) == n
> > (it's not completely true for objects without destructor). So it
> > allocates more memory than you did, and stores the array size in the
> > first word - before the returned pointer. At the delete[] call, it
> > tries to find this size information, which is missing in your
> > implementation. Otherwise, the implementation can be compiler
> > dependent, that's way I would not depend on it, and i would use the
> > char* allocation.
>
> Alright, but how to allocate a memory block appropriate for delete[],
> then? C++ provides (user definable) 'operator new()' for allocating
> memory blocks to be deallocated by 'delete'. What is the array
> counterpart of this operator?
I think you can redefine new only if delete is redefined, as well. But the
default implementation is defined.
>
> > You need also handle exceptions in the constructors properly. If one
> > of them breaks, then you have to call the destructor of the already
> > constructed items, and then rethrow the exception.
>
> You are right, thank you.
>
> Alpar
>
>
> >
> > Balazs
> >
> > On Thu, Jul 26, 2012 at 4:06 PM, Alpár Jüttner <alpar at cs.elte.hu> wrote:
> > > Two caveats concerning the array implementation of the previous mail:
> > >
> > > * The declarations 'T1 t1' in the constructor parameter lists
> > > should be changed to 'T1 &t1' or 'const T1 &t1'. In fact, both
> > > versions should be implemented. Even worse, all possible
> > > combinations of const/non-const parameters should be
> > > implemented. Any idea how to do it correctly? Maybe a pair of
> > > recursive call of the constructor having one less parameters?
> > > * The way how the memory block is allocated is wrong. Sometimes
> > > (not always it crashes at the call of delete []. Does anyone
> > > know how to correctly allocate a memory block which is to be
> > > deallocated by delete []?
> > > An alternative is the use std::allocator<>, but it seems to
> > > increase the memory footprint a bit.
> > >
> > > Regards,
> > > Alpar
> > >
> > >
> > > On Thu, 2012-07-26 at 10:24 +0200, Alpár Jüttner wrote:
> > >> Hi,
> > >>
> > >> It is a common problem that one would like use an array of objects,
but
> > >> (s)he can't because the object either (a) not default constructible
or
> > >> (b) not copyable. Notably, it is a regular question from LEMON users
how
> > >> to create an array of NodeMap<>.
> > >>
> > >> If the object is at least default constructible, than you can use
> > >> new[]/delete[], otherwise (such as for NodeMap) the only reasonable
> > >> solution is using std::vector<Object *> and manually and individually
> > >> allocating/deleting the objects.
> > >>
> > >> Note, that even std::array introduced by C++11 fails to solve this
> > >> problem, for (1) its size is determined compile-time, and (2) does
not
> > >> resolve (a).
> > >>
> > >> Instead, I propose another Array implementation, please find the
> > >> prototype at the end of this mail.
> > >>
> > >> This is a fixed-size array, but the size is determined run time,
i.e. at
> > >> construction. Moreover, the objects in the array are constructed
using
> > >> the parameters passed to Array itself. Thus you can do this:
> > >>
> > >> ListDigraph g;
> > >> ListDigraph::Node n;
> > >> ...
> > >> int size = 12;
> > >> Array<ListDigraph::NodeMap<int> > map_array(size, g);
> > >> map_array[2][n]=5;
> > >> map_array[3][n]+=11;
> > >>
> > >> or even:
> > >>
> > >> Array<ListDigraph::NodeMap<bool> > map_array(size, g, true);
> > >> map_array[2][n]=false;
> > >>
> > >> What do you think of this idea? Does it worth including into LEMON?
> > >>
> > >> Plus a design question - do we need the _size member? Omitting it
would
> > >> be result in a narrower layer above the simple pointer it actually
> > >> wraps. On the other, it allows a more stl-like interface with size(),
> > >> iterators, begin(), end() etc. But to be honest, I see very little
use
> > >> of them here, except for size().
> > >>
> > >> Regards,
> > >> Alpar
> > >>
> > >>
> > >> // *****************************************************
> > >> // * Array class *
> > >> // *****************************************************
> > >>
> > >> template<class T >
> > >> class Array {
> > >> T * _array;
> > >> size_t _size;
> > >>
> > >> ///Copying is not allowed.
> > >> Array(const Array &);
> > >> ///Copying is not allowed.
> > >> Array &operator=(const Array &);
> > >>
> > >> public:
> > >> explicit Array(size_t size) : _array(new T[size]), _size(size) {}
> > >> template <class T1>
> > >> explicit Array(size_t size, T1 t1)
> > >> : _array( static_cast<T*>(operator new[] (size*sizeof(T)))),
> > >> _size(size)
> > >> {
> > >> for(size_t i=0;i<size;i++)
> > >> new (_array+i) T(t1);
> > >> }
> > >> template <class T1, class T2>
> > >> explicit Array(size_t size, T1 t1, T2 t2)
> > >> : _array( static_cast<T*>(operator new[] (size*sizeof(T)))),
> > >> _size(size)
> > >> {
> > >> for(size_t i=0;i<size;i++)
> > >> new (_array+i) T(t1,t2);
> > >> }
> > >> template <class T1, class T2, class T3>
> > >> explicit Array(size_t size, T1 t1, T2 t2, T3 t3)
> > >> : _array( static_cast<T*>(operator new[] (size*sizeof(T)))),
> > >> _size(size)
> > >> {
> > >> for(size_t i=0;i<size;i++)
> > >> new (_array+i) T(t1,t2,t3);
> > >> }
> > >> template <class T1, class T2, class T3, class T4>
> > >> explicit Array(size_t size, T1 t1, T2 t2, T3 t3, T4 t4)
> > >> : _array( static_cast<T*>(operator new[] (size*sizeof(T)))),
> > >> _size(size)
> > >> {
> > >> for(size_t i=0;i<size;i++)
> > >> new (_array+i) T(t1,t2,t3,t4);
> > >> }
> > >> template <class T1, class T2, class T3, class T4, class T5>
> > >> explicit Array(size_t size, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
> > >> : _array( static_cast<T*>(operator new[] (size*sizeof(T)))),
> > >> _size(size)
> > >> {
> > >> for(size_t i=0;i<size;i++)
> > >> new (_array+i) T(t1,t2,t3,t4,t5);
> > >> }
> > >>
> > >> ~Array() { delete [] _array; }
> > >> operator T* () { return _array; }
> > >> size_t size() { return _size; }
> > >> };
> > >> }
> > >>
> > >>
> > >> _______________________________________________
> > >> Lemon-devel mailing list
> > >> Lemon-devel at lemon.cs.elte.hu
> > >> http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel
> > >>
> > >>
> > >>
> > >> _______________________________________________
> > >> Lemon-user mailing list
> > >> Lemon-user at lemon.cs.elte.hu
> > >> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
> > >>
> > >
> > >
> > > _______________________________________________
> > > Lemon-user mailing list
> > > Lemon-user at lemon.cs.elte.hu
> > > http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
> >
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20120726/600166d1/attachment.html>
More information about the Lemon-user
mailing list