3

I have just started with my Data Structures and I am implementing some sort of arrayed list (~=std::vector). I was wondering how is pop_back() implemented so that it has constant complexity? It has to reduce the size by 1 and delete the last element. Now I saw somewhere that it basically reduces the size by 1 and destroys last element via some iterator/pointer, but then why couldn't we implement pop_front() the same way and just redirect our pointer to first element to the next one?

template <typename T>
ArrayList<T>& ArrayList<T>::pop_back()
{
    --size_;
    auto p = new T[size_];
    std::copy(elements_,elements_+size_,p);
    delete [] elements_;   //elements_ being my pointer
    elements_ = p;
    return *this;
}
Improve this question
6
  • Is your question about pop_back() or pop_front()? Commented Mar 24, 2020 at 15:03
  • For pop_back() you don't actually have to delete/destroy that last element. You can just decrement the pointer to the last element of your array or decrement the size member (depends how you implemented this). In order to pop_front() you would still decrement size, but now you have to shift your elements towards the front, or increment your front pointer. Again depends on your impelementation. The point is you dont have to go out of your way to delete the element. Just stop using the element. Commented Mar 24, 2020 at 15:04
  • FWIW, I read an article a few months back about a data structure like vector that grows from the middle, enabling fast front operations as well, but the name escapes me. In that case, you can implement pop_front in roughly the same way. Commented Mar 24, 2020 at 15:09
  • @LLSv2.0 pop_back() certainly does have to destroy the last element. If that element has a destructor it's required that the destructor runs and that the element's lifetime ends. Commented Mar 24, 2020 at 15:11
  • 1
    @chris Well there is std::deque. It's not contiguous like a vector but has random access and fast inserts/deletes from the front and back. Commented Mar 24, 2020 at 15:12

4 Answers 4

Reset to default
5

That's not how pop_back() is typically implemented. While it is an implementation detail, typically your list/vector/dynamic array would keep track of two sizes: one the actual size of the list and the other the capacity. The capacity is the size of the underlying allocated memory. Now pop_back() simply decreases size by 1 and runs destructor on the last element (do not confuse the destruction, i.e. call to ~T() method with delete operator). It doesn't relocate anything. Capacity stays the same. The entire operation does not depend on the size of the list (unlike your implementation).

Note that you cannot do the same with pop_front() in an easy way. You would have to track both the begining and the end of the list plus the underlying memory (and depending on approach: either store size and capacity or calculate them at runtime). Which requires more memory and potentially more cpu operations. And also such structure becomes weird. You know capacity, you know size, but you actually don't know how many push_back() you can do before resize happens (you only know that the number is bounded by "capacity minus size", but it can be smaller). Unless you add this information to your structure, which again either eats memory or cpu.

Side note: If you are going to take raw destructors way, then do not use delete[] operator at all. The delete operation is pretty much "call destructors + deallocate memory". And so if you manually destruct, then an additional call to delete[] will lead to the undefined behaviour. Unless you actually allocate char memory (regardless of T) and use placement new (which also requires some manual size and offset calculations). And this is a good way of implementing such vector, although extra care is required (manual memory tracking is a b***h).

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

In OPs implementation, calling ~T() explicitly on the last element will lead to problems when they finally delete[] the underlying memory and ~T() is called again on all those elements, if T is a class type and not an int or something.
@JohnFilleau I did not intend to suggest that. I've updated the answer.
"And also such structure becomes weird. You know capacity, you know size, but you actually don't know how many push_back() you can do before resize happens." Can you please elaborate on this? From what I understood, then pop_front() could also easily work by destroying that element and leaving the memory allocated in case we do push_front(). Also if we have a pointer to the start of a list then isn't getting first and last elements as simple as dereferencing pointer and/or pointer+size?
Also I have capacity as one of my class members which is used for allocating new (2* current) chunks of memory whenever size reaches it, so makes.me wonder wouldn't currentSize - currentCapacity give us info on how many pushbacks we can have?
@ZlatanRadovanovic if you move pointers from both sides than no. Consider capacity 5. You do 2 push_back() and 2 pop_front(). Now your size is 0. But the begining moved to index 2. Meaning you can only do 3 push_back() before resize. Even though capacity-size is 5.
3

The reason you're having trouble implementing pop_back() with O(1) complexity is that by using new[] and delete[], you have tied together the lifetime of your contained objects with the storage of your objects. What I mean by that is that when you create a raw dynamically allocated array using new T[n];, two things happen: 1) storage is allocated and 2) objects are constructed in that storage. Conversely, delete[] will first destroy all objects (call their destructors) and then release the underlying memory back to the system.

C++ does provide ways to separately deal with storage and lifetimes. The main things involved here are raw storage, placement new, pointer casts, and headaches.

In your pop_back() function, it appears you want to be able to destroy just one object in the array without destroying all other objects or releasing their storage. Unfortunately, this is not possible using new[] and delete[]. The way that std::vector and some other containers work around this is by using lower-level language features. Typically, this is done by allocating a contiguous region of raw memory (typed as unsigned char or std::byte, or using helpers like std::aligned_storage), doing a ton of book-keeping and safety checks and extra work, and then using placement new to construct an object in that raw memory. To access the object, you would compute offsets into the (array of) raw memory and use a reinterpret_cast to yield a pointer to the object you've placed there. This also requires explicitly calling the destructor of the object. Working at this low level, literally every detail of the object's lifetime is in your hands and it is very tedious and error-prone. I do not recommend doing it. But it is possible and it allows std::vector::pop_back() to be implemented in O(1) complexity (and without invalidating iterators to previous elements).

Improve this answer

7 Comments

You don't reinterpret_cast raw memory to get object pointers. Placement new already returns a proper valid pointer to the created object.
Managing the raw memory isn't actually very hard. Basically all of the extra work is done to make sure the memory is aligned and safe is done at compile time. As an example you can look at std::aligned_storage. You do have to be a bit more careful with the rule of 3/5/0 however.
@FrançoisAndrieux yes, but supposing that an implementation of vector stores only a pointer to an array of std::byte or std::aligned_storage, how would you get a pointer to the i'th element in that array?
And I agree that it isn't that hard once you know what you're doing. If somebody who has just learned new[] and delete[] tries to do this sort of stuff by trial and error, it will be a disaster.
No; to clarify, when I do this sort of thing, my code is 70% asserts and static_asserts, because this amount of low-level control makes me paranoid.
|
1

When you pop_back on a standard vector you don't actually release the associated memory. Only the last element is destroyed, the size is reduced but capacity is not. No other element is copied or moved. This is hard to replicate with custom containers because you can't delete or destroy single element of an array.

For this reason std::vector<T> doesn't actually use an array of T. It allocate raw uninitialized memory (something like std::aligned_storage) and performs placement new to create elements in that allocation as needed. Placement new is a version of new that does not allocate but instead is given a pointer where it should construct the object. This means that the lifetime of the object is not directly associated with it's allocation and uniquely allows you to destroy elements individually without freeing it's underlying memory by calling it's destructor. Internally, it would look something like pop_back() { back().~T(); --size; }.

Improve this answer

2 Comments

Why can't I delete e.g last element of my array by explicitly calling it's destructor? Similarly as to what you wrote at the end of your answer?
If you do, when you eventually delete[] the array at the end of the container's lifetime or to grow it will call that destructor again. What I wrote only work if your elements used placement new.
0

I was wondering how is pop_back() implemented so that it has constant complexity? It has to reduce the size by 1 and delete the last element.

Exactly. That's all it has to do. No matter how many elements you have in total.

That's the definition of constant complexity.

Now I saw somewhere that it basically reduces the size by 1 and destroys last element via some iterator/pointer

That's right. The memory is still allocated, but the object living there undergoes logical destruction.

but then why couldn't we implement pop_front() the same way and just redirect our pointer to first element to the next one?

You could! That's how std::deque works, which is why std::deque has a pop_front() with constant complexity.

However, you can't do it while maintaining other cheap operations, because it necessarily causes memory fragmentation after a few times. Memory is allocated in chunks, and vectors need to be allocated in contiguous chunks. Imagine that vectors just "ignored" the first element if you pop_front()'d it — now do that five hundred times. You have unused memory just sitting there forever. Not good! And what if you want to add to the front now? Eventually, unless you want to end up using infinite memory, you'd have to split your memory up into distinct chunks, but that breaks the contiguity guaranteed.

Other containers are designed to give you what you want, but with trade-offs. In particular, std::deque cannot guarantee you contiguous storage. That's how it prevents leaving loads of unused memory lying around all the time.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.