Quick question about memory allocation

high, i have a function which stores two char*, name and key, into a linked list. This is a different function, which creates the char[] and passes it onto the function which places it into a linked list. My question is if I want to delete name and key later on, will it work. Im thinking that once ive passed the pointer for the char[] to the linked list, how will the function from my linked list class know the size of the strings. Does it work any way, or is there another way to do it?

Code:

---

char* testname;
char* testkey;
testname = new char[32];
testkey = new char[16];

---

Quote:

---

My question is if I want to delete name and key later on, will it work.

---

Yes, if you use delete[].

Quote:

---

Im thinking that once ive passed the pointer for the char[] to the linked list, how will the function from my linked list class know the size of the strings.

---

With respect to delete[], I believe that this size tracking is done behind the scenes. However, with respect to actually using the string, you would need to keep track of the capacity yourself (and the size, if you are not using a null character to mark the end of the portion of the string in use). In fact, you should use std::string or at least some other dedicated string class instead of dealing with raw char*.

Yes, new actually saves the size of the allocated memory in a memory block to where you allocated memory. You can actually get the size with _msize (warning: platform dependant), so I'm guessing that's how delete [] keeps track of it.
Unless it's a class, delete [] works even on void* pointer.
Just be sure to use delete [] on arrays and delete on non-arrays. And yes, you're better off with a string class, such as std::string.

with delete [], what would be the syntax of that, is it delete [] testarr or delete testarr[]
im using char[] because im reading and writing memory to another program, and its just easier to have buffers with the bytes i need instead of having to go through a list of functions.

Code:

---

delete [] ptr;

---

With std::string, you can just call c_str() to get your C-style formated string to work with. As long as you let you string to the memory handling (resize, allocate, etc) you should be fine.

This discussion just touched an issue I'm contemplating.

First, I have an allocation that looks lite this:

Code:

---

ObjectType *mArray = (ObjectType *) new char[sizeof(ObjectType) * iInitialSize];

---

Later, I delete it:

Code:

---

delete[] mArray;

---

(I use char for allocation because I do not want any objects constructed yet.)

Does delete[] work as I want to in this case? I'm imagining that there could be a problem because I allocate by char, but try to delete the memory by an ObjectType*.

Yes, it works. You can even cast it to void* (because delete takes a parameter of type void* anyway) and it will still work.
However... It will not work on classes! When allocating and deleting classes, you must not change the type of the pointer.
And don't use char, use a C++ object instead. Want a string? Use std::string. Want a buffer? Use std::vector.

Thanks.

I'm writing a fast list-class with an array underneath and insertion and deletion in O(1). I'd use the stl vector otherwise.

Quote:

---

You can even cast it to void* and it will still work.

---

Perhaps, but it's still undefined behaviour. There is no situation where you may legally apply delete[] to a pointer of a type that is different from the dynamic type of the allocated array. There is only one such situation for normal delete, and that's when the static type is a base class of the dynamic type and the base has a virtual destructor.

Undefined, you say.

What if I do this:

Code:

---

delete[] (char *) mArray;

---

:D

> ObjectType *mArray = (ObjectType *) new char[sizeof(ObjectType) * iInitialSize];
That's just HORRIBLE.

What's wrong with
ObjectType *mArray = new ObjectType[iInitialSize];
- No casting
- No worrying about whether you got the right type in the sizeof
- The proper constructors get called.

Still undefined, unless you explicitly call the destructors.

If you just want a raw memory block to place objects in, don't use new. Use operator new:

Code:

---

void *memory = ::operator new(sizeof(T) * n);
for(int i = 0; i < n; ++i) {
  new (memory + i * sizeof(T)) T;
}
T *ar = static_cast<T*>(memory);

// ...

for(int i = n-1; i >= 0; --i) {
  ar[i].~T();
}
::operator delete(memory);

---

Quote:

---

Originally Posted by Araanor

Undefined, you say.

What if I do this:

Code:

---

delete[] (char *) mArray;

---

:D

---

Then combined with:
ObjectType *mArray = (ObjectType *) new char[sizeof(ObjectType) * iInitialSize];
You're hoping two wrongs make a right?

You should listen to Salem.

Quote:

---

I'm writing a fast list-class with an array underneath and insertion and deletion in O(1).

---

What, so that's just a linked list within a memory pool? Or are you storing items in order in memory contiguously and claiming that is O(1)?

Quote:

---

Originally Posted by Salem

> ObjectType *mArray = (ObjectType *) new char[sizeof(ObjectType) * iInitialSize];
That's just HORRIBLE.

---

Sure.

Quote:

---

What's wrong with
ObjectType *mArray = new ObjectType[iInitialSize];
- No casting
- No worrying about whether you got the right type in the sizeof
- The proper constructors get called.

---

Which is the problem, I just wanted a raw memory block.

Quote:

---

Originally Posted by CornedBee

Still undefined, unless you explicitly call the destructors.

---

Oh, the destructors, that's right... Always some detail.

Quote:

---

If you just want a raw memory block to place objects in, don't use new. Use operator new:

---

Thank you, that looks better. I just settled for char after reading a stray googled article on new which used char to demonstrate placement syntax.

Quote:

---

Originally Posted by iMalc

Then combined with:
ObjectType *mArray = (ObjectType *) new char[sizeof(ObjectType) * iInitialSize];
You're hoping two wrongs make a right?

You should listen to Salem.

What, so that's just a linked list within a memory pool? Or are you storing items in order in memory contiguously and claiming that is O(1)?

---

A linked list would imply links.

The class uses an array so the objects can be stored in sequence and not be fragmented across memory.
O(1) is achieved for insertion by inserting items at the end of the list.
O(1) is achieved for deletion by replacing the deleted item with the last one in the list.

This stuff with me looking to allocate memory without constructors and other fun headaches is just some smaller optimizations for the heck of it.

I'm going to assume that your program is finished, and that you've profiled the code with some real-world data to see where the real hot spots are, and found that this is indeed a problem.

You'll just love to hear that this is the first class I'm writing. :D

Right, some background then. I had a chat with a professional game developer some time back where he told me he sped up their game by 40% by replacing all linked lists with dynamic arrays. I was fascinated by the idea. See, I'm writing a small game now. Yes, yes, premature optimization is the devil. I just thought it'd be interesting.

Use std::vector instead. It's a dynamic array and can work as a buffer instead and you won't have to worry about allocating/deallocating data.
It's bad habit to actually do delete on pointers which you've changed their original type from (exception for polymorphism, if you use virtual destructors). And you really shouldn't have to change type. With templates in C++, you have a lot of power to keep the type all the time.

Remember, the best way to avoid memory errors is simply to delete what you get from new. Don't change pointer type and call delete.
If you keep that in mind, the compiler will do the rest.

That's good advice, but I wanted deletion in constant time.

I'll keep the original type of the pointers - I just thought of a new kludge instead! Which is:

Code:

---

union
{
        void *mMemory
        ObjectType *mObjects;
};

---

So allocation and deletion is done with mMemory, and objecty stuff is done with mObjects. It's the first time I found a use for unions! Go me.


Ah, right, I wanted to ask something too:

Quote:

---

Originally Posted by CornedBee

Code:

---

for(int i = n-1; i >= 0; --i) {
  ar[i].~T();

---

---

Any particular reason for going in the reverse direction? Well I guess objects are usually deleted in the reverse order of creation... Hm, I suppose that's reason enough.

Quote:

---

Use std::vector instead. It's a dynamic array and can work as a buffer instead and you won't have to worry about allocating/deallocating data.

---

I'm not sure I understand this correctly. I'm assuming you mean you don't have to concern yourself with the details of resizing the vector. If you store pointers to objects in the vector then you must call delete on those objects or your entire vector will leak memory.

Quote:

---

Right, some background then. I had a chat with a professional game developer some time back where he told me he sped up their game by 40% by replacing all linked lists with dynamic arrays.

---

This does not mean you will get the same speed increase. The results of that could change significantly if you do not have the exact same engine structure or app structure as the fella you talked to. Linked lists are fine if you use them correctly but will be slow if you try to do 50 inserts and removes in a frame. The fundamental idea is to use the right data structure for the job. At work if I went in and changed all our linked lists to arrays and claimed it was purely for a 40% speed increase I probably wouldn't be too popular. I would hold what the fella said in the context it was said in. It does not mean since he got those results in situation A that you will get the same results in situation B.

It is far simpler to rely on easy simple straightforward code that doesn't use magic tricks to get the job done. Magic tricks cause code to become obfuscated, hard to maintain, and very error-prone. And if you are doing all of this just to see if you get the same increase I hope you have a copy of Araxis merge or some other merge program that you can use to 'undo' your handy work.

Kludge is right, for it is an assumption on your part that all pointer types have the same representation. This is not guaranteed.
http://www.c-faq.com/null/machexamp.html

Basically, are you saying you are reinventing std::vector which already does almost exactly what you want so that you can have a different erase method?

I think there might be easier solutions, such as simply writing your special erase function for a vector. May-be something along these lines:

Code:

---

template <class T>
typename std::vector<T>::iterator
fast_erase(std::vector<T>& vec, typename std::vector<T>::iterator it)
{
    assert(it != vec.end());
    *it = *vec.rbegin();
    vec.pop_back();
    return it;
}

---

Possibly even faster, especially for member types like std::string:

Code:

---

template <typename T>
typename std::vector<T>::iterator
fast_erase(std::vector<T> &vec, typename std::vector<T>::iterator it)
{
  assert(it != vec.end());
  std::iter_swap(it, vec.rbegin());
  vec.pop_back();
  return it;
}

---

Quote:

---

Originally Posted by Araanor

A linked list would imply links.

The class uses an array so the objects can be stored in sequence and not be fragmented across memory.
O(1) is achieved for insertion by inserting items at the end of the list.
O(1) is achieved for deletion by replacing the deleted item with the last one in the list.

This stuff with me looking to allocate memory without constructors and other fun headaches is just some smaller optimizations for the heck of it.

---

Ah, in that case since order is obviously unimportant, the container interface is really that of an unordered set or unordered multiset. The difference being that e.g. an std::tr1::unordered_set has about constant time operations on insert, delete AND lookup, whereas you have O(n) lookup.
Well that can certainly be acceptable if you don't use lookup very often.

Quote:

---

Originally Posted by Araanor

That's good advice, but I wanted deletion in constant time.

I'll keep the original type of the pointers - I just thought of a new kludge instead! Which is:

Code:

---

union
{
        void *mMemory
        ObjectType *mObjects;
};

---

So allocation and deletion is done with mMemory, and objecty stuff is done with mObjects. It's the first time I found a use for unions! Go me.

---

Erm...
If anything, it should be the other way around. Allocate in mObjects and assign the address to mMemory later. Allocate and delete the same variable.
But all this is irrevant if you use std::vector.
All you can do is:

Code:

---

class MyClass
{
        int mem1;
        int mem2;
        float mem3;
        struct grr
        {
                UINT64 a, b, c;
        } grr;
};

        MyClass c1, c2, c3, c4;
        std::vector<MyClass> v;
        v.push_back(c1);
        v.push_back(c2);
        v.push_back(c3);
        v.push_back(c4);

---

This works just as well, and no memory leaks.

Quote:

---

Originally Posted by Araanor

A linked list would imply links.

The class uses an array so the objects can be stored in sequence and not be fragmented across memory.
O(1) is achieved for insertion by inserting items at the end of the list.
O(1) is achieved for deletion by replacing the deleted item with the last one in the list.

This stuff with me looking to allocate memory without constructors and other fun headaches is just some smaller optimizations for the heck of it.

---

Couldn't you just write a customer Allocator and pass that to std::list?
Although, I'd just go with std::vector until I had a valid reason not to.

Quote:

---

Originally Posted by Bubba

[snip]

---

You're right.

I realise the problems with messing around with memory management. If the class proves to be too much trouble, I'll eject it. But until then, I'll see it to a somewhat finished state.

Some more background: I've had a long break from programming. The main point of me programming right now is to get into the groove and improve my skills. I can afford trying magic tricks.

Quote:

---

Originally Posted by Salem

Kludge is right, for it is an assumption on your part that all pointer types have the same representation. This is not guaranteed.
http://www.c-faq.com/null/machexamp.html

---

Right, remembered this after a good night's sleep. But things should be fine if I have separate pointers for void *mMemory and Object *mObjects, right? Every time allocation is done to mMemory, mMemory is also cast into mObjects.

Quote:

---

Originally Posted by anon

Basically, are you saying you are reinventing std::vector which already does almost exactly what you want so that you can have a different erase method?

I think there might be easier solutions, such as simply writing your special erase function for a vector. May-be something along these lines:

---

That's a thought. Might be a very good tradeoff.

Quote:

---

Originally Posted by iMalc

Ah, in that case since order is obviously unimportant, the container interface is really that of an unordered set or unordered multiset. The difference being that e.g. an std::tr1::unordered_set has about constant time operations on insert, delete AND lookup, whereas you have O(n) lookup.
Well that can certainly be acceptable if you don't use lookup very often.

---

I suppose. Access will basically be "Loop through the list and update each element".
Is std::tr1::unordered_set some kind of hash table?

Quote:

---

Originally Posted by Elysia

Erm...
If anything, it should be the other way around. Allocate in mObjects and assign the address to mMemory later. Allocate and delete the same variable.

---

I'm not following you. I don't want to construct an entire array of objects prematurely.

Quote:

---

Originally Posted by cpjust

Couldn't you just write a customer Allocator and pass that to std::list?

---

Eh, well, not being familiar with allocators I wouldn't know.

Basically, if you want char, allocate a char array, then delete it.
If you want my_object, then allocate an array of my_object, then delete it.
Don't go allocating something and casting it to void*. You don't need to do ::operator new either if you just stick to your objects. Don't mess around with them - just use them as you would, without changing the type. Then delete will work just fine.

No, I don't want char. I don't even want an array of my_object. I want a region of memory where I can put my objects. CornedBee made a good post on how this is possible. I'd only be casting from void*, and only when new memory is allocated.

I understand that it would be faster to use swapping, if the swap function was more efficient than assignment.

However, the references say:

Quote:

---

A call to iter_swap() exchanges the values of two elements exactly as a call to swap( *a, *b );

The swap() function swaps the values of a and b.
swap() expects that its arguments will conform to the Assignable model; that is, they should have a copy constructor and work with the = operator. This function performs one copy and two assignments.

---

So, to gain anything from it I would have to overload the swap function for my type (and use using std::swap to make it choose the overload)?
However, then there would be unnecessary overhead for types that don't / cannot implement swap efficiently. Is there a way to make fast_erase choose swapping automatically if there is a swap method present for the type and use assignment otherwise?

Quote:

---

Originally Posted by anon

However, the references say:

---

True, for primitives it would be slower. Nor can the compiler optimize the difference away.

Quote:

---

So, to gain anything from it I would have to overload the swap function for my type (and use using std::swap to make it choose the overload)?

---

You gain if your element type has an efficient swap. The using declaration is not necessary, because iter_swap takes care of that. (You might want to use a using declaration for iter_swap, just in case you ever exchange the vector for something else.)

Quote:

---

However, then there would be unnecessary overhead for types that don't / cannot implement swap efficiently. Is there a way to make fast_erase choose swapping automatically if there is a swap method present for the type and use assignment otherwise?

---

Not until we get Concepts in C+++09.

Quote:

---

True, for primitives it would be slower. Nor can the compiler optimize the difference away.

---

And may-be large POD structs?

Quote:

---

You might want to use a using declaration for iter_swap, just in case you ever exchange the vector for something else.

---

This would be about random access containers? Others have their specific erase methods.

Quote:

---

Not until we get Concepts in C+++09.

---

So, until then I might just write two different erase functions, one using swap and other assignment, and leave it up to the user to choose the more efficient one.

Quote:

---

Originally Posted by Araanor

No, I don't want char. I don't even want an array of my_object. I want a region of memory where I can put my objects. CornedBee made a good post on how this is possible. I'd only be casting from void*, and only when new memory is allocated.

---

The point was, if you want char (which you don't), then you allocate

Code:

---

char* p = new char[num];
delete p;

---

If you want my_obj (which you don't), then you do:

Code:

---

my_obj* p = new my_obj[num];
delete p;

---

And if you simply want void* (which basically char* is the same as), you do:

Code:

---

void* p = ::operator new(size);
::operator delete(p);

---

The point is, you allocate and delete the memory with the same. You delete the same type. Don't allocate char and delete as void, or allocate my_obj and delete as char, or whatever. As long as you delete the original pointer (or another pointer, in either case, w/o changing the type), it works as intended.

But it's also silly to allocate memory of a different type than you want. You don't want to allocate char when you want my_obj, or vice versa. Char works fine as a contigous memory block (because it's 1 byte), but you can use the raw operator new for that, I guess.
Just so we're clear, yes?

Yes.


Here's how I do it now:

Code:

---

void *mMemory;
ObjectType *mObjectArray;
...
// Allocate memory
mMemory = ::operator new(sizeof(ObjectType) * iInitialSize);
mObjectArray = static_cast<ObjectType *> (mMemory);

...

// Destruct all objects in the list
for(int i = mObjectCount-1; i >= 0; --i)
        mObjectArray[i].~ObjectType();

// Free memory
::operator delete(mMemory);

...

// Construct/add the object to the list
new(mObjectArray + mObjectCount) ObjectType;
mObjectCount++;

---

If you want objects of type ObjectType*, then allocate them like so. Why not?

Code:

---

mObjectArray = new ObjectType[iIntialSize];

---

And also desutruct them with that type.
Don't allocate void* and cast to a class -- that's just prone to errors of all kinds.

You're walking a very dangerous route, and for what, may I ask?

You know, I thought I asked if it would work. Does the cast produce undefined behaviour?

No, it doesn't. That's pretty much how standard containers are implemented, except that the container never sees the void*. It simply stores a T*. The operator new allocation is then abstracted to the allocator system.

Ah, I see. Thank you.

What if you just allocate a raw chunk of memory, then use placement new inside that block of memory?
I've never had a need to use Allocators or Placement New, but it sounds like that's what you're really looking for.

Quote:

---

Originally Posted by Araanor

You know, I thought I asked if it would work. Does the cast produce undefined behaviour?

---

The thing is, that while it may work, it's not really C++ -- it's more like C. If you're going to have type safety, then why not use it? There's no need to use void in C++, since we have templates. Just use T and allocate that with new.
I don't really see why not? There's absolutely no reason (unless you're storing lots of different objects inside one container, in which case you need to be careful) not to.
I tried to do that once. It wasn't very flexible and you'll have to be able to remember the type or the user of the class has to cast it once it gets its pointer.
In either case, it is to be avoided, if possible.

So do answer, because I'm not really sure. Are you storing multiple objects in one container or just one?

Optimization. The class uses an array to store objects, I found this to be the most efficient and clean way to implement it.
The alternative would have been to do new ObjectType[someSize] when allocating. This would actually construct someSize objects before anything had been inserted into the list. Very ugly.

It's a template class. The template is for the type of object to be stored. No mixing of object types. Everything is encapsulated in the class. Code on the outside knows nothing of the implementation, it only sees a list which isn't very unlike a bare bones std::vector.

I see now... That makes it all clear.
I'm still not sure if a single array to hold all data is more efficient than simply creating objects on the fly, though. Maybe you should do a test. Otherwise there would be no point is doing it your way.
Anyway, it sounds like an interesting project, so good luck.

It's more efficient. Test the iteration and creation efficiency of a vector against a list, and you'll see.

I suppose that depends on the implentation.

No. There is no way to implement a linked list so that it is more efficient at bulk allocation and iteration than a properly implemented vector.

I disagree, but this isn't the place to discuss that.

I agree this is not the right thread.

I disagree that it's technically possible to add a large number of items to a linked list, no matter how well designed, compared to a vector that does block allocations. That's like saying "You can make a standard off-the-forecourt car go as fast as a dedicated race-car". Linked lists are good at certain things - like inserting or deleting single elements. But adding/deleting large numbers of elements is not one of the strengths of a linked list.

--
Mats

Quote:

---

Originally Posted by CornedBee

Code:

---

for(int i = n-1; i >= 0; --i)

---

---

This one puzzles me. Any particular reason you're using --i instead of i--? I can't make out any difference to a for-header.

Some kind of convention for reverse iteration?

Doesn't matter. It's a matter of style when using it there.

Quote:

---

Originally Posted by Araanor

This one puzzles me. Any particular reason you're using --i instead of i--? I can't make out any difference to a for-header.

Some kind of convention for reverse iteration?

---

I always use prefix instead of postfix operators unless I actually need the old value first.
Most compilers should optimize them both to the same thing, but I just think it's a good habit to get into.

Postfix increment/decrement are slower for custom objects, because they create a copy of the current object and return it by value, whereas prefix simply returns itself by reference.

For primitives, it makes no difference, but I like my programming style to not depend on the type of the variable I'm dealing with.

Quote:

---

Originally Posted by cpjust

Most compilers should optimize them both to the same thing, but I just think it's a good habit to get into.

---

The compiler can only optimize it away if the constructor for the type has no side effects. Yet another reason to strive for empty constructor bodies, IMHO.