| Doc. no. | N4484 |
| Date: | 2015-05-23 |
| Project: | Programming Language C++ |
| Reply to: | Marshall Clow <lwgchair@gmail.com> |
Revised 2015-05-23 at 15:05:40 UTC
Reference ISO/IEC IS 14882:2014(E)
Also see:
The purpose of this document is to record the status of issues which have come before the Library Working Group (LWG) of the INCITS PL22.16 and ISO WG21 C++ Standards Committee. Issues represent potential defects in the ISO/IEC IS 14882:2014(E) document.
This document contains only library issues which are actively being considered by the Library Working Group, i.e., issues which have a status of New, Open, Ready, or Review. See Library Defect Reports List for issues considered defects and Library Closed Issues List for issues considered closed.
The issues in these lists are not necessarily formal ISO Defect Reports (DR's). While some issues will eventually be elevated to official Defect Report status, other issues will be disposed of in other ways. See Issue Status.
Prior to Revision 14, library issues lists existed in two slightly different versions; a Committee Version and a Public Version. Beginning with Revision 14 the two versions were combined into a single version.
This document includes [bracketed italicized notes] as a reminder to the LWG of current progress on issues. Such notes are strictly unofficial and should be read with caution as they may be incomplete or incorrect. Be aware that LWG support for a particular resolution can quickly change if new viewpoints or killer examples are presented in subsequent discussions.
For the most current official version of this document see http://www.open-std.org/jtc1/sc22/wg21/. Requests for further information about this document should include the document number above, reference ISO/IEC 14882:2014(E), and be submitted to Information Technology Industry Council (ITI), 1250 Eye Street NW, Washington, DC 20005.
Public information as to how to obtain a copy of the C++ Standard, join the standards committee, submit an issue, or comment on an issue can be found in the comp.std.c++ FAQ.
Issues reported to the LWG transition through a variety of statuses, indicating their progress towards a resolution. Typically, most issues will flow through the following stages.
New - The issue has not yet been reviewed by the LWG. Any Proposed Resolution is purely a suggestion from the issue submitter, and should not be construed as the view of LWG.
Open - The LWG has discussed the issue but is not yet ready to move the issue forward. There are several possible reasons for open status:
A Proposed Resolution for an open issue is still not be construed as the view of LWG. Comments on the current state of discussions are often given at the end of open issues in an italic font. Such comments are for information only and should not be given undue importance.
Review - Exact wording of a Proposed Resolution is now available for review on an issue for which the LWG previously reached informal consensus.
Ready - The LWG has reached consensus that the issue is a defect in the Standard, the Proposed Resolution is correct, and the issue is ready to forward to the full committee for further action as a Defect Report (DR).
Typically, an issue must have a proposed resolution in the currently published issues list, whose wording does not change during LWG review, to move to the Ready status.
Voting - This status should not be seen in a published issues list, but is a marker for use during meetings to indicate an issues was Ready in the pre-meeting mailing, the Proposed Resolution is correct, and the issue will be offered to the working group at the end of the current meeting to apply to the current working paper (WP) or to close in some other appropriate manner. This easily distinguishes such issues from those moving to Ready status during the meeting itself, that should not be forwarded until the next meeting. If the issue does not move forward, it should fall back to one of the other open states before the next list is published.
Immediate - This status should not be seen in a published issues list, but is a marker for use during meetings to indicate an issues was not Ready in the pre-meeting mailing, but the Proposed Resolution is correct, and the issue will be offered to the working group at the end of the current meeting to apply to the current working paper (WP) or to close in some other appropriate manner. This status is used only rarely, typically for fixes that are both small and obvious, and usually within a meeting of the expected publication of a revised standard. If the issue does not move forward, it should fall back to one of the other open states before the next list is published.
In addition, there are a few ways to categorise and issue that remains open to a resolution within the library, but is not actively being worked on.
Deferred - The LWG has discussed the issue, is not yet ready to move the issue forward, but neither does it deem the issue significant enough to delay publishing a standard or Technical Report. A typical deferred issue would be seeking to clarify wording that might be technically correct, but easily mis-read.
A Proposed Resolution for a deferred issue is still not be construed as the view of LWG. Comments on the current state of discussions are often given at the end of open issues in an italic font. Such comments are for information only and should not be given undue importance.
Core - The LWG has discussed the issue, and feels that some key part of resolving the issue is better handled by a cleanup of the language in the Core part of the standard. The issue is passed to the Core Working Group, which should ideally open a corresponding issue that can be linked from the library issue. Such issues will be revisitted after Core have made (or declined to make) any changes.
EWG - The LWG has discussed the issue, and wonder that some key part of resolving the issue is better handled by some (hopefully small) extension to the language. The issue is passed to the Evolution Working Group, which should ideally open a corresponding issue that can be linked from the library issue. Such issues will be revisitted after Evoltion have made (or declined to make) any recommendations. Positive recommendations from EWG will often mean the issue transition to Core status while we wait for some proposed new feature to land in the working paper.
LEWG - The LWG has discussed the issue, and deemd the issue is either an extension, however small, or changes the library design in some fundamental way, and so has delegated the initial work to the Library Evolution Working Group.
Ultimately, all issues should reach closure with one of the following statuses.
DR - (Defect Report) - The full WG21/PL22.16 committee has voted to forward the issue to the Project Editor to be processed as a Potential Defect Report. The Project Editor reviews the issue, and then forwards it to the WG21 Convenor, who returns it to the full committee for final disposition. This issues list accords the status of DR to all these Defect Reports regardless of where they are in that process.
WP - (Working Paper) - The proposed resolution has not been accepted as a Technical Corrigendum, but the full WG21/PL22.16 committee has voted to apply the Defect Report's Proposed Resolution to the working paper.
C++14 - (C++ Standard, as revised for 2014) - The full WG21/PL22.16 committee has voted to accept the Defect Report's Proposed Resolution into the published 2011 revision to the C++ standard, ISO/IEC IS 14882:2014(E).
C++11 - (C++ Standard, as revised for 2011) - The full WG21/PL22.16 committee has voted to accept the Defect Report's Proposed Resolution into the published 2011 revision to the C++ standard, ISO/IEC IS 14882:2011(E).
CD1 - (Committee Draft 2008) - The full WG21/PL22.16 committee has voted to accept the Defect Report's Proposed Resolution into the Fall 2008 Committee Draft.
TC1 - (Technical Corrigenda 1) - The full WG21/PL22.16 committee has voted to accept the Defect Report's Proposed Resolution as a Technical Corrigenda. Action on this issue is thus complete and no further action is possible under ISO rules.
TRDec - (Decimal TR defect) - The LWG has voted to accept the Defect Report's Proposed Resolution into the Decimal TR. Action on this issue is thus complete and no further action is expected.
Resolved - The LWG has reached consensus that the issue is a defect in the Standard, but the resolution adopted to resolve the issue came via some other mechanism than this issue in the list - typically by applying a formal paper, occasionally as a side effect of consolidating several interacting issue resolutions into a single issue.
Dup - The LWG has reached consensus that the issue is a duplicate of another issue, and will not be further dealt with. A Rationale identifies the duplicated issue's issue number.
NAD - The LWG has reached consensus that the issue is not a defect in the Standard.
NAD Editorial - The LWG has reached consensus that the issue can either be handled editorially, or is handled by a paper (usually linked to in the rationale).
Tentatively - This is a status qualifier. The issue has been reviewed online, or at an unofficial meeting, but not in an official meeting, and some support has been formed for the qualified status. Tentatively qualified issues may be moved to the unqualified status and forwarded to full committee (if Ready) within the same meeting. Unlike Ready issues, Tentatively Ready issues will be reviewed in subcommittee prior to forwarding to full committee. When a status is qualified with Tentatively, the issue is still considered active.
Pending - This is a status qualifier. When prepended to a status this indicates the issue has been processed by the committee, and a decision has been made to move the issue to the associated unqualified status. However for logistical reasons the indicated outcome of the issue has not yet appeared in the latest working paper.
The following statuses have been retired, but may show up on older issues lists.
NAD Future - In addition to the regular status, the LWG believes that this issue should be revisited at the next revision of the standard. That is now an ongoing task managed by the Library Evolution Working Group, and most issues in this status were reopended with the status LEWG.
NAD Concepts - This status reflects an evolution of the language during the development of C++11, where a new feature entered the language, called concepts, that fundamentally changed the way templates would be specified and written. While this language feature was removed towards the end of the C++11 project, there is a clear intent to revisit this part of the language design. During that development, a number of issues were opened against the updated library related to use of that feature, or requesting fixes that would require exlicit use of the concepts feature. All such issues have been closed with this status, and may be revisitted should this or a similar language feature return for a future standard.
Issues are always given the status of New when they first appear on the issues list. They may progress to Open or Review while the LWG is actively working on them. When the LWG has reached consensus on the disposition of an issue, the status will then change to Dup, NAD, or Ready as appropriate. Once the full PL22.16 committee votes to forward Ready issues to the Project Editor, they are given the status of Defect Report (DR). These in turn may become the basis for Technical Corrigenda (TC1), an updated standard (C++11, C++14), or are closed without action other than a Record of Response (Resolved) where the desired effect has already been achieved by some other process. The intent of this LWG process is that only issues which are truly defects in the Standard move to the formal ISO DR status.
Section: 27.6.3 [streambuf] Status: LEWG Submitter: Martin Sebor Opened: 2000-08-12 Last modified: 2015-04-08
View all other issues in [streambuf].
View all issues with LEWG status.
Discussion:
The basic_streambuf members gbump() and pbump() are specified to take an int argument. This requirement prevents the functions from effectively manipulating buffers larger than std::numeric_limits<int>::max() characters. It also makes the common use case for these functions somewhat difficult as many compilers will issue a warning when an argument of type larger than int (such as ptrdiff_t on LLP64 architectures) is passed to either of the function. Since it's often the result of the subtraction of two pointers that is passed to the functions, a cast is necessary to silence such warnings. Finally, the usage of a native type in the functions signatures is inconsistent with other member functions (such as sgetn() and sputn()) that manipulate the underlying character buffer. Those functions take a streamsize argument.
[ 2009-07 Frankfurt ]
This is part of a bigger problem. If anyone cares enough, they should write a paper solving the bigger problem of offset types in iostreams.
This is related to the paper about large file sizes. Beman has already agreed to drop the section of that paper that deals with this.
int is big enough for reasonable buffers.
Move to NAD Future.
This is related to LWG 423.
Proposed resolution:
Change the signatures of these functions in the synopsis of template class basic_streambuf (27.5.2) and in their descriptions (27.5.2.3.1, p4 and 27.5.2.3.2, p4) to take a streamsize argument.
Although this change has the potential of changing the ABI of the library, the change will affect only platforms where int is different than the definition of streamsize. However, since both functions are typically inline (they are on all known implementations), even on such platforms the change will not affect any user code unless it explicitly relies on the existing type of the functions (e.g., by taking their address). Such a possibility is IMO quite remote.
Alternate Suggestion from Howard Hinnant, c++std-lib-7780:
This is something of a nit, but I'm wondering if streamoff wouldn't be a better choice than streamsize. The argument to pbump and gbump MUST be signed. But the standard has this to say about streamsize (27.4.1/2/Footnote):
[Footnote: streamsize is used in most places where ISO C would use size_t. Most of the uses of streamsize could use size_t, except for the strstreambuf constructors, which require negative values. It should probably be the signed type corresponding to size_t (which is what Posix.2 calls ssize_t). --- end footnote]
This seems a little weak for the argument to pbump and gbump. Should we ever really get rid of strstream, this footnote might go with it, along with the reason to make streamsize signed.
Rationale:
The LWG believes this change is too big for now. We may wish to reconsider this for a future revision of the standard. One possibility is overloading pbump, rather than changing the signature.
[ [2006-05-04: Reopened at the request of Chris (Krzysztof ?elechowski)] ]
Section: 27 [input.output] Status: LEWG Submitter: Martin Sebor Opened: 2003-09-18 Last modified: 2015-04-08
View all other issues in [input.output].
View all issues with LEWG status.
Discussion:
A third party test suite tries to exercise istream::ignore(N) with a negative value of N and expects that the implementation will treat N as if it were 0. Our implementation asserts that (N >= 0) holds and aborts the test.
I can't find anything in section 27 that prohibits such values but I don't see what the effects of such calls should be, either (this applies to a number of unformatted input functions as well as some member functions of the basic_streambuf template).
[ 2009-07 Frankfurt ]
This is related to LWG 255.
Move to NAD Future.
Proposed resolution:
I propose that we add to each function in clause 27 that takes an argument, say N, of type streamsize a Requires clause saying that "N >= 0." The intent is to allow negative streamsize values in calls to precision() and width() but disallow it in calls to streambuf::sgetn(), istream::ignore(), or ostream::write().
[Kona: The LWG agreed that this is probably what we want. However, we need a review to find all places where functions in clause 27 take arguments of type streamsize that shouldn't be allowed to go negative. Martin will do that review.]
Section: 24.2.3 [input.iterators] Status: LEWG Submitter: Chris Jefferson Opened: 2004-09-16 Last modified: 2015-04-08
View all other issues in [input.iterators].
View all issues with LEWG status.
Discussion:
From comp.std.c++:
I note that given an input iterator a for type T, then *a only has to be "convertable to T", not actually of type T.
Firstly, I can't seem to find an exact definition of "convertable to T". While I assume it is the obvious definition (an implicit conversion), I can't find an exact definition. Is there one?
Slightly more worryingly, there doesn't seem to be any restriction on the this type, other than it is "convertable to T". Consider two input iterators a and b. I would personally assume that most people would expect *a==*b would perform T(*a)==T(*b), however it doesn't seem that the standard requires that, and that whatever type *a is (call it U) could have == defined on it with totally different symantics and still be a valid inputer iterator.
Is this a correct reading? When using input iterators should I write T(*a) all over the place to be sure that the object I'm using is the class I expect?
This is especially a nuisance for operations that are defined to be "convertible to bool". (This is probably allowed so that implementations could return say an int and avoid an unnessary conversion. However all implementations I have seen simply return a bool anyway. Typical implemtations of STL algorithms just write things like while(a!=b && *a!=0). But strictly speaking, there are lots of types that are convertible to T but that also overload the appropriate operators so this doesn't behave as expected.
If we want to make code like this legal (which most people seem to expect), then we'll need to tighten up what we mean by "convertible to T".
[Lillehammer: The first part is NAD, since "convertible" is well-defined in core. The second part is basically about pathological overloads. It's a minor problem but a real one. So leave open for now, hope we solve it as part of iterator redesign.]
[ 2009-07-28 Reopened by Alisdair. No longer solved by concepts. ]
[ 2009-10 Santa Cruz: ]
Mark as NAD Future. We agree there's an issue, but there is no proposed solution at this time and this will be solved by concepts in the future.
Proposed resolution:
Rationale:
[ San Francisco: ]
Solved by N2758.
Section: 28 [re] Status: LEWG Submitter: Eric Niebler Opened: 2005-07-01 Last modified: 2015-04-08
View other active issues in [re].
View all other issues in [re].
View all issues with LEWG status.
Discussion:
A problem with TR1 regex is currently being discussed on the Boost developers list. It involves the handling of case-insensitive matching of character ranges such as [Z-a]. The proper behavior (according to the ECMAScript standard) is unimplementable given the current specification of the TR1 regex_traits<> class template. John Maddock, the author of the TR1 regex proposal, agrees there is a problem. The full discussion can be found at http://lists.boost.org/boost/2005/06/28850.php (first message copied below). We don't have any recommendations as yet.
-- Begin original message --
The situation of interest is described in the ECMAScript specification (ECMA-262), section 15.10.2.15:
"Even if the pattern ignores case, the case of the two ends of a range is significant in determining which characters belong to the range. Thus, for example, the pattern /[E-F]/i matches only the letters E, F, e, and f, while the pattern /[E-f]/i matches all upper and lower-case ASCII letters as well as the symbols [, \, ], ^, _, and `."
A more interesting case is what should happen when doing a case-insentitive match on a range such as [Z-a]. It should match z, Z, a, A and the symbols [, \, ], ^, _, and `. This is not what happens with Boost.Regex (it throws an exception from the regex constructor).
The tough pill to swallow is that, given the specification in TR1, I don't think there is any effective way to handle this situation. According to the spec, case-insensitivity is handled with regex_traits<>::translate_nocase(CharT) -- two characters are equivalent if they compare equal after both are sent through the translate_nocase function. But I don't see any way of using this translation function to make character ranges case-insensitive. Consider the difficulty of detecting whether "z" is in the range [Z-a]. Applying the transformation to "z" has no effect (it is essentially std::tolower). And we're not allowed to apply the transformation to the ends of the range, because as ECMA-262 says, "the case of the two ends of a range is significant."
So AFAICT, TR1 regex is just broken, as is Boost.Regex. One possible fix is to redefine translate_nocase to return a string_type containing all the characters that should compare equal to the specified character. But this function is hard to implement for Unicode, and it doesn't play nice with the existing ctype facet. What a mess!
-- End original message --
[ John Maddock adds: ]
One small correction, I have since found that ICU's regex package does implement this correctly, using a similar mechanism to the current TR1.Regex.
Given an expression [c1-c2] that is compiled as case insensitive it:
Enumerates every character in the range c1 to c2 and converts it to it's case folded equivalent. That case folded character is then used a key to a table of equivalence classes, and each member of the class is added to the list of possible matches supported by the character-class. This second step isn't possible with our current traits class design, but isn't necessary if the input text is also converted to a case-folded equivalent on the fly.
ICU applies similar brute force mechanisms to character classes such as [[:lower:]] and [[:word:]], however these are at least cached, so the impact is less noticeable in this case.
Quick and dirty performance comparisons show that expressions such as "[X-\\x{fff0}]+" are indeed very slow to compile with ICU (about 200 times slower than a "normal" expression). For an application that uses a lot of regexes this could have a noticeable performance impact. ICU also has an advantage in that it knows the range of valid characters codes: code points outside that range are assumed not to require enumeration, as they can not be part of any equivalence class. I presume that if we want the TR1.Regex to work with arbitrarily large character sets enumeration really does become impractical.
Finally note that Unicode has:
Three cases (upper, lower and title). One to many, and many to one case transformations. Character that have context sensitive case translations - for example an uppercase sigma has two different lowercase forms - the form chosen depends on context(is it end of a word or not), a caseless match for an upper case sigma should match either of the lower case forms, which is why case folding is often approximated by tolower(toupper(c)).
Probably we need some way to enumerate character equivalence classes, including digraphs (either as a result or an input), and some way to tell whether the next character pair is a valid digraph in the current locale.
Hoping this doesn't make this even more complex that it was already,
[ Portland: Alisdair: Detect as invalid, throw an exception. Pete: Possible general problem with case insensitive ranges. ]
[ 2009-07 Frankfurt ]
We agree that this is a problem, but we do not know the answer.
We are going to declare this NAD until existing practice leads us in some direction.
No objection to NAD Future.
Move to NAD Future.
Proposed resolution:
Section: 20.4.2.7 [tuple.rel], TR1 6.1.3.5 [tr.tuple.rel] Status: LEWG Submitter: David Abrahams Opened: 2005-11-29 Last modified: 2015-04-08
View other active issues in [tuple.rel].
View all other issues in [tuple.rel].
View all issues with LEWG status.
Duplicate of: 348
Discussion:
Where possible, tuple comparison operators <,<=,=>, and > ought to be defined in terms of std::less rather than operator<, in order to support comparison of tuples of pointers.
[ 2009-07-28 Reopened by Alisdair. No longer solved by concepts. ]
[ 2009-10 Santa Cruz: ]
If we solve this for tuple we would have to solve it for pair algorithms, etc. It is too late to do that at this time. Move to NAD Future.
Proposed resolution:
change 6.1.3.5/5 from:
Returns: The result of a lexicographical comparison between t and u. The result is defined as: (bool)(get<0>(t) < get<0>(u)) || (!(bool)(get<0>(u) < get<0>(t)) && ttail < utail), where rtail for some tuple r is a tuple containing all but the first element of r. For any two zero-length tuples e and f, e < f returns false.
to:
Returns: The result of a lexicographical comparison between t and u. For any two zero-length tuples e and f, e < f returns false. Otherwise, the result is defined as: cmp( get<0>(t), get<0>(u)) || (!cmp(get<0>(u), get<0>(t)) && ttail < utail), where rtail for some tuple r is a tuple containing all but the first element of r, and cmp(x,y) is an unspecified function template defined as follows.
Where T is the type of x and U is the type of y:
if T and U are pointer types and T is convertible to U, returns less<U>()(x,y)
otherwise, if T and U are pointer types, returns less<T>()(x,y)
otherwise, returns (bool)(x < y)
[ Berlin: This issue is much bigger than just tuple (pair, containers, algorithms). Dietmar will survey and work up proposed wording. ]
Rationale:
Recommend NAD. This will be fixed with the next revision of concepts.
[ San Francisco: ]
Solved by N2770.
Section: 22 [localization] Status: LEWG Submitter: Peter Dimov Opened: 2007-07-28 Last modified: 2015-04-08
View all other issues in [localization].
View all issues with LEWG status.
Discussion:
The POSIX "Extended API Set Part 4,"
introduces extensions to the C locale mechanism that allow multiple concurrent locales to be used in the same application by introducing a type locale_t that is very similar to std::locale, and a number of _l functions that make use of it.
The global locale (set by setlocale) is now specified to be per- process. If a thread does not call uselocale, the global locale is in effect for that thread. It can install a per-thread locale by using uselocale.
There is also a nice querylocale mechanism by which one can obtain the name (such as "de_DE") for a specific facet, even for combined locales, with no std::locale equivalent.
std::locale should be harmonized with the new POSIX locale_t mechanism and provide equivalents for uselocale and querylocale.
[ Kona (2007): Bill and Nick to provide wording. ]
[ San Francisco: Bill and Nick still intend to provide wording, but this is a part of the task to be addressed by the group that will look into issue 860. ]
[ 2009-07 Frankfurt: ]
It's our intention to stay in sync with WG14. If WG14 makes a decision that requires a change in WG21 the issue will be reopened.
Move to NAD Future.
Proposed resolution:
Section: 23.2 [container.requirements] Status: Tentatively NAD Submitter: Paolo Carlini Opened: 2007-11-11 Last modified: 2015-04-08
View other active issues in [container.requirements].
View all other issues in [container.requirements].
View all issues with Tentatively NAD status.
Discussion:
In an emplace member function the function parameter pack may be bound to a priori unlimited number of objects: some or all of them can be elements of the container itself. Apparently, in order to conform to the blanket statement 23.2 [container.requirements]/11, the implementation must check all of them for that possibility. A possible solution can involve extending the exception in 23.2 [container.requirements]/12 also to the emplace member. As a side note, the push_back and push_front member functions are luckily not affected by this problem, can be efficiently implemented anyway.
[ Related to 767 and to 2164 ]
[ Bellevue: ]
The proposed addition (13) is partially redundant with the existing paragraph 12. Why was the qualifier "rvalues" added to paragraph 12? Why does it not cover subelements and pointers?
Resolution: Alan Talbot to rework language, then set state to Review.
[ 2009-07 Frankfurt ]
The problem is broader than emplace. The LWG doesn't feel that it knows how to write wording that prohibits all of the problematic use cases at this time.
NAD Future.
[2015-02 Cologne]
LWG believes that 2164 addresses this issue and therefore considers 760 as NAD.
Proposed resolution:
Add after 23.2 [container.requirements]/12:
-12- Objects passed to member functions of a container as rvalue references shall not be elements of that container. No diagnostic required.
-13- Objects bound to the function parameter pack of the emplace member function shall not be elements or sub-objects of elements of the container. No diagnostic required.
Section: 23.4 [associative], 23.5 [unord] Status: LEWG Submitter: Alan Talbot Opened: 2008-05-18 Last modified: 2015-04-08
View other active issues in [associative].
View all other issues in [associative].
View all issues with LEWG status.
Discussion:
Splice is a very useful feature of list. This functionality is also very useful for any other node based container, and I frequently wish it were available for maps and sets. It seems like an omission that these containers lack this capability. Although the complexity for a splice is the same as for an insert, the actual time can be much less since the objects need not be reallocated and copied. When the element objects are heavy and the compare operations are fast (say a map<int, huge_thingy>) this can be a big win.
Suggested resolution:
Add the following signatures to map, set, multimap, multiset, and the unordered associative containers:
void splice(list<T,Allocator>&& x); void splice(list<T,Allocator>&& x, const_iterator i); void splice(list<T,Allocator>&& x, const_iterator first, const_iterator last);
Hint versions of these are also useful to the extent hint is useful. (I'm looking for guidance about whether hints are in fact useful.)
void splice(const_iterator position, list<T,Allocator>&& x); void splice(const_iterator position, list<T,Allocator>&& x, const_iterator i); void splice(const_iterator position, list<T,Allocator>&& x, const_iterator first, const_iterator last);
[ Sophia Antipolis: ]
Don't try to splice "list" into the other containers, it should be container-type.
forward_list already has splice_after.
Would "splice" make sense for an unordered_map?
Jens, Robert: "splice" is not the right term, it implies maintaining ordering in lists.
Howard: adopt?
Jens: absorb?
Alan: subsume?
Robert: recycle?
Howard: transfer? (but no direction)
Jens: transfer_from. No.
Alisdair: Can we give a nothrow guarantee? If your compare() and hash() doesn't throw, yes.
Daniel: For unordered_map, we can't guarantee nothrow.
[ San Francisco: ]
Martin: this would possibly outlaw an implementation technique that is currently in use; caching nodes in containers.
Alan: if you cache in the allocator, rather than the individual container, this proposal doesn't interfere with that.
Martin: I'm not opposed to this, but I'd like to see an implementation that demonstrates that it works.
[ 2009-07 Frankfurt: ]
NAD Future.
[ 2009-09-19 Howard adds: ]
I'm not disagreeing with the NAD Future resolution. But when the future gets here, here is a possibility worth exploring:
Add to the "unique" associative containers:
typedef details node_ptr; node_ptr remove(const_iterator p); pair<iterator, bool> insert(node_ptr&& nd); iterator insert(const_iterator p, node_ptr&& nd);And add to the "multi" associative containers:
typedef details node_ptr; node_ptr remove(const_iterator p); iterator insert(node_ptr&& nd); iterator insert(const_iterator p, node_ptr&& nd);Container::node_ptr is a smart pointer much like unique_ptr. It owns a node obtained from the container it was removed from. It maintains a reference to the allocator in the container so that it can properly deallocate the node if asked to, even if the allocator is stateful. This being said, the node_ptr can not outlive the container for this reason.
The node_ptr offers "const-free" access to the node's value_type.
With this interface, clients have a great deal of flexibility:
- A client can remove a node from one container, and insert it into another (without any heap allocation). This is the splice functionality this issue asks for.
- A client can remove a node from a container, change its key or value, and insert it back into the same container, or another container, all without the cost of allocating a node.
- If the Compare function is nothrow (which is very common), then this functionality is nothrow unless modifying the value throws. And if this does throw, it does so outside of the containers involved.
- If the Compare function does throw, the insert function will have the argument nd retain ownership of the node.
- The node_ptr should be independent of the Compare parameter so that a node can be transferred from set<T, C1, A> to set<T, C2, A> (for example).
Here is how the customer might use this functionality:
Splice a node from one container to another:
m2.insert(m1.remove(i));Change the "key" in a std::map without the cost of node reallocation:
auto p = m.remove(i); p->first = new_key; m.insert(std::move(p));Change the "value" in a std::set without the cost of node reallocation:
auto p = s.remove(i); *p = new_value; s.insert(std::move(p));Move a move-only or heavy object out of an associative container (as opposed to the proposal in 1041):
MoveOnly x = std::move(*s.remove(i));
- remove(i) transfers ownership of the node from the set to a temporary node_ptr.
- The node_ptr is dereferenced, and that non-const reference is sent to move to cast it to an rvalue.
- The rvalue MoveOnly is move constructed into x from the node_ptr.
- ~node_ptr() destructs the moved-from MoveOnly and deallocates the node.
Contrast this with the 1041 solution:
MoveOnly x = std::move(s.extract(i).first);The former requires one move construction for x while the latter requires two (one into the pair and then one into x). Either of these constructions can throw (say if there is only a copy constructor for x). With the former, the point of throw is outside of the container s, after the element has been removed from the container. With the latter, one throwing construction takes place prior to the removal of the element, and the second takes place after the element is removed.
The "node insertion" API maintains the API associated with inserting value_types so the customer can use familiar techniques for getting an iterator to the inserted node, or finding out whether it was inserted or not for the "unique" containers.
Lightly prototyped. No implementation problems. Appears to work great for the client.
Proposed resolution:
Section: 23.3.2 [array] Status: LEWG Submitter: Benjamin Kosnik Opened: 2008-06-05 Last modified: 2015-04-08
View other active issues in [array].
View all other issues in [array].
View all issues with LEWG status.
Discussion:
This is an issue that came up on the libstdc++ list, where a discrepancy between "C" arrays and C++0x's std::array was pointed out.
In "C," this array usage is possible:
int ar[] = {1, 4, 6};
But for C++,
std::array<int> a = { 1, 4, 6 }; // error
Instead, the second parameter of the array template must be explicit, like so:
std::array<int, 3> a = { 1, 4, 6 };
Doug Gregor proposes the following solution, that assumes generalized initializer lists.
template<typename T, typename... Args>
inline array<T, sizeof...(Args)>
make_array(Args&&... args)
{ return { std::forward<Args>(args)... }; }
Then, the way to build an array from a list of unknown size is:
auto a = make_array<T>(1, 4, 6);
[ San Francisco: ]
Benjamin: Move to Ready?
Bjarne: I'm not convinced this is useful enough to add, so I'd like us to have time to reflect on it.
Alisdair: the constraints are wrong, they should be
template<ValueType T, ValueType... Args> requires Convertible<Args, T>... array<T, sizeof...(Args)> make_array(Args&&... args);Alidair: this would be useful if we had a constexpr version.
Bjarne: this is probably useful for arrays with a small number of elements, but it's not clearly useful otherwise.
Consensus is to move to Open.
[ 2009-06-07 Daniel adds: ]
I suggest a fix and a simplification of the current proposal: Recent prototyping by Howard showed, that a fix is required because narrowing conversion 8.5.4 [dcl.init.list]/6 b.3 would severely limit the possible distribution of argument types, e.g. the expression make_array<double>(1, 2.0) is ill-formed, because the narrowing happens inside the function body where no constant expressions exist anymore. Furthermore given e.g.
int f(); double g();we probably want to support
make_array<double>(f(), g());as well. To make this feasible, the currently suggested expansion
{ std::forward<Args>(args)... }needs to be replaced by
{ static_cast<T>(std::forward<Args>(args))... }which is safe, because we already ensure convertibility via the element-wise Convertible<Args, T> requirement. Some other fixes are necessary: The ValueType requirement for the function parameters is invalid, because all lvalue arguments will deduce to an lvalue-reference, thereby no longer satisfying this requirement.
The suggested simplification is to provide a default-computed effective type for the result array based on common_type and decay, in unconstrained form:
template<typename... Args> array<typename decay<typename common_type<Args...>::type>::type, sizeof...(Args)> make_array(Args&&... args);The approach used below is similar to that of make_pair and make_tuple using a symbol C to represent the decayed common type [Note: Special handling of reference_wrapper types is intentionally not provided, because our target has so satisfy ValueType, thus under the revised proposal only an all-reference_wrapper-arguments would be well-formed and an array of reference_wrapper will be constructed]. I do currently not suggest to add new concepts reflecting decay and common_type, but an implementor will need something like this to succeed. Note that we use a similar fuzziness for make_pair and make_tuple currently. This fuzziness is not related to the currently missing Constructible<Vi, Ti&&> requirement for those functions. The following proposal fixes that miss for make_array. If the corresponding C type deduction is explicitly wanted for standardization, here the implementation
auto concept DC<typename... T> { typename type = typename decay<typename common_type<T...>::type>::type; }where C is identical to DC<Args...>::type in the proposed resolution below.
I intentionally added no further type relation between type and the concept template parameters, but instead added this requirement below to make the specification as transparent as possible. As written this concept is satisfied, if the corresponding associated type exists.
Suggested Resolution:
Add to the array synopsis in 23.3 [sequences]:
template<ReferentType... Args> requires ValueType<C> && IdentityOf<Args> && Constructible<C, Args&&>... array<C, sizeof...(Args)> make_array(Args&&... args);Append after 23.3.2.9 [array.tuple] Tuple interface to class template array the following new section:
23.4.1.7 Array creation functions [array.creation]
template<ReferentType... Args> requires ValueType<C> && IdentityOf<Args> && Constructible<C, Args&&>... array<C, sizeof...(Args)> make_array(Args&&... args);Let C be decay<common_type<Args...>::type>::type.
Returns: an array<C, sizeof...(Args)> initialized with { static_cast<C>(std::forward<Args>(args))... }.
[ 2009-07 Frankfurt: ]
The proposed resolution uses concepts.
Daniel to rewrite the proposed resolution.
Leave Open.
[ 2009-07-25 Daniel provides rewritten proposed resolution. ]
[ 2009-10 Santa Cruz: ]
Argument for NAD future: everything about this could be added on. This does not require changes to the existing text.
Proposed resolution:
Add to the array synopsis in 23.3 [sequences]:
template<class... Args> array<CT, sizeof...(Args)> make_array(Args&&... args);
Append after 23.3.2.9 [array.tuple] "Tuple interface to class template array" the following new section:
XX.X.X.X Array creation functions [array.creation]
template<class... Args> array<CT, sizeof...(Args)> make_array(Args&&... args)Let CT be decay<common_type<Args...>::type>::type.
Returns: An array<CT, sizeof...(Args)> initialized with { static_cast<CT>(std::forward<Args>(args))... }.
[Example:
int i = 0; int& ri = i; make_array(42u, i, 2.78, ri);returns an array of type
array<double, 4>—end example]
Section: 17 [library] Status: LEWG Submitter: Martin Sebor Opened: 2008-08-23 Last modified: 2015-04-08
View other active issues in [library].
View all other issues in [library].
View all issues with LEWG status.
Discussion:
Recent changes to the working draft have introduced a gratuitous inconsistency with the C++ 2003 version of the specification with respect to exception guarantees provided by standard functions. While the C++ 2003 standard consistenly uses the empty exception specification, throw(), to declare functions that are guaranteed not to throw exceptions, the current working draft contains a number of "Throws: Nothing." clause to specify essentially the same requirement. The difference between the two approaches is that the former specifies the behavior of programs that violate the requirement (std::unexpected() is called) while the latter leaves the behavior undefined.
A survey of the working draft reveals that there are a total of 209 occurrences of throw() in the library portion of the spec, the majority in clause 18, a couple (literally) in 19, a handful in 20, a bunch in 22, four in 24, one in 27, and about a dozen in D.9.
There are also 203 occurrences of "Throws: Nothing." scattered throughout the spec.
While sometimes there are good reasons to use the "Throws: Nothing." approach rather than making use of throw(), these reasons do not apply in most of the cases where this new clause has been introduced and the empty exception specification would be a better approach.
First, functions declared with the empty exception specification permit compilers to generate better code for calls to such functions. In some cases, the compiler might even be able to eliminate whole chunks of user-written code when instantiating a generic template on a type whose operations invoked from the template specialization are known not to throw. The prototypical example are the std::uninitialized_copy() and std::uninitialized_fill() algorithms where the entire catch(...) block can be optimized away.
For example, given the following definition of the std::uninitialized_copy function template and a user-defined type SomeType:
template <class InputIterator, class ForwardIterator>
ForwardIterator
uninitialized_copy (InputIterator first, InputIterator last, ForwardIterator res)
{
typedef iterator_traits<ForwardIterator>::value_type ValueType;
ForwardIterator start = res;
try {
for (; first != last; ++first, ++res)
::new (&*res) ValueType (*first);
}
catch (...) {
for (; start != res; --start)
(&*start)->~ValueType ();
throw;
}
return res;
}
struct SomeType {
SomeType (const SomeType&) throw ();
}
compilers are able to emit the following efficient specialization of std::uninitialized_copy<const SomeType*, SomeType*> (note that the catch block has been optimized away):
template <> SomeType*
uninitialized_copy (const SomeType *first, const SomeType *last, SomeType *res)
{
for (; first != last; ++first, ++res)
::new (res) SomeType (*first);
return res;
}
Another general example is default constructors which, when decorated with throw(), allow the compiler to eliminate the implicit try and catch blocks that it otherwise must emit around each the invocation of the constructor in new-expressions.
For example, given the following definitions of class MayThrow and WontThrow and the two statements below:
struct MayThrow {
MayThrow ();
};
struct WontThrow {
WontThrow () throw ();
};
MayThrow *a = new MayThrow [N];
WontThrow *b = new WontThrow [N];
the compiler generates the following code for the first statement:
MayThrow *a;
{
MayThrow *first = operator new[] (N * sizeof (*a));
MayThrow *last = first + N;
MayThrow *next = first;
try {
for ( ; next != last; ++next)
new (next) MayThrow;
}
catch (...) {
for ( ; first != first; --next)
next->~MayThrow ();
operator delete[] (first);
throw;
}
a = first;
}
but it is can generate much more compact code for the second statement:
WontThrow *b = operator new[] (N * sizeof (*b)); WontThrow *last = b + N; for (WontThrow *next = b; next != last; ++next) new (next) WontThrow;
Second, in order for users to get the maximum benefit out of the new std::has_nothrow_xxx traits when using standard library types it will be important for implementations to decorate all non throwing copy constructors and assignment operators with throw(). Note that while an optimizer may be able to tell whether a function without an explicit exception specification can throw or not based on its definition, it can only do so when it can see the source code of the definition. When it can't it must assume that the function may throw. To prevent violating the One Definition Rule, the std::has_nothrow_xxx trait must return the most pessimistic guess across all translation units in the program, meaning that std::has_nothrow_xxx<T>::value must evaluate to false for any T whose xxx (where xxx is default or copy ctor, or assignment operator) is defined out-of-line.
Counterarguments:
During the discussion of this issue on c++std-lib@accu.org (starting with post c++std-lib-21950) the following arguments in favor of the "Throws: Nothing." style have been made.
The answer to point (1) above is that implementers can (and some have) declare functions with throw() to indicate to the compiler that calls to the function can safely be assumed not to throw in order to allow it to generate efficient code at the call site without also having to define the functions the same way and causing the compiler to generate suboptimal code for the function definition. That is, the function is declared with throw() in a header but it's defined without it in the source file. The throw() declaration is suppressed when compiling the definition to avoid compiler errors. This technique, while strictly speaking no permitted by the language, is safe and has been employed in practice. For example, the GNU C library takes this approach. Microsoft Visual C++ takes a similar approach by simply assuming that no function with C language linkage can throw an exception unless it's explicitly declared to do so using the language extension throw(...).
Our answer to point (2) above is that there is no existing practice where C++ Standard Library implementers have opted to make use of the proprietary mechanisms to declare functions that don't throw. The language provides a mechanism specifically designed for this purpose. Avoiding its use in the specification itself in favor of proprietary mechanisms defeats the purpose of the feature. In addition, making use of the empty exception specification inconsistently, in some areas of the standard, while conspicuously avoiding it and making use of the "Throws: Nothing." form in others is confusing to users.
The answer to point (3) is simply to exercise caution when declaring functions and especially function templates with the empty exception specification. Functions that required not to throw but that may call back into user code are poor candidates for the empty exception specification and should instead be specified using "Throws: Nothing." clause.
[ 2009-07 Frankfurt ]
We need someone to do an extensive review.
NAD Future.
Proposed resolution:
We propose two possible solutions. Our recommendation is to adopt Option 1 below.
Option 1:
Except for functions or function templates that make calls back to user-defined functions that may not be declared throw() replace all occurrences of the "Throws: Nothing." clause with the empty exception specification. Functions that are required not to throw but that make calls back to user code should be specified to "Throw: Nothing."
Option 2:
For consistency, replace all occurrences of the empty exception specification with a "Throws: Nothing." clause.
Section: 20.8.1.2.5 [unique.ptr.single.modifiers] Status: LEWG Submitter: Alisdair Meredith Opened: 2008-11-27 Last modified: 2015-04-08
View all other issues in [unique.ptr.single.modifiers].
View all issues with LEWG status.
Discussion:
If we are supporting stateful deleters, we need an overload for reset that takes a deleter as well.
void reset( pointer p, deleter_type d);
We probably need two overloads to support move-only deleters, and this sounds uncomfortably like the two constructors I have been ignoring for now...
[ Batavia (2009-05): ]
Howard comments that we have the functionality via move-assigment.
Move to Open.
[ 2009-10 Santa Cruz: ]
Mark as NAD Future.
Proposed resolution:
Section: 20.12.7 [time.clock] Status: LEWG Submitter: Beman Dawes Opened: 2008-11-24 Last modified: 2015-04-08
View all issues with LEWG status.
Discussion:
Each of the three clocks specified in Clocks 20.12.7 [time.clock] provides the member function:
static time_point now();
The semantics specified by Clock requirements 20.12.3 [time.clock.req] make no mention of error handling. Thus the function may throw bad_alloc or an implementation-defined exception (17.6.5.12 [res.on.exception.handling] paragraph 4).
Some implementations of these functions on POSIX, Windows, and presumably on other operating systems, may fail in ways only detectable at runtime. Some failures on Windows are due to supporting chipset errata and can even occur after successful calls to a clock's now() function.
These functions are used in cases where exceptions are not appropriate or where the specifics of the exception or cause of error need to be available to the user. See N2828, Library Support for hybrid error handling (Rev 1), for more specific discussion of use cases. Thus some change in the interface of now is required.
The proposed resolution has been implemented in the Boost version of the chrono library. No problems were encountered.
[ Batavia (2009-05): ]
We recommend this issue be deferred until the next Committee Draft has been issued and the prerequisite paper has been accepted.
Move to Open.
[ 2009-10 Santa Cruz: ]
Mark as NAD future. Too late to make this change without having already accepted the hybrid error handling proposal.
Proposed resolution:
Accept the proposed wording of N2828, Library Support for hybrid error handling (Rev 1).
Change Clock requirements 20.12.3 [time.clock.req] as indicated:
-2- In Table 55 C1 and C2 denote clock types. t1 and t2 are values returned by C1::now() where the call returning t1 happens before (1.10) the call returning t2 and both of these calls happen before C1::time_point::max(). ec denotes an object of type error_code (19.5.2.1 [syserr.errcode.overview]).
Table 55 — Clock requirements Expression Return type Operational semantics ... ... ... C1::now() C1::time_point Returns a time_point object representing the current point in time. C1::now(ec) C1::time_point Returns a time_point object representing the current point in time.
Change class system_clock 20.12.7.1 [time.clock.system] as indicated:
static time_point now(error_code& ec=throws());
Change class monotonic_clock X [time.clock.monotonic] as indicated:
static time_point now(error_code& ec=throws());
Change class high_resolution_clock 20.12.7.3 [time.clock.hires] as indicated:
static time_point now(error_code& ec=throws());
Section: 30.4.1 [thread.mutex.requirements] Status: LEWG Submitter: Pete Becker Opened: 2008-12-05 Last modified: 2015-04-08
View other active issues in [thread.mutex.requirements].
View all other issues in [thread.mutex.requirements].
View all issues with LEWG status.
Duplicate of: 961
Discussion:
30.4.1 [thread.mutex.requirements] describes the requirements for a type to be a "Mutex type". A Mutex type can be used as the template argument for the Lock type that's passed to condition_variable_any::wait (although Lock seems like the wrong name here, since Lock is given a different formal meaning in 30.4.2 [thread.lock]) and, although the WD doesn't quite say so, as the template argument for lock_guard and unique_lock.
The requirements for a Mutex type include:
Also, a Mutex type "shall not be copyable nor movable".
The latter requirement seems completely irrelevant, and the three requirements on return types are tighter than they need to be. For example, there's no reason that lock_guard can't be instantiated with a type that's copyable. The rule is, in fact, that lock_guard, etc. won't try to copy objects of that type. That's a constraint on locks, not on mutexes. Similarly, the requirements for void return types are unnecessary; the rule is, in fact, that lock_guard, etc. won't use any returned value. And with the return type of bool, the requirement should be that the return type is convertible to bool.
[ Summit: ]
Move to open. Related to conceptualization and should probably be tackled as part of that.
- The intention is not only to place a constraint on what types such as lock_guard may do with mutex types, but on what any code, including user code, may do with mutex types. Thus the constraints as they are apply to the mutex types themselves, not the current users of mutex types in the standard.
- This is a low priority issue; the wording as it is may be overly restrictive but this may not be a real issue.
[ Post Summit Anthony adds: ]
Section 30.4.1 [thread.mutex.requirements] conflates the requirements on a generic Mutex type (including user-supplied mutexes) with the requirements placed on the standard-supplied mutex types in an attempt to group everything together and save space.
When applying concepts to chapter 30, I suggest that the concepts Lockable and TimedLockable embody the requirements for *use* of a mutex type as required by unique_lock/lock_guard/condition_variable_any. These should be relaxed as Pete describes in the issue. The existing words in 30.4.1 [thread.mutex.requirements] are requirements on all of std::mutex, std::timed_mutex, std::recursive_mutex and std::recursive_timed_mutex, and should be rephrased as such.
Proposed resolution:
Section: 30.4.1 [thread.mutex.requirements] Status: LEWG Submitter: Pete Becker Opened: 2009-01-07 Last modified: 2015-04-08
View other active issues in [thread.mutex.requirements].
View all other issues in [thread.mutex.requirements].
View all issues with LEWG status.
Duplicate of: 936
Discussion:
30.4.1 [thread.mutex.requirements] describes required member functions of mutex types, and requires that they throw exceptions under certain circumstances. This is overspecified. User-defined types can abort on such errors without affecting the operation of templates supplied by standard-library.
[ Summit: ]
Move to open. Related to conceptualization and should probably be tackled as part of that.
[ 2009-10 Santa Cruz: ]
Would be OK to leave it as is for time constraints, could loosen later.
Mark as NAD Future.
Proposed resolution:
Section: 20.9.13 [unord.hash] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-03-11 Last modified: 2015-04-08
View other active issues in [unord.hash].
View all other issues in [unord.hash].
View all issues with LEWG status.
Discussion:
Addresses UK 208 [CD1]
std::hash should be implemented for much more of the standard library. In particular for pair, tuple and all the standard containers.
Proposed resolution:
Section: 20.8.2.2 [util.smartptr.shared] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-03-11 Last modified: 2015-04-08
View other active issues in [util.smartptr.shared].
View all other issues in [util.smartptr.shared].
View all issues with LEWG status.
Discussion:
Addresses US 78 [CD1]
There is presently no way to convert directly from a shared_ptr to a unique_ptr. Add an interface that performs the conversion.
[ Summit: ]
We look forward to a paper on this topic. We recommend no action until a paper is available. We believe that the shared pointer must use the default deleter for the conversion to succeed.
[ Peter Dimov adds: ]
This is basically a request for shared_ptr<>::release in disguise, with all the associated problems. Not a good idea.
[ 2009-07 post-Frankfurt: ]
The rationale for the omission of a release() member function from shared_ptr is given in: http://www.boost.org/doc/libs/1_39_0/libs/smart_ptr/shared_ptr.htm
The implementation of such a member is non-trivial (and maybe impossible), because it would need to account for the deleter.
[ 2009-07-26 Howard sets to Tentatively NAD Future. ]
I took an online poll and got 3 votes for NAD and 3 for NAD Future. Personally I prefer NAD Future as this does refer to an extension that could conceivably be considered beyond C++0X.
However such an extension would need to solve a couple of problems:
- What is the interface for such a conversion when the shared_ptr does not have unique ownership? Throw an exception? Create a null unique_ptr? Undefined behavior?
How does one handle custom deleters given to the shared_ptr constructor?
I do not believe it is possible to implement a general answer to this question. The shared_ptr deleter is a run time (or construction time) characteristic. The unique_ptr deleter is a compile time characteristic. In general one can not know to what type of unqiue_ptr you are converting to.
One answer is for the user of the conversion to specify the deleter type and perhaps throw an exception if the specification turns out to be incorrect.
Another answer is for the conversion to only be valid when the underlying deleter is default_delete. We would probalby need to specify that this is indeed the underlying deleter of a shared_ptr when a custom deleter is not given in the constructor.
At any rate, there are non-trivial design issues which would need to be implemented and tested in the field for usability prior to standardization.
[ 2009 Santa Cruz: ]
Moved to NAD Future.
Proposed resolution:
Section: 23.2.4 [associative.reqmts] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-03-12 Last modified: 2015-04-08
View other active issues in [associative.reqmts].
View all other issues in [associative.reqmts].
View all issues with LEWG status.
Discussion:
Addresses UK 239 [CD1]
It is not possible to take a move-only key out of an unordered container, such as (multi)set or (multi)map, or the new unordered containers.
Add below a.erase(q), a.extract(q), with the following notation:
a.extract(q)>, Return type pair<key, iterator> Extracts the element pointed to by q and erases it from the set. Returns a pair containing the value pointed to by q and an iterator pointing to the element immediately following q prior to the element being erased. If no such element exists,returns a.end().
[ Summit: ]
We look forward to a paper on this topic. We recommend no action until a paper is available. The paper would need to address exception safety.
[ Post Summit Alisdair adds: ]
Would value_type be a better return type than key_type?
[ 2009-07 post-Frankfurt: ]
Leave Open. Alisdair to contact Chris Jefferson about this.
[ 2009-09-20 Howard adds: ]
See the 2009-09-19 comment of 839 for an API which accomplishes this functionality and also addresses several other use cases which this proposal does not.
[ 2009-10 Santa Cruz: ]
Mark as NAD Future. No consensus to make the change at this time.
Proposed resolution:
In 23.2.4 [associative.reqmts] Table 85, add:
Table 85 -- Associative container requirements (in addition to container) Expression Return type Assertion/note
pre-/post-conditionComplexity a.erase(q) ... ... ... a.extract(q) pair<key_type, iterator> Extracts the element pointed to by q and erases it from the set. Returns a pair containing the value pointed to by q and an iterator pointing to the element immediately following q prior to the element being erased. If no such element exists, returns a.end(). amortized constant
In 23.2.5 [unord.req] Table 87, add:
Table 87 -- Unordered associative container requirements (in addition to container) Expression Return type Assertion/note
pre-/post-conditionComplexity a.erase(q) ... ... ... a.extract(q) pair<key_type, iterator> Extracts the element pointed to by q and erases it from the set. Returns a pair containing the value pointed to by q and an iterator pointing to the element immediately following q prior to the element being erased. If no such element exists, returns a.end(). amortized constant
Section: 24.5.1.3.5 [reverse.iter.opref] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-03-12 Last modified: 2015-04-08
View all other issues in [reverse.iter.opref].
View all issues with LEWG status.
Discussion:
Addresses UK 281 [CD1]
The current specification for return value for reverse_iterator::operator-> will always be a true pointer type, but reverse_iterator supports proxy iterators where the pointer type may be some kind of 'smart pointer'.
[ Summit: ]
move_iterator avoids this problem by returning a value of the wrapped Iterator type. study group formed to come up with a suggested resolution.
move_iterator solution shown in proposed wording.
[ 2009-07 post-Frankfurt: ]
Howard to deconceptize. Move to Review after that happens.
[ 2009-08-01 Howard deconceptized: ]
[ 2009-10 Santa Cruz: ]
We can't think of any reason we can't just define reverse iterator's pointer types to be the same as the underlying iterator's pointer type, and get it by calling the right arrow directly.
Here is the proposed wording that was replaced:
template <class Iterator> class reverse_iterator { ... typedeftypename iterator_traits<Iterator>::pointerpointer;Change 24.5.1.3.5 [reverse.iter.opref]:
pointer operator->() const;Returns:
&(operator*());this->tmp = current; --this->tmp; return this->tmp;
[ 2010-03-03 Daniel opens: ]
- There is a minor problem with the exposition-only declaration of the private member deref_tmp which is modified in a const member function (and the same problem occurs in the specification of operator*). The fix is to make it a mutable member.
The more severe problem is that the resolution for some reasons does not explain in the rationale why it was decided to differ from the suggested fix (using deref_tmp instead of tmp) in the [ 2009-10 Santa Cruz] comment:
this->deref_tmp = current; --this->deref_tmp; return this->deref_tmp;combined with the change of
typedef typename iterator_traits<Iterator>::pointer pointer;to
typedef Iterator pointer;The problem of the agreed on wording is that the following rather typical example, that compiled with the wording before 1052 had been applied, won't compile anymore:
#include <iterator> #include <utility> int main() { typedef std::pair<int, double> P; P op; std::reverse_iterator<P*> ri(&op + 1); ri->first; // Error }Comeau online returns (if a correspondingly changed reverse_iterator is used):
"error: expression must have class type return deref_tmp.operator->(); ^ detected during instantiation of "Iterator reverse_iterator<Iterator>::operator->() const [with Iterator=std::pair<int, double> *]""Thus the change will break valid, existing code based on std::reverse_iterator.
IMO the suggestion proposed in the comment is a necessary fix, which harmonizes with the similar specification of std::move_iterator and properly reflects the recursive nature of the evaluation of operator-> overloads.
Suggested resolution:
In the class template reverse_iterator synopsis of 24.5.1.1 [reverse.iterator] change as indicated:
namespace std { template <class Iterator> class reverse_iterator : public iterator<typename iterator_traits<Iterator>::iterator_category, typename iterator_traits<Iterator>::value_type, typename iterator_traits<Iterator>::difference_type,typename iterator_traits<Iterator>::pointer, typename iterator_traits<Iterator>::reference> { public: [..] typedeftypename iterator_traits<Iterator>::pointerpointer; [..] protected: Iterator current; private: mutable Iterator deref_tmp; // exposition only };- Change 24.5.1.3.5 [reverse.iter.opref]/1 as indicated:
pointer operator->() const;1
ReturnsEffects:&(operator*()).deref_tmp = current; --deref_tmp; return deref_tmp;
[ 2010 Pittsburgh: ]
We prefer to make to use a local variable instead of deref_tmp within operator->(). And although this means that the mutable change is no longer needed, we prefer to keep it because it is needed for operator*() anyway.
Here is the proposed wording that was replaced:
Change 24.5.1.3.5 [reverse.iter.opref]:
pointer operator->() const;Returns:
&(operator*());deref_tmp = current; --deref_tmp; return deref_tmp::operator->();
[ 2010-03-10 Howard adds: ]
Here are three tests that the current proposed wording passes, and no other solution I've seen passes all three:
Proxy pointer support:
#include <iterator> #include <cassert> struct X { int m; }; X x; struct IterX { typedef std::bidirectional_iterator_tag iterator_category; typedef X& reference; struct pointer { pointer(X& v) : value(v) {} X& value; X* operator->() const {return &value;} }; typedef std::ptrdiff_t difference_type; typedef X value_type; // additional iterator requirements not important for this issue reference operator*() const { return x; } pointer operator->() const { return pointer(x); } IterX& operator--() {return *this;} }; int main() { std::reverse_iterator<IterX> ix; assert(&ix->m == &(*ix).m); }Raw pointer support:
#include <iterator> #include <utility> int main() { typedef std::pair<int, double> P; P op; std::reverse_iterator<P*> ri(&op + 1); ri->first; // Error }Caching iterator support:
#include <iterator> #include <cassert> struct X { int m; }; struct IterX { typedef std::bidirectional_iterator_tag iterator_category; typedef X& reference; typedef X* pointer; typedef std::ptrdiff_t difference_type; typedef X value_type; // additional iterator requirements not important for this issue reference operator*() const { return value; } pointer operator->() const { return &value; } IterX& operator--() {return *this;} private: mutable X value; }; int main() { std::reverse_iterator<IterX> ix; assert(&ix->m == &(*ix).m); }
[ 2010 Pittsburgh: ]
Moved to NAD Future, rationale added.
Rationale:
The LWG did not reach a consensus for a change to the WP.
Proposed resolution:
In the class template reverse_iterator synopsis of 24.5.1.1 [reverse.iterator] change as indicated:
namespace std {
template <class Iterator>
class reverse_iterator : public
iterator<typename iterator_traits<Iterator>::iterator_category,
typename iterator_traits<Iterator>::value_type,
typename iterator_traits<Iterator>::difference_type,
typename iterator_traits<Iterator&>::pointer,
typename iterator_traits<Iterator>::reference> {
public:
[..]
typedef typename iterator_traits<Iterator&>::pointer pointer;
[..]
protected:
Iterator current;
private:
mutable Iterator deref_tmp; // exposition only
};
pointer operator->() const;1
ReturnsEffects:&(operator*()).deref_tmp = current; --deref_tmp; return deref_tmp;
Section: 25 [algorithms] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-03-12 Last modified: 2015-04-08
View other active issues in [algorithms].
View all other issues in [algorithms].
View all issues with LEWG status.
Discussion:
Addresses UK 295 [CD1]
There is a level of redundancy in the library specification for many algorithms that can be eliminated with the combination of concepts and default parameters for function templates. Eliminating redundancy simplified specification and reduces the risk of introducing accidental inconsistencies.
Proposed resolution: Adopt N2743.
[ Summit: ]
NAD, this change would break code that takes the address of an algorithm.
[ Post Summit Alisdair adds: ]
Request 'Open'. The issues in the paper go beyond just reducing the number of signatures, but cover unifying the idea of the ordering operation used by algorithms, containers and other library components. At least, it takes a first pass at the problem.
For me (personally) that was the more important part of the paper, and not clearly addressed by the Summit resolution.
[ 2009-10 Santa Cruz: ]
Too inventive, too late, would really need a paper. Moved to NAD Future.
Proposed resolution:
Section: 20.6 [template.bitset] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-05-06 Last modified: 2015-04-08
View other active issues in [template.bitset].
View all other issues in [template.bitset].
View all issues with LEWG status.
Discussion:
std::bitset is a homogeneous container-like sequence of bits, yet it does not model the Range concept so cannot be used with the new for-loop syntax. It is the only such type in the library that does NOT support the new for loop.
The obvious reason is that bitset does not support iterators.
At least two reasonable solutions are available:
The latter will still need some kind of iterator-like adapter for bitset, but gives implementers greater freedom on the details. E.g. begin/end return some type that simply invokes operator[] on the object it wraps, and increments its index on operator++. A vendor can settle for InputIterator support, rather than wrapping up a full RandomAccessIterator.
I have a mild preference for option (ii) as I think it is less work to specify at this stage of the process, although (i) is probably more useful in the long run.
Hmm, my wording looks a little woolly, as it does not say what the element type of the range is. Do I get a range of bool, bitset<N>::reference, or something else entirely?
I guess most users will assume the behaviour of reference, but expect to work with bool. Bool is OK for read-only traversal, but you really need to take a reference to a bitset::reference if you want to write back.
[ Batavia (2009-05): ]
Move to Open. We further recommend this be deferred until after the next Committee Draft.
[ 2009-05-25 Alisdair adds: ]
I just stumbled over the Range concept_map for valarray and this should probably set the precedent on how to write the wording.
[ Howard: I've replaced the proposed wording with Alisdair's suggestion. ]
[ 2009-07-24 Daniel modifies the proposed wording for non-concepts. ]
[ 2009-10 post-Santa Cruz: ]
Mark as Tentatively NAD Future due to the loss of concepts.
Rationale:
All concepts-related text has been removed from the draft.
Proposed resolution:
Modify the section 20.6 [template.bitset] <bitset> synopsis by adding the following at the end of the synopsis:
// XX.X.X bitset range access [bitset.range] template<size_t N> unspecified-1 begin(bitset<N>&); template<size_t N> unspecified-2 begin(const bitset<N>&); template<size_t N> unspecified-1 end(bitset<N>&); template<size_t N> unspecified-2 end(const bitset<N>&);
Add a new section "bitset range access" [bitset.range] after the current section 20.6.4 [bitset.operators] with the following series of paragraphs:
1. In the begin and end function templates that follow, unspecified-1 is a type that meets the requirements of a mutable random access iterator (24.2.7 [random.access.iterators]) whose value_type is bool and whose reference type is bitset<N>::reference. unspecified-2 is a type that meets the requirements of a constant random access iterator (24.2.7 [random.access.iterators]) whose value_type is bool and whose reference type is bool.
template<size_t N> unspecified-1 begin(bitset<N>&); template<size_t N> unspecified-2 begin(const bitset<N>&);2. Returns: an iterator referencing the first bit in the bitset.
template<size_t N> unspecified-1 end(bitset<N>&); template<size_t N> unspecified-2 end(const bitset<N>&);3. Returns: an iterator referencing one past the last bit in the bitset.
Section: 20.10 [meta] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-05-23 Last modified: 2015-04-08
View other active issues in [meta].
View all other issues in [meta].
View all issues with LEWG status.
Discussion:
Sometimes it is necessary to remove all qualifiers from a type before passing on to a further API. A good example would be calling the tuple query APIs tuple_size or tuple_element with a deduced type inside a function template. If the deduced type is cv-qualified or a reference then the call will fail. The solution is to chain calls to remove_cv<remove_reference<T>::type>::type, and note that the order matters.
Suggest it would be helpful to add a new type trait, remove_all, that removes all top-level qualifiers from a type i.e. cv-qualification and any references. Define the term in such a way that if additional qualifiers are added to the language, then remove_all is defined as stripping those as well.
[ 2009-10-14 Daniel adds: ]
remove_all seems too generic, a possible alternative matching the current naming style could be remove_cv_reference or remove_reference_cv. It should also be considered whether this trait should also remove 'extents', or pointer 'decorations'. Especially if the latter situations are considered as well, it might be easier to chose the name not in terms of what it removes (which might be a lot), but in terms of it creates. In this case I could think of e.g. extract_value_type.
[ 2009-10 Santa Cruz: ]
NAD Future.
Proposed resolution:
Section: 20.11.4 [ratio.arithmetic] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-05-25 Last modified: 2015-04-08
View all other issues in [ratio.arithmetic].
View all issues with LEWG status.
Discussion:
Both add and multiply could sensibly be called with more than two arguments. The variadic template facility makes such declarations simple, and is likely to be frequently wrapped by end users if we do not supply the variant ourselves.
We deliberately ignore divide at this point as it is not transitive. Likewise, subtract places special meaning on the first argument so I do not suggest extending that immediately. Both could be supported with analogous wording to that for add/multiply below.
Note that the proposed resolution is potentially incompatible with that proposed for 921, although the addition of the typedef to ratio would be equally useful.
[ 2009-10-30 Alisdair adds: ]
The consensus of the group when we reviewed this in Santa Cruz was that 921 would proceed to Ready as planned, and the multi-paramater add/multiply templates should be renamed as ratio_sum and ratio_product to avoid the problem mixing template aliases with partial specializations.
It was also suggested to close this issue as NAD Future as it does not correspond directly to any NB comment. NBs are free to submit a specific comment (and re-open) in CD2 though.
Walter Brown also had concerns on better directing the order of evaluation to avoid overflows if we do proceed for 0x rather than TR1, so wording may not be complete yet.
[ Alisdair updates wording. ]
[ 2009-10-30 Howard: ]
Moved to Tentatively NAD Future after 5 positive votes on c++std-lib.
Rationale:
Does not have sufficient support at this time. May wish to reconsider for a future standard.
Proposed resolution:
Add the following type traits to p3 20.11 [ratio]
// ratio arithmetic template <class R1, class R2> struct ratio_add; template <class R1, class R2> struct ratio_subtract; template <class R1, class R2> struct ratio_multiply; template <class R1, class R2> struct ratio_divide; template <class R1, class ... RList> struct ratio_sum; template <class R1, class ... RList> struct ratio_product;
after 20.11.4 [ratio.arithmetic] p1: add
template <class R1, class ... RList> struct ratio_sum; // declared, never defined template <class R1> struct ratio_sum<R1> : R1 {};Requires: R1 is a specialization of class template ratio
template <class R1, class R2, class ... RList> struct ratio_sum<R1, R2, RList...> : ratio_add< R1, ratio_sum<R2, RList...>> { };Requires: R1 and each element in parmater pack RList is a specialization of class template ratio
after 20.11.4 [ratio.arithmetic] p3: add
template <class R1, class ... RList> struct ratio_product; // declared, never defined template <class R1> struct ratio_product<R1> : R1 {};Requires: R1 is a specialization of class template ratio
template <class R1, class R2, class ... RList> struct ratio_sum<R1, R2, RList...> : ratio_add< R1, ratio_product<R2, RList...>> { };Requires: R1 and each element in parmater pack RList is a specialization of class template ratio
Section: 27.9.1.14 [fstream] Status: LEWG Submitter: LWG Opened: 2009-06-28 Last modified: 2015-04-08
View all issues with LEWG status.
Discussion:
Addresses JP 73
Description
It is a problem from C++98, fstream cannot appoint a filename of wide character string(const wchar_t and const wstring&).
Suggestion
Add interface corresponding to wchar_t, char16_t and char32_t.
[ 2009-07-01 Alisdair notes that this is a duplicate of 454 which has more in-depth rationale. ]
[ 2009-09-21 Daniel adds: ]
I suggest to mark this issue as NAD Future with the intend to solve the issue with a single file path c'tor template assuming a provision of a TR2 filesystem library.
[ 2009 Santa Cruz: ]
NAD Future. This is a duplicate of 454.
Proposed resolution:
Section: 26.4 [complex.numbers] Status: LEWG Submitter: LWG Opened: 2009-06-28 Last modified: 2015-04-08
View other active issues in [complex.numbers].
View all other issues in [complex.numbers].
View all issues with LEWG status.
Discussion:
Addresses FR 35
Description
Instantiations of the class template complex<> have to be allowed for integral types, to reflect existing practice and ISO standards (LIA-III).
Suggestion
[ 2009-10-26 Proposed wording in N3002. ]
[ 2010 Pittsburgh: ]
Moved to NAD Future. Rationale added.
Rationale:
There is no consensus for making this change at this time.
Proposed resolution:
Adopt N3002.
Section: 22.4.2.1.2 [facet.num.get.virtuals] Status: Ready Submitter: Cosmin Truta Opened: 2009-07-04 Last modified: 2015-05-22
View other active issues in [facet.num.get.virtuals].
View all other issues in [facet.num.get.virtuals].
View all issues with Ready status.
Discussion:
As specified in the latest draft,
N2914,
num_get is still not fully compatible with the following C
functions: strtoul, strtoull,
strtof and
strtod.
In C, when conversion of a string to an unsigned integer type falls
outside the
representable range, strtoul and strtoull return
ULONG_MAX and ULLONG_MAX, respectively,
regardless
whether the input field represents a positive or a negative value.
On the other hand, the result of num_get conversion of
negative
values to unsigned integer types is zero. This raises a compatibility
issue.
Moreover, in C, when conversion of a string to a floating-point type falls
outside the representable range, strtof, strtod
and
strtold return ±HUGE_VALF,
±HUGE_VAL and ±HUGE_VALL, respectively.
On the other hand, the result of num_get conversion of such
out-of-range floating-point values results in the most positive/negative
representable value.
Although many C library implementations do implement HUGE_VAL
(etc.) as the highest representable (which is, usually, the infinity),
this isn't required by the C standard. The C library specification makes no
statement regarding the value of HUGE_VAL and friends, which
potentially raises the same compatibility issue as in the above case of
unsigned integers.
In addition, neither C nor C++ define symbolic constants for the maximum
representable floating-point values (they only do so only for the maximum
representable finite floating-point values), which raises a
usability
issue (it would be hard for the programmer to check the result of
num_get against overflow).
As such, we propose to adjust the specification of num_get to
closely follow the behavior of all of its underlying C functions.
[ 2010 Rapperswil: ]
Some concern that this is changing the specification for an existing C++03 function, but it was pointed out that this was underspecified as resolved by issue 23. This is clean-up for that issue in turn. Some concern that we are trying to solve the same problem in both clause 22 and 27.
Bill: There's a change here as to whether val is stored to in an error case.
Pablo: Don't think this changes whether val is stored to or not, but changes the value that is stored.
Bill: Remembers having skirmishes with customers and testers as to whether val is stored to, and the resolution was not to store in error cases.
Howard: Believes since C++03 we made a change to always store in overflow.
Everyone took some time to review the issue.
Pablo: C++98 definitely did not store any value during an error condition.
Dietmar: Depends on the question of what is considered an error, and whether overflow is an error or not, which was the crux of LWG 23.
Pablo: Yes, but given the "zero, if the conversion function fails to convert the entire field", we are requiring every error condition to store.
Bill: When did this happen?
Alisdair: One of the last two or three meetings.
Dietmar: To store a value in case of failure is a very bad idea.
Move to Open, needs more study.
[2011-03-24 Madrid meeting]
Move to deferred
[ 2011 Bloomington ]
The proposed wording looks good, no-one sure why this was held back before. Move to Review.
[2012,Kona]
Move to Open.
THe issues is what to do with -1. Should it match 'C' or do the "sane" thing. A fix here changes behavior, but is probably what we want.
Pablo to provide wording, with help from Howard.
[2015-05-06 Lenexa: Move to Ready]
STL: I like that this uses strtof, which I think is new in C99. that avoids truncation from using atof. I have another issue ...
MC: yes LWG 2403 (stof should call strtof)
PJP: the last line is horrible, you don't assign to err, you call setstate(ios_base::failbit). Ah, no, this is inside num_get so the caller does the setstate.
MC: we need all these words. are they the right words?
JW: I'd like to take a minute to check my impl. Technically this implies a change in behaviour (from always using strtold and checking the extracted floating point value, to using the right function). Oh, we already do exactly this.
MC: Move to Ready
6 in favor, none opposed, 1 abstention
Proposed resolution:
Change 22.4.2.1.2 [facet.num.get.virtuals] as follows:
Stage 3: The sequence of
chars accumulated in stage 2 (the field) is converted to a numeric value by the rules of one of the functions declared in the header<cstdlib>:
- For a signed integer value, the function
strtoll.- For an unsigned integer value, the function
strtoull.- For a
floatvalue, the functionstrtof.- For a
doublevalue, the functionstrtod.- For a
floating-pointlong doublevalue, the functionstrtold.The numeric value to be stored can be one of:
- zero, if the conversion function fails to convert the entire field.
ios_base::failbitis assigned toerr.- the most positive (or negative) representable value, if the field to be converted to a signed integer type represents a value too large positive (or negative) to be represented in
val.ios_base::failbitis assigned toerr.the most negative representable value or zero for an unsigned integer type, if the field represents a value too large negative to be represented inval.ios_base::failbitis assigned toerr.- the most positive representable value, if the field to be converted to an unsigned integer type represents a value that cannot be represented in
val.- the converted value, otherwise.
The resultant numeric value is stored in
val. If the conversion function fails to convert the entire field, or if the field represents a value outside the range of representable values,ios_base::failbitis assigned toerr.
Section: 17 [library] Status: Open Submitter: David Abrahams Opened: 2009-07-14 Last modified: 2015-04-08
View other active issues in [library].
View all other issues in [library].
View all issues with Open status.
Discussion:
Issue: The CopyConstructible requirements are wishy-washy. It requires that the copy is "equivalent" to the original, but "equivalent" is never defined.
I believe this to be an example of a more general lack of rigor around copy and assignment, although I haven't done the research to dig up all the instances.
It's a problem because if you don't know what CopyConstructible means, you also don't know what it means to copy a pair of CopyConstructible types. It doesn't prevent us from writing code, but it is a hole in our ability to understand the meaning of copy.
Furthermore, I'm pretty sure that vector's copy constructor doesn't require the elements to be EqualityComparable, so that table is actually referring to some ill-defined notion of equivalence when it uses ==.
[ 2009 Santa Cruz: ]
Move to "Open". Dave is right that this is a big issue. Paper D2987 ("Defining Move Special Member Functions", Bjarne Stroustrup and Lawrence Crowl) touches on this but does not solve it. This issue is discussed in Elements of Programming.
[ 2010 Rapperswil: ]
This issue is quite vague, so it is difficult to know if and when it has been resolved. John Lakos wrote a paper covering this area a while back, and there is a real interest in providing some sort of clean-up in the future. We need a more clearly draughted issues with an addressable set of concerns, ideally with a paper proposing a resolution, but for a future revision of the standard. Move to Tentatively NAD Future.
[ Moved to NAD Future at 2010-11 Batavia ]
Proposed resolution:
Section: 23.2.5 [unord.req] Status: Open Submitter: Pablo Halpern Opened: 2009-07-17 Last modified: 2015-04-08
View other active issues in [unord.req].
View all other issues in [unord.req].
View all issues with Open status.
Discussion:
When I look at the unordered_* constructors, I think the complexity is poorly described and does not follow the style of the rest of the standard.
The complexity for the default constructor is specified as constant. Actually, it is proportional to n, but there are no invocations of value_type constructors or other value_type operations.
For the iterator-based constructor the complexity should be:
Complexity: exactly n calls to construct value_type from InputIterator::value_type (where n = distance(f,l)). The number of calls to key_equal::operator() is proportional to n in the average case and n*n in the worst case.
[ 2010 Rapperswil: ]
Concern that the current wording may require O(1) where that cannot be delivered. We need to look at both the clause 23 requirements tables and the constructor description of each unordered container to be sure.
Howard suggests NAD Editorial as we updated the container requirement tables since this issue was written.
Daniel offers to look deeper, and hopefully produce wording addressing any outstanding concerns at the next meeting.
Move to Open.
[2011-02-26: Daniel provides wording]
I strongly suggest to clean-up the differences between requirement tables and individual specifications. In the usual way, the most specific specifications wins, which is in this case the wrong one. In regard to the concern expressed about missing DefaultConstructible requirements of the value type I disagree: The function argument n is no size-control parameter, but only some effective capacity parameter: No elements will be value-initialized by these constructors. The necessary requirement for the value type, EmplaceConstructible into *this, is already listed in Table 103 — Unordered associative container requirements. Another part of the proposed resolution is the fact that there is an inconsistency of the complexity counting when both a range and a bucket count is involved compared to constructions where only bucket counts are provided: E.g. the construction X a(n); has a complexity of n bucket allocations, but this part of the work is omitted for X a(i, j, n);, even though it is considerable larger (in the average case) for n ≫ distance(i, j).
[2011-03-24 Madrid meeting]
Move to deferred
[ 2011 Bloomington ]
The proposed wording looks good. Move to Review.
[2012, Kona]
Fix up some presentation issues with the wording, combining the big-O expressions into single expressions rather than the sum of two separate big-Os.
Strike "constant or linear", prefer "linear in the number of buckets". This allows for number of buckets being larger than requested n as well.
Default n to "unspecified" rather than "implementation-defined". It seems an un-necessary burden asking vendors to document a quantity that is easily determined through the public API of these classes.
Replace distance(f,l) with "number of elements in the range [f,l)"
Retain in Review with the updated wording
[2012, Portland: Move to Open]
The wording still does not call out Pablo's original concern, that the element constructor is called no more than N times, and that the N squared term applies to moves during rehash.
Inconsistent use of O(n)+O(N) vs. O(n+N), with a preference for the former.
AJM to update wording with a reference to "no more than N element constructor calls".
Matt concerned that calling out the O(n) requirements is noise, and dangerous noise in suggesting a precision we do not mean. The cost of constructing a bucket is very different to constructing an element of user-supplied type.
AJM notes that if there are multiple rehashes, the 'n' complexity is probably not linear.
Matt suggests back to Open, Pablo suggests potentially NAD if we keep revisitting without achieving a resolution.
Matt suggests complexity we are concerned with is the number of operations, such as constructing elements, moving nodes, and comparing/hashing keys. We are less concerned with constructing buckets, which are generally noise in this bigger picture.
[2015-01-29 Telecon]
AM: essentially correct, but do we want to complicate the spec?
HH: Pablo has given us permission to NAD it JM: when I look at the first change in the P/R I find it mildly disturbing that the existing wording says you have a constant time constructor with a single element even if your n is 10^6, so I think adding this change makes people aware there might be a large cost in initializing the hash table, even though it doesn't show up in user-visible constructions. HH: one way to avoid that problem is make the default ctor noexcept. Then the container isn't allowed to create an arbitrarily large hash table AM: but this is the constructor where the user provides n MC: happy with the changes, except I agree with the editorial recommendation to keep the two 𝒪s separate. JW: yes, the constant 'k' is different in 𝒪(n) and 𝒪(N) GR: do we want to talk about buckets at all JM: yes, good to highlight that bucket construction might be a significant cost HH: suggest we take the suggestion to split 𝒪(n+N) to 𝒪(n)+𝒪(N) and move to Tentatively Ready GR: 23.2.1p2 says all complexity requirements are stated solely in terms of the number of operations on the contained object, so we shouldn't be stating complexity in terms of the hash table initialization HH: channeling Pete, there's an implicit "unless otherwise specified" everywhere. VV: seem to be requesting modifications that render this not Tentatively Ready GR: I think it can't be T/R AM: make the editorial recommendation, consider fixing 23.2.1/3 to give us permission to state complexity in terms of bucket initialization HH: only set it to Review after we get new wording to review[2015-02 Cologne]
Update wording, revisit later.
Proposed resolution:
Modify the following rows in Table 103 — Unordered associative container requirements to add the explicit bucket allocation overhead of some constructions. As editorial recommendation it is suggested not to shorten the sum 𝒪(n) + 𝒪(N) to 𝒪(n + N), because two different work units are involved.
Table 103 — Unordered associative container requirements (in addition to container) Expression Return type Assertion/note pre-/post-condition Complexity … X(i, j, n, hf, eq)
X a(i, j, n, hf, eq)X …
Effects: Constructs an empty container with at least n
buckets, using hf as the hash function and eq as the key
equality predicate, and inserts elements from [i, j) into it.Average case 𝒪(n + N) (N is distance(i, j)),
worst case 𝒪(n) + 𝒪(N2)X(i, j, n, hf)
X a(i, j, n, hf)X …
Effects: Constructs an empty container with at least n
buckets, using hf as the hash function and key_equal() as the key
equality predicate, and inserts elements from [i, j) into it.Average case 𝒪(n + N) (N is distance(i, j)),
worst case 𝒪(n + N2)X(i, j, n)
X a(i, j, n)X …
Effects: Constructs an empty container with at least n
buckets, using hasher() as the hash function and key_equal() as the key
equality predicate, and inserts elements from [i, j) into it.Average case 𝒪(n + N) (N is distance(i, j)),
worst case 𝒪(n + N2)…
Modify 23.5.4.2 [unord.map.cnstr] p. 1-4 as indicated (The edits of p. 1 and p. 3 attempt to fix some editorial oversight.):
explicit unordered_map(size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());1 Effects: Constructs an empty unordered_map using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_map. max_load_factor() returns 1.0.2 Complexity:
ConstantLinear in the number of buckets.
template <class InputIterator> unordered_map(InputIterator f, InputIterator l, size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());3 Effects: Constructs an empty unordered_map using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_map. Then inserts elements from the range [f, l). max_load_factor() returns 1.0.4 Complexity:
Average case linear, worst case quadraticLinear in the number of buckets. In the average case linear in N and in the worst case quadratic in N to insert the elements, where N is equal to number of elements in the range [f,l).
Modify 23.5.5.2 [unord.multimap.cnstr] p. 1-4 as indicated (The edits of p. 1 and p. 3 attempt to fix some editorial oversight.):
explicit unordered_multimap(size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());1 Effects: Constructs an empty unordered_multimap using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_multimap. max_load_factor() returns 1.0.2 Complexity:
ConstantLinear in the number of buckets.
template <class InputIterator> unordered_multimap(InputIterator f, InputIterator l, size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());3 Effects: Constructs an empty unordered_multimap using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_multimap. Then inserts elements from the range [f, l). max_load_factor() returns 1.0.4 Complexity:
Average case linear, worst case quadraticLinear in the number of buckets. In the average case linear in N and in the worst case quadratic in N to insert the elements, where N is equal to number of elements in the range [f,l).
Modify 23.5.6.2 [unord.set.cnstr] p. 1-4 as indicated (The edits of p. 1 and p. 3 attempt to fix some editorial oversight.):
explicit unordered_set(size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());1 Effects: Constructs an empty unordered_set using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_set. max_load_factor() returns 1.0.2 Complexity:
ConstantLinear in the number of buckets.
template <class InputIterator> unordered_set(InputIterator f, InputIterator l, size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());3 Effects: Constructs an empty unordered_set using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_set. Then inserts elements from the range [f, l). max_load_factor() returns 1.0.4 Complexity:
Average case linear, worst case quadraticLinear in the number of buckets. In the average case linear in N and in the worst case quadratic in N to insert the elements, where N is equal to number of elements in the range [f,l).
Modify 23.5.7.2 [unord.multiset.cnstr] p. 1-4 as indicated (The edits of p. 1 and p. 3 attempt to fix some editorial oversight.):
explicit unordered_multiset(size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());1 Effects: Constructs an empty unordered_multiset using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_multiset. max_load_factor() returns 1.0.2 Complexity:
ConstantLinear in the number of buckets.
template <class InputIterator> unordered_multiset(InputIterator f, InputIterator l, size_type n = see below, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type());3 Effects: Constructs an empty unordered_multiset using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is unspecified
impldefdefault number of buckets in unordered_multiset. Then inserts elements from the range [f, l). max_load_factor() returns 1.0.4 Complexity:
Average case linear, worst case quadraticLinear in the number of buckets. In the average case linear in N and in the worst case quadratic in N to insert the elements, where N is equal to number of elements in the range [f,l).
Section: 23.3.6 [vector] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-07-29 Last modified: 2015-04-08
View all other issues in [vector].
View all issues with LEWG status.
Discussion:
Opened at Alisdair's request, steming from 96. Alisdair recommends NAD Future.
[ 2009-10 Santa Cruz: ]
NAD Future. We want a heap allocated bitset, but we don't have one today and don't have time to add one.
Proposed resolution:
Section: 23.2.5 [unord.req], 23.5 [unord] Status: LEWG Submitter: Matt Austern Opened: 2009-08-10 Last modified: 2015-04-08
View other active issues in [unord.req].
View all other issues in [unord.req].
View all issues with LEWG status.
Discussion:
Unordered associative containers have a notion of a maximum load factor: when the number of elements grows large enough, the containers automatically perform a rehash so that the number of elements per bucket stays below a user-specified bound. This ensures that the hash table's performance characteristics don't change dramatically as the size increases.
For similar reasons, Google has found it useful to specify a minimum load factor: when the number of elements shrinks by a large enough, the containers automatically perform a rehash so that the number of elements per bucket stays above a user-specified bound. This is useful for two reasons. First, it prevents wasting a lot of memory when an unordered associative container grows temporarily. Second, it prevents amortized iteration time from being arbitrarily large; consider the case of a hash table with a billion buckets and only one element. (This was discussed even before TR1 was published; it was TR issue 6.13, which the LWG closed as NAD on the grounds that it was a known design feature. However, the LWG did not consider the approach of a minimum load factor.)
The only interesting question is when shrinking is allowed. In principle the cleanest solution would be shrinking on erase, just as we grow on insert. However, that would be a usability problem; it would break a number of common idioms involving erase. Instead, Google's hash tables only shrink on insert and rehash.
The proposed resolution allows, but does not require, shrinking in rehash, mostly because a postcondition for rehash that involves the minimum load factor would be fairly complicated. (It would probably have to involve a number of special cases and it would probably have to mention yet another parameter, a minimum bucket count.)
The current behavior is equivalent to a minimum load factor of 0. If we specify that 0 is the default, this change will have no impact on backward compatibility.
[ 2010 Rapperswil: ]
This seems to a useful extension, but is too late for 0x. Move to Tentatively NAD Future.
[ Moved to NAD Future at 2010-11 Batavia ]
Proposed resolution:
Add two new rows, and change rehash's postcondition in the unordered associative container requirements table in 23.2.5 [unord.req]:
Table 87 — Unordered associative container requirements (in addition to container) Expression Return type Assertion/note pre-/post-condition Complexity a.min_load_factor() float Returns a non-negative number that the container attempts to keep the load factor greater than or equal to. The container automatically decreases the number of buckets as necessary to keep the load factor above this number. constant a.min_load_factor(z) void Pre: z shall be non-negative. Changes the container's minimum load factor, using z as a hint. [Footnote: the minimum load factor should be significantly smaller than the maximum. If z is too large, the implementation may reduce it to a more sensible value.] constant a.rehash(n) void Post: a.bucket_count() >= n, and a.size() <= a.bucket_count() * a.max_load_factor(). [Footnote: It is intentional that the postcondition does not mention the minimum load factor. This member function is primarily intended for cases where the user knows that the container's size will increase soon, in which case the container's load factor will temporarily fall below a.min_load_factor().] a.bucket_cout > a.size() / a.max_load_factor() and a.bucket_count() >= n.Average case linear in a.size(), worst case quadratic.
Add a footnote to 23.2.5 [unord.req] p12:
The insert members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. The erase members shall invalidate only iterators and references to the erased elements.
[A consequence of these requirements is that while insert may change the number of buckets, erase may not. The number of buckets may be reduced on calls to insert or rehash.]
Change paragraph 13:
The insert members shall not affect the validity of iterators if
(N+n) < z * Bzmin * B <= (N+n) <= zmax * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container's bucket count, zmin is the container's minimum load factor, and zmax is the container's maximum load factor.
Add to the unordered_map class synopsis in section 23.5.4 [unord.map], the unordered_multimap class synopsis in 23.5.5 [unord.multimap], the unordered_set class synopsis in 23.5.6 [unord.set], and the unordered_multiset class synopsis in 23.5.7 [unord.multiset]:
float min_load_factor() const; void min_load_factor(float z);
In 23.5.4.2 [unord.map.cnstr], 23.5.5.2 [unord.multimap.cnstr], 23.5.6.2 [unord.set.cnstr], and 23.5.7.2 [unord.multiset.cnstr], change:
... max_load_factor() returns 1.0 and min_load_factor() returns 0.
Section: 20.4.2.4 [tuple.creation], 20.3 [pairs] Status: LEWG Submitter: Alisdair Meredith Opened: 2009-09-05 Last modified: 2015-04-08
View all other issues in [tuple.creation].
View all issues with LEWG status.
Discussion:
Spotting a recent thread on the boost lists regarding collapsing optional representations in optional<optional<T>> instances, I wonder if we have some of the same issues with make_tuple, and now make_pair?
Essentially, if my generic code in my own library is handed a reference_wrapper by a user, and my library in turn delegates some logic to make_pair or make_tuple, then I am going to end up with a pair/tuple holding a real reference rather than the intended reference wrapper.
There are two things as a library author I can do at this point:
(There may be some metaprogramming approaches my library can use to wrap the make_tuple call, but all will be significantly more complex than simply implementing a simplified make_tuple.)
Now I don't propose we lose this library facility, I think unwrapping references will be the common behaviour. However, we might want to consider adding another overload that does nothing special with ref-wrappers. Note that we already have a second overload of make_tuple in the library, called tie.
[ 2009-09-30 Daniel adds: ]
I suggest to change the currently proposed paragraph for make_simple_pair
template<typename... Types> pair<typename decay<Types>::type...> make_simple_pair(Types&&... t);
Type requirements: sizeof...(Types) == 2.Remarks: The program shall be ill-formed, if sizeof...(Types) != 2....
or alternatively (but with a slightly different semantic):
Remarks: If sizeof...(Types) != 2, this function shall not participate in overload resolution.
to follow a currently introduced style and because the library does not have yet a specific "Type requirements" element. If such thing would be considered as useful this should be done as a separate issue. Given the increasing complexity of either of these wordings it might be preferable to use the normal two-argument-declaration style again in either of the following ways:
Let V1 be typename decay<T1>::type and V2 be typename decay<T2>::type.
[ 2009-10 post-Santa Cruz: ]
Mark as Tentatively NAD Future.
Rationale:
Does not have sufficient support at this time. May wish to reconsider for a future standard.
Proposed resolution:
Add the following function to 20.3 [pairs] and signature in appropriate synopses:
template<typename... Types> pair<typename decay<Types>::type...> make_simple_pair(Types&&... t);Type requirements: sizeof...(Types) == 2.
Returns: pair<typename decay<Types>::type...>(std::forward<Types>(t)...).
[ Draughting note: I chose a variadic representation similar to make_tuple rather than naming both types as it is easier to read through the clutter of metaprogramming this way. Given there are exactly two elements, the committee may prefer to draught with two explicit template type parameters instead ]
Add the following function to 20.4.2.4 [tuple.creation] and signature in appropriate synopses:
template<typename... Types> tuple<typename decay<Types>::type...> make_simple_tuple(Types&&... t);Returns: tuple<typename decay<Types>::type...>(std::forward<Types>(t)...).
Section: 27.7.3.9 [ostream.rvalue], 27.7.2.6 [istream.rvalue] Status: LEWG Submitter: Howard Hinnant Opened: 2009-09-06 Last modified: 2015-04-08
View all issues with LEWG status.
Discussion:
27.7.3.9 [ostream.rvalue] was created to preserve the ability to insert into (and extract from 27.7.2.6 [istream.rvalue]) rvalue streams:
template <class charT, class traits, class T> basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>&& os, const T& x);1 Effects: os << x
2 Returns: os
This is good as it allows code that wants to (for example) open, write to, and close an ofstream all in one statement:
std::ofstream("log file") << "Some message\n";
However, I think we can easily make this "rvalue stream helper" even easier to use. Consider trying to quickly create a formatted string. With the current spec you have to write:
std::string s = static_cast<std::ostringstream&>(std::ostringstream() << "i = " << i).str();
This will store "i = 10" (for example) in the string s. Note the need to cast the stream back to ostringstream& prior to using the member .str(). This is necessary because the inserter has cast the ostringstream down to a more generic ostream during the insertion process.
I believe we can re-specify the rvalue-inserter so that this cast is unnecessary. Thus our customer now has to only type:
std::string s = (std::ostringstream() << "i = " << i).str();
This is accomplished by having the rvalue stream inserter return an rvalue of the same type, instead of casting it down to the base class. This is done by making the stream generic, and constraining it to be an rvalue of a type derived from ios_base.
The same argument and solution also applies to the inserter. This code has been implemented and tested.
[ 2009 Santa Cruz: ]
NAD Future. No concensus for change.
Proposed resolution:
Change 27.7.2.6 [istream.rvalue]:
template <classcharT, class traitsIstream, class T>basic_istream<charT, traits>&Istream&& operator>>(basic_istream<charT, traits>Istream&& is, T& x);1 Effects: is >> x
2 Returns: std::move(is)
3 Remarks: This signature shall participate in overload resolution if and only if Istream is not an lvalue reference type and is derived from ios_base.
Change 27.7.3.9 [ostream.rvalue]:
template <classcharT, class traitsOstream, class T>basic_ostream<charT, traits>&Ostream&& operator<<(basic_ostream<charT, traits>Ostream&& os, const T& x);1 Effects: os << x
2 Returns: std::move(os)
3 Remarks: This signature shall participate in overload resolution if and only if Ostream is not an lvalue reference type and is derived from ios_base.
Section: 24.2 [iterator.requirements] Status: Open Submitter: Daniel Krügler Opened: 2009-09-19 Last modified: 2015-05-08
View all other issues in [iterator.re