[Containers] Marshalling deques
There's a thread here -- http://groups.google.com/group/comp.lang.c++/browse_thread/thread/0a6a19f831... that I'd like to mention. Does the deque in the Containers library have support for accessing the chunks it uses? Would you be willing to add a function that gives that? Tia. Shalom, Brian Wood Ebenezer Enterprises http://webEbenezer.net
El 22/08/2011 19:44, Brian Wood escribió:
There's a thread here -- http://groups.google.com/group/comp.lang.c++/browse_thread/thread/0a6a19f831...
that I'd like to mention. Does the deque in the Containers library have support for accessing the chunks it uses?
No.
Would you be willing to add a function that gives that? Tia.
Yes, I think we need to think about a useful interface for that, maybe something like local_iterator in unordered containers or something like segmented iterator described by Matt Austern in his "Segmented Iterators and Hierarchical Algorithms" paper Best, Ion
"Brian Wood" <woodbrian77@gmail.com> wrote in message news:CABWFOjtOAVqtM6Yf0tJ+FE=X1DKXwAWq8-K1rQGYKeFBZOzQQA@mail.gmail.com...
that I'd like to mention. Does the deque in the Containers library have support for accessing the chunks it uses? Would you be willing to add a function that gives that? Tia.
Shalom, Brian Wood
I think that having a “configurable” deque class template is one of the best things that could be offered by a boost Containers library. I have always wondered why noone wrote a version of the deque class template that allowed the configuration of such things as the page / block size, rather than have it be determined by a compile time formula based on the size of the data type being stored. It would seem to me that the page / block size is one of the more critical pieces affecting the size / speed tradeoffs in a deque’s performance when there are many insertions taking place. Michael Goldshteyn
El 25/08/2011 22:01, Michael Goldshteyn escribió:
"Brian Wood" <woodbrian77@gmail.com> wrote in message news:CABWFOjtOAVqtM6Yf0tJ+FE=X1DKXwAWq8-K1rQGYKeFBZOzQQA@mail.gmail.com...
that I'd like to mention. Does the deque in the Containers library have support for accessing the chunks it uses? Would you be willing to add a function that gives that? Tia.
Shalom, Brian Wood
I think that having a “configurable” deque class template is one of the best things that could be offered by a boost Containers library. I have always wondered why noone wrote a version of the deque class template that allowed the configuration of such things as the page / block size, rather than have it be determined by a compile time formula based on the size of the data type being stored. It would seem to me that the page / block size is one of the more critical pieces affecting the size / speed tradeoffs in a deque’s performance when there are many insertions taking place.
That's is a good idea, thanks. I'll add this to the to-do list. Best, Ion
"Ion Gaztañaga" wrote in message news:4E5725CA.6040206@gmail.com...
El 25/08/2011 22:01, Michael Goldshteyn escribió:
I think that having a “configurable” deque class template is one of the best things that could be offered by a boost Containers library. I have always wondered why noone wrote a version of the deque class template that allowed the configuration of such things as the page / block size, rather than have it be determined by a compile time formula based on the size of the data type being stored. It would seem to me that the page / block size is one of the more critical pieces affecting the size / speed tradeoffs in a deque’s performance when there are many insertions taking place.
That's is a good idea, thanks. I'll add this to the to-do list.
Likewise, making the growth multiplier for vector configurable via a template argument would be the other boon in such a container library. These two features (deque page / block size and vector multiplier config) should have been part of the STL to begin with. How many times have library vendors tweaked these two items? Why not let the developer choose his constants / coefficients at the time of class template instantiation? Michael Goldshteyn
On 26 August 2011 10:33, Michael Goldshteyn <mgoldshteyn@comcast.net> wrote:
Likewise, making the growth multiplier for vector configurable via a template argument would be the other boon in such a container library. These two features (deque page / block size and vector multiplier config) should have been part of the STL to begin with. How many times have library vendors tweaked these two items? Why not let the developer choose his constants / coefficients at the time of class template instantiation?
1. The problem is that template arguments change the type. Do you really want vector<int, std::allocator<int>, 2> to be a different type than vector<int, std::allocator<int>, 3>? 2. You want to be able to pass in floating point numbers to the multiplier (for instance, multipliers under the golden ratio allow a vector to reuse the holes it leaves in the heap). 3. In order to guarantee amortized O(1) push_back, you have to enforce that the multiplier is strictly > 1. There are, of course, ways to mitigate all of this. But it isn't clear that the added complexity is worth it. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
participants (4)
-
Brian Wood -
Ion Gaztañaga -
Michael Goldshteyn -
Nevin Liber