1

So I was debating on whether to use a dynamic array of Node* or std::vector<Node*> for an array in a program I was making. The program essentially tests STL sorting on a linked list (a custom made one), and therefore inserts each nodeptr from the LL into an array (dynamically allocated array or vector) and then calls std::sort on it. So when moving the pointers of the LL around after sorting the array, I initially used a vector to hold all of the nodes. But I realized that the vector gets destroyed via std::vector::~vector once out of scope. Which I believe is O(n) time according to cppreference:

std::vector::~vector() Destructs the vector. The destructors of the elements are called and the used storage is deallocated. Note, that if the elements are pointers, the pointed-to objects are not destroyed.

I believe the bolded section indicates O(n) time. So then I wondered if you could instead allocate a dynamic array to hold the nodes and then just delete the array after all of the sorting. (Whereas using ~vector(), you'd be iterating through the list twice; once during sorting, and a second time when freeing the array) Because if so, then you would subtract a whole O(n) operation from the code, which would be faster if possible.

Am I misunderstanding here, or would a regular dynamic array be faster because of this?

James Newman
  • 110
  • 8
  • Note the note about pointers. If the `vector` is storing linked list nodes, it'll probably be doing it via pointers to the nodes rather than copies of the nodes that have to be deleted. Still be O(N) either way, but destruction of a pointer's pretty much a no-op. – user4581301 Sep 02 '21 at 23:27
  • 2
    Please do clarify whether this is a `std::vector`. You talk about holding the nodes but I don't know whether you mean `std::vector`, and you talk about nodeptrs but I don't know if those are raw pointers or something else. Actually, just show some code. And don't be afraid of whitespace. – Useless Sep 02 '21 at 23:29
  • @user4581301 That's where I was confused. Does it recognize that the vector holds pointers and therefore doesn't call the deallocator on each of them? – James Newman Sep 02 '21 at 23:29
  • @Useless Ah yes sorry. It is `std::vector` – James Newman Sep 02 '21 at 23:30
  • 3
    It doesn't call any deallocator on anything directly except its single contiguous allocation. It calls _destructors_ on everything, but destroying a trivial type is a trivial no-op and probably optimized out. – Useless Sep 02 '21 at 23:31
  • @Useless Ah right. So then my understanding (that sorting and then cleaning up together with a vector is O(2n)) is wrong? – James Newman Sep 02 '21 at 23:33
  • "So then I wondered if you could instead allocate a dynamic array to hold the nodes and then just delete the array after all of the sorting." No, because *the code is broken* if the destructors don't get called. Aside from which, this would only in a big-O sense if you never do anything *else* with the vector that's O(N) or higher, which is clearly impossible since *creating* it is O(N). – Karl Knechtel Sep 02 '21 at 23:35
  • 1
    "my understanding (that sorting and then cleaning up together with a vector is O(2n)) is wrong?" It's wrong because *there is no such thing as "O(2n)"*. The entire point of big-O analysis is to drop the constant factors. After all, you could just move to a faster machine. – Karl Knechtel Sep 02 '21 at 23:37
  • @KarlKnechtel Wouldn't the destructors get called once the final scope is left? That's how I have it written anyway. And in this case, the vector's only purpose is to hold the node*s to be sorted and then the vector gets destroyed immediately after the pointers are adjusted accordingly. – James Newman Sep 02 '21 at 23:39
  • 3
    If the `vector` holds `Node*`s, it doesn't [own](https://stackoverflow.com/questions/49024982/what-is-ownership-of-resources-or-pointers) the allocations the `Node*`s point at. The `vector` will destroy its backing array, the array will destroy its contents, and its contents are dumb-stupid pointers that require no destruction effort. – user4581301 Sep 02 '21 at 23:47
  • Side note: sometime you'll see a hideous time complexity utterly crush a favourable one. O(1) means constant time, but that constant time could be 13.5 billion years. – user4581301 Sep 02 '21 at 23:49
  • It is relatively easy to detect at compile time that the destructor does nothing (for raw pointers) and thus you don't actually need to do the loop. Thus a std::vector on a normal good implementation is going to be just as fast as your hand coded version (the one thing it will be is much safer as we know there are no bugs in std::vector). https://lokiastari.com/blog/2016/03/19/vector-simple-optimizations/index.html – Martin York Sep 03 '21 at 00:05
  • @JamesNewman *or would a regular dynamic array be faster because of this?* -- What do you believe a `std::vector` is underneath the hood? It does the same operations that you would do if you coded your own dynamic array class. There isn't any magic going on in the vector class -- it is normal C++ code, yes, complex, but still C++ code. If you created your own dynamic array of type `T`, the destructors will be called when they're removed. That is the case regardless of whether it is std::vector or your own home-made dynamic array class. – PaulMcKenzie Sep 03 '21 at 01:48

3 Answers3

6

Yes, std::vector::~vector takes O(n) time, but so does delete[]ing a raw dynamically-allocated array.

Either data structure must destroy its contents, and the way to do that is to run each item's destructor. Of course, the destructor for a raw pointer is trivial, so its likely that no code will be emitted at all for destroying the pointers themselves no matter which container you use.

Miles Budnek
  • 28,216
  • 2
  • 35
  • 52
3

Raw pointers have no destructors and doing nothing N times takes no time. (C++ knows the type of the vector's elements at compile time.) So that part of std::vector's destructor isn't going to cost you anything.

C++ does not provide complexity guarantees for memory management, so actually freeing the storage used by the vector could take any amount of time. But the usual expectation is that the time to deallocate is more or less independent of the size of the block being deallocated. In any case, it won't be any different between a vector and an array.

rici
  • 234,347
  • 28
  • 237
  • 341
1

The description at cppreference (like the standard) doesn't provide complexity guarantees for the destructor of std::vector but allows estimating worst-case (or best-case in some cases) execution times. It is necessary to make a few assumptions though (i.e. describe particular cases of interest).

If n is the number of elements and the element type has a destructor, then there will be n calls of the destructor. The complexity of that will therefore be O(n)*O(d) or to O(n*d) where O(d) describes the complexity of the destructor call of the element.

That will represent a worst-case complexity for std::vector (destroying the elements) in general.

For types with no destructor (int, raw pointers, etc) there is nothing preventing the implementation from recognising that the destruction of an element is a non-op, and therefore not implementing a loop that executes the destructor for each element. In that case, the destruction of elements may be reduced to nothing or (in complexity terms O(1)). That represents a best case complexity for destruction of elements.

The other part of the destructor of std::vector is releasing the storage used by the elements (i.e. the raw memory). That will only happen once, but the time will be implementation-defined. Practically, some implementations may do it in constant time (e.g. a fixed number of operations independently of the size of the raw memory) or in linear time (the time to release a chunk of memory proportional to the size of that memory). That suggests a WCET complexity of O(c), where c is the capacity of the vector, not the size. A best case would (assuming deallocation is constant time) be O(1). [It's also not impossible that some implementations may be worse than that - but I'll leave that alone].

The implementation is free to do other things on deallocation that may affect execution time. For example, a security-focused implementation may implement a loop that overwrites each byte three times before releasing it, in which WCET complexity would be O(c). Equally, such an implementation may use some way to do that overwriting in constant time.

It's then possible to work out complexity for particular cases. For example.

Assuming release of storage (raw memory) is a constant time operation, the elements don't have a destructor, and the implementation is optimised for that case, the WCET complexity of vectors destructor will be O(1).

Assuming release of storage (raw memory) is a constant time operation, and elements are destructed in a loop by calling their destructor, that capacity of the vector and its size are equal, then WCET complexity of vectors destructor will be O(n*d) where d describes complexity of the elements's constructor. If destruction of an element is a constant-time operation, this means complexity of O(n).

Peter
  • 35,646
  • 4
  • 32
  • 74