JuniorCodeCommonNot answered yet
Implement a minimal vector<T> with push_back, push_front, pop_back, pop_front, size, clear
Implement a simplified Vector<T> that owns a heap-allocated buffer, with push_back, push_front, pop_back, pop_front, operator[], size, and clear.
Requirements:
(Rule of Five).
push_backamortised O(1) (grow by doubling capacity when full).push_front/pop_frontare O(n) (shift elements).- The class owns a resource — provide correct copy, move, and destructor
template<typename T>
class Vector {
public:
void push_back(const T& val);
void push_front(const T& val);
void pop_back();
void pop_front();
T& operator[](size_t i);
size_t size() const;
void clear();
// your code here
};Write the implementation.
A vector owns a heap-allocated array, a size (used elements), and a capacity (allocated slots). push_back amortises O(1) by doubling capacity when full. push_front is O(n) as it must shift all elements. Proper copy/move semantics and destructor are required for correctness (Rule of Five).
- ✗Using
new T[n]which default-initialises all elements — prefer raw memory + placement new for efficiency - ✗Forgetting to call destructors on existing elements before
clear()for non-trivial T - ✗Growing by 1 instead of doubling — leads to O(n²) total push_back cost
- →Why does
std::vectoruse capacity doubling and not tripling or fixed increment? - →How would you implement
insertat an arbitrary position efficiently?
Contents
Task
Implement a simplified Vector<T> with push_back, push_front, pop_back, pop_front, operator[], size, clear. Apply the Rule of Five.
Key points
push_front/pop_frontare O(n) for a vector — usestd::dequeif O(1) front ops are needed.- Raw memory + placement new avoid default-initialising unused slots.
- Capacity doubling ensures amortised O(1)
push_back. - Implement copy/move/destructor correctly — this class owns a resource.
Contents
