std::vector Non-Array Implementation?

Question

I've seen some posts on the StackExchange family of sites talking about std::vector implementations. They all seem to indicate that std::vector is implemented strictly as an array (in practice), and that C++ 2003 dictates contiguity of elements - pretty much closing non-array loopholes.

Now I thought that I had read once of a non-array implementation of std::vector - perhaps this predated the 2003 enforcement of contiguity? (Edit: Herb Sutter makes note of this here) I believe it was something like a series of linked arrays with decreasing or increasing sizes under the hood but I can't remember the details. Does anyone know of std::vector implementations (or perhaps, more broadly, non-STL vector implementations) that use a non-array approach like this?

Edit: I'd like to clarify here that the emphasis is less on strict std::vector implementation for C++ and rather more on 1) historical STL implementations prior to C++ 2003 contiguous elements constraints or possibly even 2) "vector" implementations in other languages - that do not use the usual array-like structure. A VList implementation of a vector might be a potential example and I'm looking for others.

Answer 1

StackOverflow would be a somewhat better place for asking programming/algorithm related questions. In any case, the implementation you must have read would be based on "tables". Here is how such implementation works:

• Initialize vector with size n, say n = 16

Address: 0xAAA0 to 0xAAB0 Memory reserved

• Insert 17 elements. First 16 inserted fine. Next element requires more memory.

STL Library: Allocate memory for 16 * 2 = 32. Copy 16 elements. (Actual time taken = 16 units). Insert the 17th element.

• Insert 16 more elements. First 15 inserted fine. Next element requires more space.

STL Library: Allocate memory for 16 * 2 * 2 = 64. Copy 32 elements. (Actual time taken = 32 units). Insert the 33rd element.

• Insert 32 more elements. First 31 inserted fine. Next requires more space. STL Library: Allocate memory for 16 * 2 * 2 * 2 = 128. Copy 64 elements. (Actual time taken = 64 units). Insert the 65th element.

This implementation is O(1) for accessing and O(1) amortized for insertion. How? Over a very large number of operations, the total time of inserts would be:

Time = 2^0 (inserts) + 2^0 (copy) + 2^1 / 2 ( inserts ) + 2^1(copy) + 2^2/2 (inserts) + 2^2 (copy) ... .. + 2^n(copy)

• Total number of inserts = 2^n Time = 2^0 + 2^0 + 2^0 + 2^1 + 2^1 + 2^2 + 2^2 = 1 + 2*2^0 + 2*2^1 +...+2*2^(n-1) = 1 + 2*(2^n - 1)

Average time per insert = 2 units

• Total inserts = 2^n + 1 Time = 2^0 + 2^0 + 2^0 + 2^1 + 2^1 + 2^2 + 2^2 + 2^3 ... = 1 + 2*2^0 + 2*2^1 +...+2*2^(n-1) + 2^n = 1 + 2*(2^n - 1) + 2^n

Average time per insert = 3 units

Its not a linked list- but I'm pretty this is what you read: 'increasing/decreasing' sizes. Decrease in size upon deletes is similar. When used size is less than 1/4, free up the rest of memory, free up half of memory. If you're using your own memory allocator, it shouldn't be too hard to free only what you want. But if you want to copy over as well, analysis would tell you deletes still remain O(1)

Answer 2

It's legally possible to implement std::vector<T> without using arrays (or data structures that use arrays under the hood). The only stipulation is that std::vector<T>::max_size() must return a value of 0 or 1.

---

Example:

// A standard's conforming sketch for (std::vector) that does not use arrays
// under the hood.
template <typename T>
class vector {
public:
    typedef T * iterator;

    vector () {}

    // This is provably guaranteed to be O(1) in the number of elements in the vector.
    void push_back (T const & x) {
        if (!ptr) {
            ptr = new T(x);
        }
        else {
            throw "You've been a bad boy. You've viloated this->max_size().";
        }
    }

    void pop_back () {
        assert(ptr);
        ptr.reset(nullptr);
    }

    size_t size () const {
        return ptr ? 1 : 0;
    }

    size_t max_size () const {
        return 1;
    }

    T * data () {
        return ptr;
    }

    iterator begin () {
        return ptr;
    }

    iterator end () {
        // Technically adding 1 to a non-array pointer is undefined (or at least
        // something to that effect). This problem can be mitigated by using a
        // proper iterator class instead of a typedef'ed pointer.
        return ptr ? ptr + 1 : ptr;
    }

private:
    std::unique_ptr<T> ptr;
};

---

The max_size() == 0 case is trivial. Left as an exercise for the reader.

Answer 3

Finding very old STL documentation may not be as easy as it sounds. What I do recall from using STL back in 1996 was &vec[0] was already guaranteed to provide the beginning of the vector's array of data. I doubt there were any non-array implementations that met the original STL specs.

Answer 4

It took me a while to find something I thought to be authoritative and finally found this nugget from a Dr. Dobb's Journal 2001 article:

"Intuitively, the standard-library vector class is like a built-in array: we can think of it as holding its elements in a single block of contiguous memory. Indeed, although the C++ Standard does not explicitly require that the elements of a vector occupy contiguous memory, the standards committee decided in its October, 2000 meeting that this requirement was missing due to an oversight, and voted to include the requirement as part of its Technical Corrigendum. This delayed imposition was not a particular hardship, because every existing implementation already worked that way."

So from a strict perspective, I believe no STL implementation ever used something other than an array.

However, for the curious, I believe that VLists (the growing array variant) more or less meet all the runtime requirements of std::vector without contiguity and notably without extra copies during expansion. From a more theoretical point of view, stable_vector is an interesting approach for iterator management and fits the bill from a more "letter of the law" perspective.

Also, thanks @0fnt for your explanation of amortized growth!

Answer 5

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

O(1) time for every single acces. I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..

EDIT: If we don't assume RAM model, then the expected complexity of an access would be O(1) under assumptions of all indices being access uniformly. The time bound step would be finding which main_array has the data and that would be computed by looking at the bits in the index. The probabilistic analysis here is same as that of VList.