Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[container.reqmts] p65 seems to ban small string optimization #5518

Open
killerbee13 opened this issue Jun 10, 2022 · 6 comments
Open

[container.reqmts] p65 seems to ban small string optimization #5518

killerbee13 opened this issue Jun 10, 2022 · 6 comments

Comments

@killerbee13
Copy link

[container.reqmts] p65 (previously at [container.requirements.general] p9 in C++11–20) states that, except for array in particular, a.swap(b) shall not copy, move, or swap any container elements, and preserves iterator stability. However, [basic.string.general] p2 states that specializations of basic_string are contiguous containers. SSO would mean that both requirements of p65 are impossible to satisfy, as if either string is small, the elements must be copied from the internal buffer of that string into the internal buffer of the other string, even if such copying is trivial.

LWG1415 described an overlapping issue, and was resolved by N3108, which added normative wording exempting basic_string from the allocator-aware construct and destroy requirements as well as a footnote stating this exception for swap, but notes are non-normative. [string.require] p4 does not exempt swap from the general rule allowing iterator invalidation by non-const member functions, and the footnote there does mention swap (seemingly being a less specific version of the note suggested by N3108, though it may be unrelated), however, it is not clear to me that it should override the invalidation guarantees in [container.reqmts] p65 (is a general rule about many operations on a specific container more specific than a more descriptive rule about a specific member function of many containers, particularly one which does specify an exception?), and it definitely doesn't override the complementary restriction on element copy, move, or swap operations stated there that SSO also necessarily violates, because there is no wording in [basic.string] that mentions swap performing or not performing those operations.

The simplest resolution is to simply add 'and basic_string' after 'other than array' in [container.reqmts] p65.

@jensmaurer
Copy link
Member

@jwakely , the suggestion seems to be eminently reasonable. What do you think?

@JohelEGP
Copy link
Contributor

is a general rule about many operations on a specific container more specific than a more descriptive rule about a specific member function of many containers, particularly one which does specify an exception?

It's as you just pointed out with std::string. Explicitly describing a member function is not license to deviate from the container requirements.

The container requirements centralize exceptions. Elsewhere, where some [library] requirement is overriden, the exception is at the point of use, like

4
#
Note B: Notwithstanding the provisions of [meta.type.synop], and pursuant to [namespace.std], a program may specialize common_­type<T1, T2> for types T1 and T2 such that is_­same_­v<T1, decay_­t> and is_­same_­v<T2, decay_­t> are each true.

@jwakely
Copy link
Member

jwakely commented Sep 24, 2022

Hmm, N3108 solved this problem, but then that paragraph was removed in WP N3242 (see the red change marks in [basic.string] p3). I can't find any justification for removing that text. The editor's report in N3243 doesn't mention it. I can't find any paper or LWG issue saying to remove it.

@jwakely
Copy link
Member

jwakely commented Sep 24, 2022

We had to put back the wording about basic_string not using the allocator's construct and destroy members in P1072R10. That should have been unnecessary, because we already had that wording prior to N3242.

@jwakely
Copy link
Member

jwakely commented Sep 24, 2022

LWG1415 described an overlapping issue, and was resolved by N3108, which added normative wording exempting basic_string from the allocator-aware construct and destroy requirements as well as a footnote stating this exception for swap, but notes are non-normative.

That's not quite right. N3108 did not add the text about construct and destroy, it added the text shown in bold in N3108, which includes a normative exemption for swap (and a footnote saying why the exemption exists).

N3108 solved this problem, then some mystery edit in N3242 removed it (and the allocator stuff) and somehow nobody noticed. I'm quite concerned by this (LWG 2263 suggests there was another accidental deletion in N3242).

The simplest resolution is to simply add 'and basic_string' after 'other than array' in [container.reqmts] p65.

I don't think that's sufficient. That would allow us to copy characters when swapping strings, but it's not clear to me that "other than array" in that first sentence also exempts array from the penultimate sentence in the paragraph, about iterators. And if exceptions in that first sentence to apply to the whole paragraph, then your suggestion would mean that basic_string no longer uses propogate_on_container_swap, which would be wrong. We also have the following in [container.reqmts] p16 (16.6) which should exclude array:

no swap() function invalidates any references, pointers, or iterators referring to the elements of the
containers being swapped.

Technically that only applies to containers in "this Clause", so already excludes basic_string, but that's subtle and it's not clear to me why those requirements don't apply to basic_string.

I think we need an LWG issue, this is messy.

@jensmaurer
Copy link
Member

That old Working Draft was just before we moved to git, so we can't really trace what caused the removal.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants