Much of the work done by an involves shifting (by and ) and copying (by ) of data. In the implementations shown above, this was done using loops. It turns out that many programming environments have specific functions that are very efficient at copying and moving blocks of data. In the C programming language, there are the and functions. In the C++ language there is the algorithm. In Java there is the method.
void resize() { array<T> b(max(1, 2*n)); std::copy(a+0, a+n, b+0); a = b; } void add(int i, T x) { if (n + 1 > a.length) resize(); std::copy_backward(a+i, a+n, a+n+1); a[i] = x; n++; }
These functions are usually highly optimized and may even use special machine instructions that can do this copying much faster than we could by using a loop. Although using these functions does not asymptotically decrease the running times, it can still be a worthwhile optimization.
In the C++ implementations here, the use of the native resulted in speedups of a factor between 2 and 3, depending on the types of operations performed. Your mileage may vary.
opendatastructures.org