Re: Marshalling deques

From:

Leigh Johnston <leigh@i42.co.uk>

Newsgroups:

comp.lang.c++

Date:

Wed, 17 Aug 2011 18:46:07 +0100

Message-ID:

<SLCdne4dPfv7Y9bTnZ2dnUVZ8tydnZ2d@giganews.com>

On 17/08/2011 18:41, Leigh Johnston wrote:

On 17/08/2011 18:32, Victor Bazarov wrote:

On 8/17/2011 12:28 PM, Ebenezer wrote:

On Aug 17, 5:23 am, "Bo Persson"<b...@gmb.dk> wrote:

Ebenezer wrote:

When you have a vector of a primitive type, rather than
iterating through each element, you can marshal the vector
with the address of the first element and multiply the size
of the vector with the size of each element like this:

buf.Receive(&*vec.begin(), vec.size() * sizeof(T));

I'd like to do something similar with deques, but they are
implemented in chunks rather than a single chunk. How
to get the address and size of each chunk, though? Tia.

http://www.gotw.ca/gotw/054.htm

You cannot.

Deque has to use a two level addressing, probably involving an array
of pointers to the chunks, but the details are not specified by the
standard. There is no interface to this internal structure.

In that case, how about changing the standard? I believe iterating
through a deque is more involved than iterating through a vector.

So? It's not designed/designated to be "less involved" than vector. It's
designed to have a faster push_back than vector, and comparable lookup,
and have more relaxed memory requirements (no need to have a contiguous
block). Try iterating through a set...

I am of the opinion that you are incorrect to say that deque push_back
is designed to be faster than vector push_back. If you pre-allocate a
vector with reserve() then its push_back would easily out-perform deque
push_back. Even if you don't call reserve() I am still unconvinced that
deque's push_back out-performs vector's on average.

To confirm this I did some quick timings on VC++:

struct timer
{
     timer(const char* message)
     {
         std::cout << message;
         QueryPerformanceCounter(&iStartTime);
     }
     ~timer()
     {
         LARGE_INTEGER endTime;
         QueryPerformanceCounter(&endTime);
         LARGE_INTEGER freq;
         QueryPerformanceFrequency(&freq);
         std::cout.precision(4);
         std::cout << std::fixed << (float)(endTime.QuadPart -
iStartTime.QuadPart)/(float)freq.QuadPart << " seconds" << std::endl;
     }
     LARGE_INTEGER iStartTime;
};

int main()
{
    std::vector<int> v;
    {
        timer t("vector :");
        for (int i = 0; i != 10000000; ++i)
            v.push_back(i);
    }
    std::deque<int> d;
    {
        timer t("deque :");
        for (int i = 0; i != 10000000; ++i)
            d.push_back(i);
    }
}

outputs:

vector :0.0636 seconds
deque :0.2866 seconds

HTH.

/Leigh