First of all, thanks Jens for the thorough overview - please consider any points I don't comment on below as accepted criticism and as things I will action upon:
- Please suggest stable labels and a location in the standard
where the additional container should go.
When you say "stable labels", do you mean numbered headings as in "220.127.116.11 deque specialized algorithms".
- The "Skipfield" template parameter is not specified.
Which restrictions apply? (For example, can it be void,
an array of unknown bound, an abstract base class, a function
type, or a non-copyable class type?)
I don't think it's necessary to leave it anything other than implementation-defined? The reference implementation must use unsigned integral types, but I don't want to obviate future potential improvements on implementations, that could, for example, use a floating-point type (somehow).
- Would it be useful to give the default template argument
for Skipfield a user-visible name? We also use the public
name std::allocator for the default argument of Allocator etc.
Since the type is meant to be implementation-defined, I'm unsure how to do this.
- "const size_type min/max_block_capacity"
drop "const"; it's ignored in a non-defining function declaration anyway.
There's plenty of use of const in the existing standard, for containers, not sure what is different about what I'm doing. For example:
"iterator insert(const_iterator position, size_type n, const T& x);"
under 18.104.22.168 Class template deque overview.
- The synopsis should show "assign" member functions near "operator=".
There are no assign member functions. I was following the path of other unordered containers by not including them. Is there an obvious reason for including them? Implementation would be clear();reserve();insert().
- " // Since this could be derived from --end() depending on implementation, and that could result in undefined behaviour in a colony with no insertions and unbounded iterators, whether this is noexcept is implementation-defined"
"Since" is rationale that doesn't belong in normative text. Do you want to say
noexcept( see below ) , or what?
Why is "rbegin() const" not so marked? Same question for crbegin().
I assumed the reader would be able to extrapolate from one to the others. Plus it's a large block of text. Maybe should go in a footnote and use a reference marker.
Why do we need this funny restriction anyway? Can the implementation
specialize reverse_iterator<colony::iterator> to do the right thing and
avoid the undefined behavior for rbegin() with no runtime cost and no
insane code cost? If so, that should be required, not implementation-defined.
The only way to avoid that behaviour is to store a permanent reference to the current back element in-code, which would need to be updated in many places, and that's costly. I don't like reverse iterators for performance reasons and I personally wouldn't ever sacrifice overall performance to obtain an undefined-behaviour free function for rbegin. I want to give implementors the same ability. Frankly, as an unordered-insert container, the relevance of reverse_iterators is sparse at-best.
- These block capacity functions use a "Skipfield" type (plus redundant const),
but the default arguments in the constructor use size_type. That seems inconsistent.
Good point. This is relevant to the current implementation but possibly not to others. Will fix.
- In general, the standard doesn't do "get_" and "set_" prefixes for getting/setting values.
Instead, we have
name_for_value(x) to set a value
name_for_value() to retrieve the value
I don't think that's clear, but okay.
If you need to return several values, use a struct with nice member names.
... Why. How is creating an arbitrary struct type, having the user instantiate one, and then have to get rid of it, any better than passing-by-reference. It's a waste of time for both the implementor and the user.
- similar for get_index_from_iterator; Why can't we use std::distance(begin(), it)
(We have "Complexity: Same as distance specialized algorithm, see below.", so there
seems to be no benefit.)
If you read the implementation you'll find there's a lot of code you can get rid of when you have the assumption of counting from begin(), which makes for a faster function. Whether an implementor decides to act on that is up to them.
"If n is larger than min_block_capacity, the capacity of the first block created will be the smaller of n or max_block_capacity."
If you want the min/max block capacity to have any normative impact,
you need to establish an actual abstract model you can tie into.
Otherwise, why does the capacity of some block matter at all?
Because the length of the block affects potential cache locality. The abstract model is described in Design Decisions.
- Why do we need MoveInsertable for "reserve" anyway? Aren't we just allocating
a new memory block of the desired size, without any moves?
That's an open question that I want addressed, so thanks for bringing it up - see 'questions for the committee' section.
"Complexity: Implementation-defined. One strong strategy involves using the standard library's sort function to sort an array of pointers to colony elements by the value of the elements they point to, and would have std::sort()'s complexity."
This is, of course, idle chatter. If there is a reasonable implementation
strategy that is O(n log n), we should simply require that complexity and be
done with it.
That also is an open question. See Questions for Committee section.
- splice p17:
"Better performance may be gained in some cases by allowing the source blocks to go to the front rather than the back, depending on how full the final block in x's iterative sequence is. This is because unused elements that are not at the back of colony's iterative sequence will need to be marked as skipped, and skipping over large numbers of elements will incur a small performance disadvantage during iteration compared to skipping over a small number of elements, due to memory locality."
You must be kidding me, right? Burn that with fire and move the ashes
to the prose section of the paper.
Okay calm down.
- approximate_memory_use p19
"Complexity: Implementation-defined. Should typically be constant."
If there is a reasonable implementation strategy to make this constant, then make it so
in the spec.
Constant relies on the same code (maintaining sequential memory block numbers or alternatively having vector of memory blocks rather than linked-list) that allows operators >/</>=/<= to exist. If the committee decides that they don't want those, you would have to maintain those just to allow for constant implementation of this function, which I'm not in favour of. However I see benefit to retaining
, so adopting a wait-and-see attitude at this point.
- Why is reinitialize needed? Can't you just do my_colony = colony(min_block_size, max_block_size) ?
Oh, we don't have that constructor, but it seems we should definitely have it.
That constructor is not possible as it creates overload conflict with the fill constructor when using integers.
- get_iterator_from_pointer p1: "pointer is not invalid" : The name of the parameter is element_pointer
(which is a bit verbose, though, just call it "p"). I think we need a precondition that the pointer
points to an element of *this.
- In general, I think we need to be more clear which operations invalidate iterators,
and we should do so in an overall introductory paragraph of the normative wording.
This is in the first appendix, but I'm happy to move it upwards if you can name the section you think it should be in.
and of course the lengthy explanation of the complexity doesn't belong here. Just say O(n)
Where? You mean in the technical spec? Or in the paper in general?