Hi Satyam, Thanks for clarifying that. Since we can use any implementation for

this, (which satisfies the requirements and an appropriate interface of course), I suggest using a dynamic array which grows on both sides.

As in you allocate one contiguous block, and start using it from the middle? The problem would be that you lose the property that pointers/iterators/references are not invalidated if the container only grows at the ends, since you may need to perform re-allocation after the beginning or end of the single contiguous block is reached. Also, with a list of blocks approach, wouldn't it be rather difficult

to provide amortized O(1) random access?

The list of blocks could be a vector of pointers, as described in the "Segmented Iterators and Hierarchical Algorithms" article that the ideas page links to. Regards, Eugene Wee

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

Esben Mose Hansen skrev:

On Friday 27 March 2009 20:02:41 Satyam Shekhar wrote:

...

b. Why isn't the reserve function already there in a deque? Assuming there is a [use] 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.

I'm pretty sure the assumption "there is a valid [use] case" is false.

reserve() is in vector so that clients can control when a possible complete realloc+move is going to happen, and possibly even avoid it altogether. This is important for a lot of reasons, including that all iterators get invalidated. For deque, new blocks are simply allocated as needed and the existing blocks are never reallocated. Thus, there would be little point with preallocating the array.

Please see my other post. -Thorsten

Satyam Shekhar wrote:

One of the factors influencing this would obviously be whether segmented iterators are going to be used widely in the future for other containers. (hash tables etc)

The segmented iterator abstraction certainly makes a lot of sense, so is there any reason why it should not be used widely in the future? Perhaps Andrei Alexandrescu will tell us some reasons why not: Dave Abrahams (http://lists.boost.org/Archives/boost/2009/03/150068.php) wrote:

The official schedule is now live at http://www.boostcon.com/program! A few highlights of the "mouth-watering content" (in the words of one enrollee) are:

* A keynote address from Andrei Alexandrescu called "Iterators Must Go." It's sure to be provocative!

I hope there will be some way to learn about his opinions even for non-BoostCon participants. Regards, Thomas

Mathias Gaunard on March 30 wrote:

Satyam Shekhar wrote:

...

But would it be worthwhile to modify Boost.Iterator itself and define new concepts using segmentedness as another orthogonal category, and then modify iterator_facade to support it? One of the factors influencing this would obviously be whether segmented iterators are going to be used widely in the future for other containers.

segmented iterators can also be used to iterate through recursive structures, such as trees, if I understood what I read on the subject correctly.

On a second thought (while deleting old mail...), this statement is misleading for several reasons: 1) A "normal" non-segmented iterator is perfectly able to iterate through recursive structures, such as trees. 2) A segmented iterator would be more efficient for "compile-time" recursice structures, but for "run-time" recursive structures, it would just fall back to the behavior (and efficiency) of a "normal" non-segmented iterator. 3) The "real" efficiency advantage of segmented iterators will normally come from the "inner-most" iteration, so whether a given recursive data structure will gain something by providing segmented-iterators will only depend on whether it is possible to provide a more efficient "inner-most" iteration for that data structure than without segmented iterators.