This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [RFC] libstdc++/19422: complexity of ass. containers range constr.
- From: Paolo Carlini <pcarlini at suse dot de>
- To: Paolo Carlini <pcarlini at suse dot de>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>,Matt Austern <austern at apple dot com>
- Date: Thu, 13 Jan 2005 19:48:34 +0100
- Subject: Re: [RFC] libstdc++/19422: complexity of ass. containers range constr.
- References: <41E6B516.3080508@suse.de> <41E6B595.7090803@suse.de>
Paolo Carlini wrote:
Paolo Carlini wrote:
Now, my immediate reaction: why we are not using instead the versions
of insert_unique/insert_equal that take an hint iterator too? That
version has guaranteed constant complexity if t is inserted right
after p (Table 69) and that would be the case when [i, j) is already
sorted, I think...
Forgot to add: in this application, the suited hint iterator would be
end(), of course.
Sorry for replying to myself again: in the meanwhile, learned from pag.
167 of Musser/Derge/Saini that my idea makes perfect sense ;)
Therefore, if nobody stops me, I'm going to implement and test it.
Paolo.
P.S. Why the bug? I guess that the requirement in Table 69 about linear
complexity of "ordered" construction and insert, was not part of the
original design of the STL.