7

Yes, another realloc vs. std::vector question. I know what you're going to say, and I agree, forget manual memory allocation, and just use a std::vector. Well unfortunately my professor has forbidden me to use anything from the STL for this assignment.

So yeah, I have a dynamic array of T and I need it to be resizable, and I can't use std::vector. I could return to the dark ages and do the whole thing with malloc and family, but if I could use new that would be totally awesome.

I've read plenty of threads where everyone said "no, you can't do it, use std::vector", but they were all posted before August 2011, and I'm hoping against hope that something might have changed since the dawn of C++11. So tell me, am I in luck, or do I have to revert to C style memory allocation?

Xeo
  • 129,499
  • 52
  • 291
  • 397
Michael Dorst
  • 8,210
  • 11
  • 44
  • 71
  • [The homework tag is deprecated](http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated). – jogojapan Feb 25 '13 at 06:05
  • You can.. (god forbid) use realloc in C++ if you want. – Rapptz Feb 25 '13 at 06:05
  • 8
    "Well unfortunately my professor has forbidden me to use anything from the STL for this assignment." - That's no problem, `std::vector` is not in the STL, it's in the C++ standard library. –  Feb 25 '13 at 06:07
  • 1
    @Rapptz: You can't if you want your code to actually work. – Nicol Bolas Feb 25 '13 at 06:07
  • `std::vector` is written in C++ without using `std::vector`, so it must be possible :) give it a shot. I believe what people in the threads meant to say is "no you SHOULDNT do it .." – Karthik T Feb 25 '13 at 06:09
  • realloc is new followed by a copy – perreal Feb 25 '13 at 06:10
  • @perreal You mean it's _malloc_ followed by a copy? – jogojapan Feb 25 '13 at 06:10
  • @H2CO3 are you sure? I've always been a little bit fuzzy on exactly what is and what isn't part of the STL. – Michael Dorst Feb 25 '13 at 06:11
  • I mean new as in `new int[55]` – perreal Feb 25 '13 at 06:11
  • @perreal realloc is like malloc followed by a memcpy. That is not quite the same as what C++ calls a copy. – R. Martinho Fernandes Feb 25 '13 at 06:11
  • 4
    @MichaelDorst what H2CO3 is reffering to, is the fact that STL is an old name of an outdated 3rd party library, and nowadays what is mistakenly reffered to as STL is all part of the standard library of C++. Check out [What's this STL vs. "C++ Standard Library" fight all about?](http://stackoverflow.com/a/5205571) if you are interested.. – Karthik T Feb 25 '13 at 06:12
  • 2
    @perreal you mean `malloc` followed by a copy, and sometimes it is, but if there is room, `realloc` will not copy, it will simply allocate more space. – Michael Dorst Feb 25 '13 at 06:13
  • 1
    @jogojapan whatever you're trying to tell me sounds promising, could you post an answer where you go into more detail? – Michael Dorst Feb 25 '13 at 06:18
  • 1
    @jogojapan using realloc upon non-trivially-copyable objects will result in undefined behaviour the moment a reallocation is actually required. – R. Martinho Fernandes Feb 25 '13 at 06:19
  • @R.MartinhoFernandes True. Forget what I said. – jogojapan Feb 25 '13 at 06:20
  • @MichaelDorst: H2CO3 was just being a smart aleck, ignore what he said. – user541686 Feb 25 '13 at 06:21
  • Don't allocators have the concept of hints? I assume that this may be used for reallocation, but I've never used it myself. However, vector (which you should just reimplement btw) is generally designed to minimise reallocation by doubling the allocation when it runs out of space. – Alex Chamberlain Feb 25 '13 at 06:30
  • `std::vector` *is* the `realloc` of C++. There's no other. If you cannot use it, well, that's unfortunate. Do your own allocate-and-copy. – n. m. could be an AI Feb 25 '13 at 06:31

2 Answers2

11

You should avoid realloc completely anyway, because you can't move around C++ objects like that.

  • Use buf = new unsigned char[sizeof(T) * capacity] to create a new buffer
  • Cast the allocated unsigned char * to T * and use these T-pointers from now on
  • Construct new elements via "placement new", as in new (&buf[i]) T(original_copy)
  • To copy the buffer to a larger buffer, allocate the new one first, use std::uninitialized_copy (not std::copy), then destroy the elements in the old one using buf[i].~T() and deallocate the old buffer using delete [] buf.

All of this is assuming you don't have to worry about exception-safety, which is probably OK for the assignment.
Just be aware that in real-world code you'd have to guarantee exception safety and it's a lot more tedious than this.

user541686
  • 205,094
  • 128
  • 528
  • 886
  • 3
    Bad! Use `static_cast(::operator new(sizeof(T) * cap))` to get memory, if anything. Then use placement new to stick things in there. This way, you can use normal pointer arithmetic to mark your first, last and end. I'd even say this overcomplicates things for an assignment and would just do a straight `new T[capacity]` and require default constructability. – Xeo Feb 25 '13 at 06:41
  • @Xeo: I don't get it, why is `new unsigned char[]` bad, and how is `::operator new()` better? Regarding default-constructability: if he goes that route then he also needs to use `std::copy`. – user541686 Feb 25 '13 at 06:52
  • 2
    The idea is that you have explicitly typed memory. – Xeo Feb 25 '13 at 07:01
  • @Xeo: Could you elaborate? I'm not sure what you mean. Isn't everything explicitly typed in my case too? – user541686 Feb 25 '13 at 07:06
  • Not really, since you just have an `unsigned char*`. If you have a `T*` buffer, you can conveniently use three `T*` - `first`, pointing to the beginning of the buffer, `last`, pointing to one-pase-the-end of the sequence, and `end`, pointing to the end of the capacity. With those typed pointers, you can simply do pointer arithmetic, without casting or much to get wrong. But as I said, a simple `new T[N]` should suffice for a simple assignment. – Xeo Feb 25 '13 at 07:10
  • @Xeo: Oh, I see why my answer confused you -- I didn't mean he should be performing the cast *every time* when accessing the elements, I just meant that he shouldn't forget to cast it before ever accessing them. He would indeed store 3 pointers which were casted from `unsigned char *` originally, but the pointers would be `T *`, which I believe is the same as what you intended. I'll clarify it in my post. – user541686 Feb 25 '13 at 07:22
  • 2
    Re " you can't move around C++ objects like that", well, although std::vector can't be made to use realloc in general, it does exactly move around C++ objects like that. The problem isn't with realloc, but with the container design (which requires simple standard allocators). `realloc` would provide a very nice performance boost for a *suitable container*, no problem (greater than the implementation problem of `std::vector`, that is). – Cheers and hth. - Alf Aug 11 '15 at 09:26
8

The problem with realloc is that is may move the existing data to a different range of contiguous addresses. Should it need to do so, given it's a C function the data is copied without any nod to C++ object lifetime:

  • copy/move constructors aren't used
  • destructors aren't invoked afterwards for the source objects

This can cause fatal consequences - for example, when the objects being moved contain pointers/references that remain pointing at addresses in the memory area being vacated.

Sadly, normal malloc implementations don't allow a callback hook allowing you to replace the memory-content-copying code with your own C++-safe implementation. If you're determined you could try to find a more flexible "malloc" library, but it's unlikely to be worth the hassle and risk.

Consequently, in the general case you should use new to change your capacity, copy/move each object, and delete the originals afterwards.

If you're certain your data is simple enough that a memcpy-style relocation won't cause adverse consequences, then you can use realloc (at your own risk).

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252