Satyam Shekhar skrev:
Hi Thorsten, I have been working on my proposal for the last few days and am almost done. Some of the questions which came to my mind:
a. Why would deque need a reserve function? Vector needs it because growing a vector is costly due to relocations, and a reserve can reduce those relocations. A deque which is *generally* (from the reading I did and the opinions on this list) implemented as a list of blocks (whose addresses are stored in an array) will not need the relocations because the blocks are all scattered in memory. The only case where relocations would be required is when the array storing the addresses grows and needs to be relocated. Will this be frequent? Is this the case we are targeting when we want to add the reserve function?
b. Why isn't the reserve function already there in a deque? Assuming there is a valid case for this function, adding it shouldn't be too difficult. Allocate a block(s) and add the address to the top-level array.
Well, I can't say why exactly std::deque is like it is. But I guess it has something to do with shrinking the container automatically when elements are erased (std::vector never does this). Now, I think it will be possible to implement reserve such that it allocates one big chunk with the new segments pointing into this chunk by adding a flag saying if the segment can be deallocated.
c. Why would be want to specify the size of the chunks? Again, as in a., relocation does not take place in a deque except the top-level array, and changing the chunk size will not change the frequency of relocations in that. Also, with blocks of unequal sizes, providing constant time random access will be difficult.
The chunk size needs to be the same. So if the chunk size is changed after elements is added to the container, it would need to reallocate to new segments (sort of like rehash()). But, initially, it would be very handy to set the segment size such that it matches your particular application, and such that allocation performance is portable accross compilers. With std::deque you just don't know.
Regarding the project proposal, I wished to know whether to put it on the mailing list first, or submit it through the gsoc app.
I guess you should do both. -Thorten