5 Dynamic Array
Published:
Implementation of
std::vector(templatized class)
Dynamically growable integer array (add to back)
- Allocate
sz + 1elements on the heap - When you call
push_back(), add to the provision element, andsize++
Preferred, since members already constructed and initialized simultaneously
- Avoids default construct, then assignment in the body
class IntArray {
private:
size_t sz;
size_t cap; // need cap declared before a
int* a;
public:
IntArray() : sz{0}, cap{1}, a{new int[cap]} // member initializer list
{
// sz = 0;
// cap = 1;
// a = new int[cap];
}
void push_back(int x) {
if (sz == cap) {
int* a2 = new int[cap * 2]; // if new fails, exits, but cap intact
cap *= 2; // strong exception guarantee
std::copy(a, a+sz, a2); // [first, last+1), dst
delete[] a;
a = a2;
}
a[sz++] = x;
}
// ...
- If have capacity, put the next element (\(O(1)\))
- If not, allocate double the capacity, copy over, and add (\(O(n)\))
- Overall complexity: \(O(2n) = O(n)\) for \(n\) elements
- Average: amortized \(O(1)\)
If an exception happens in the middle, it won’t mess up your object
Not planning to use copy constructor and copy assignment, so use delete
- Undefine the compiler generated one
- Copy attempts will fail to compile
- Use
defaultfor compiler generated
// ...
~IntArray() {
delete[] a;
}
IntArray(const IntArray&) = delete;
IntArray& operator=(const IntArray&) = delete;
int& operator[](int i) { return a[i]; }
const int& operator[](int i) const { return a[i]; }
size_t size() const { return sz; }
size_t capacity() const { return cap; }
};
int main() {
using namespace std;
IntArray ia;
for (int i = 0; i < 20; i++) {
ia.push_back(i);
cout << ia << endl;
}
}