Defining a vector with the at least size

[Kubani]

Hi,
By reading the following drill I see that I should define a vactor like this:

#define vector Vector
class vector {
int* p;

public:
    /*
    ...
   */
};

The drill:
Sometimes, it is desirable that an empty vector be as small as possible. For example, someone might use
vector<vector<vector<int>>> a lot but have most element vectors empty. Define a vector so that
sizeof(vector<int>)==sizeof(int*), that is, so that the vector itself consists only of a pointer to a representation
consisting of the elements, the number of elements, and the space pointer.

Is your understanding from the reading it similar to mine? (I'm note sure I have understood the drill completely)

[kbw]

That is what the question seems to be asking for, so I'd say yes.

However, you need to record the size of the vector too. If you can't store it in a separate variable, you can store it in the dynamically allocated thing along with the data.

[Kubani]

I didn't understand the last part! How to record the size of that vector!?

[kbw]

Well, you need to store an array of ints. And the size of the array can also fit in an int, so rather than declaring a second variable to hold that size, you can store it in the array.

Where in the array can we store it? We can store in the the first element, then store the vector data in elements one beyond the index.

So vector::size() const might look like:

int vector::size() const
{
    if (p)
        return p[0];  // we have an array, the size in in p[0]
    else
        return 0;  // we haven't allocated any space, so size must be zero.
}

The indexes would be shuffled down one, but we can hide that with operator[].

int& operator[](int index)
{
    if (!p  ||
        ( ! (0 <= index && index < size()) )
        throw std::out_of_range("Index out of range: " + std::to_string(index));

    return p[index + 1];
}

Does that make sense to you?

[keskiverto]

sizeof(T*) is independent of T, is it?

If yes, what if you don't hold a pointer p to T but to a pair of size_t and T* ?

[Kubani]

Isn't the drill pointing to the Pimpl idiom subject at all?
To be honest, I'm confused. I heard about that idiom from someone else but I'm not familiar with such an idiom nor have been taught about it :(

[dhayden]

My interpretation is that it wants something like this.
class vector {
class Implementation {
public:
int *data;
unsigned size;
// etc;
}
Implementation *imp; // this is the only data member.

vector() : imp(nullptr) {}
size_t size() {
if (imp == nullptr) return 0;
else return imp->size();
}
// etc.
};
So all the details are in the implementation class. The vector class just calls the appropriate methods on the imp member.

[kbw]

Oh, yes. I completely forgot about that. It's much better to use the pimpl pattern, rather than my dirty solution.

The idea is, if you're still confused, is to implement the functionality elsewhere, and hold a pointer to that implementation. It's a special case of composition.

[keskiverto]

@kbw: Your "dirty solution" (also the first one that did pop into my mind) evolves interestingly, when we decide that the size is stored as size_t and the value_type is a templated parameter. The sizeof(size_t) does not have to equal the sizeof(value_type) and thus the additional reserved space and offset to actual data are more math for the implementer. Drill material in itself.

C++11 did add smart pointers to the standard library and evolve pimpl-implementation details. The size of a smart pointer object compared to size of a pointer ...

[Kubani]

So apparently I need to use the pimple-idiom. OK, but I haven't been taught it. Where is the best place to be familiar with it with a simple example suitable for a learner?

[keskiverto]

Try: http://herbsutter.com/gotw/_100/