2

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.

  • 3
    From stackoverflow.com/a/2096581: "It's not possible to implement a std::vector<T> with a linked list because the standard guarantees the elements in the list will be held in contiguous memory." – Robert Harvey May 31 '15 at 3:23
  • Yes. I saw that post. If you look further down in the comments, it explicitly states that this was only as of C++ 2003 - which is why I added the caveat in my question. – J Trana May 31 '15 at 5:18
  • I've been doing some digging to see if I could find it again and the closest thing to what I remember that I've seen so far is VLists - they have that linked array sort of structure. – J Trana May 31 '15 at 5:34
  • 5
    "A series of linked arrays" sounds a lot like the typical implementation of std::deque. – Ixrec May 31 '15 at 11:53
  • Thanks @Ixrec, just took a look at deque implementations. Note quite what I was recalling (no increase/decrease in array size), but insightful nonetheless - and was highly useful if only to ask the question "why vector vs. deque" in a deeper way than I had before. – J Trana Jun 1 '15 at 1:22
2
+50

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)

  • +1 since this is the first answer that actually answers the question. Do you happen to know of any implementations that actually used this? And algorithm questions are perfectly on-topic here (even if some of them are also on-topic at SO). – Ixrec Jun 8 '15 at 19:18
  • 1
    @lxrec Actually I think (at least as of about 5-6 years ago) this is how std::vector is actually implemented. – 0fnt Jun 8 '15 at 23:13
  • Thanks for answering the question! This is indeed very similar to the VLists I brought up in the comments and appears to use the same amortizing runtime trick. @0fnt if you can point me to any sort of note about this being an STL implementation in the past from a semi-authoritative source, I will award you not only the bounty for the question but also an additional bounty! – J Trana Jun 8 '15 at 23:40
  • (Note: the same amortizing trick is present in both and this answer helps bridge the gap; this answer explains the insertion case of a standard array-based vector, the VList uses the same trick but without the copies because it uses separate arrays of different sizes - so there is still room for non-array answers here.) – J Trana Jun 9 '15 at 0:31
  • 1
    Nah, I think my mythical unicorn still exists out there! If you haven't taken a look at VLists, please do. This is a data structure that appeared in 2002, uses linked geometrically-sized arrays, and provides average O(1) access and nice runtimes for other operations as well... – J Trana Jun 10 '15 at 0:40
1

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.

  • 1
    I believe the standard includes performance guarantees for vector that would be hard to implement with anything but a contiguous memory block. – Gort the Robot May 31 '15 at 15:17
  • 1
    Hrmmm, well, true - but I think @ThomasEding is referring to a sort of a degenerate implementation here for which this can happen. Technically quite accurate, but not really in the spirit of the question. – J Trana Jun 1 '15 at 1:26
  • @StevenBurnap A fixed depth tree has the same asymptotic performance as a single block. Of course in practice the additional indirections will decrease performance. – CodesInChaos Jun 1 '15 at 6:51
  • @CodesInChaos: But now you've broken contiguous memory guarantees. – Thomas Eding Jun 1 '15 at 15:26
  • 1
    @ThomasEding Of course. This was just a response to Steven's comment that the performance guarantees would be hard to implement without a contiguous memory block. – CodesInChaos Jun 1 '15 at 17:08
0

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.

0

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!

  • I added an answer based on your Vlist link. – 0fnt Jun 10 '15 at 1:42
  • @0fnt I turned this into a community wiki. I'd like to preserve the content I have here as the accepted answer; however, if you'd like to merge the VList explanation in, that'd probably improve the answer. – J Trana Jun 11 '15 at 0:45
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.