Re: insertion with hint
On 2008-06-26 11:57, Greg Herlihy wrote:
On Jun 25, 5:17 pm, Erik Wikstr??m <Erik-wikst...@telia.com> wrote:
On 2008-06-25 13:24, otun...@yahoo.com wrote:
The C++ standard (ISO/IEC 14882:2003) states in table 69 (in clause
23.1.2), for the insert member with a hint:
"Complexity: logarithmic in general, but amortized constant if t is
inserted right after p."
t is the inserted object and p the hint.
If this is the case, how would I give a hint to insert t to the
beginning of an associative container ?
std::set<int> set;
set.insert(set.begin(), 1);
No, set.begin() would be the appropriate hint when when inserting a
second-placed item into an associative container. In the current C++
language Standard, there is in fact no way to specify an appropriate
hint when inserting a first placed-element into an associative
container (because there is no iterator that comes before the iterator
returned by begin()).
C++09 corrects this deficiency. In the next C++ Language Standard, the
insertion hint specifies the element that comes -after- the element
being inserted. So in C++09x, std.begin() would be the appropriate
hint when inserting an item into the beginning of an associative
container.
Hmm, you are right, I only looked in the "assertion/note/pre/post-
condition" column, where it says that the hint is the place where the
search is started. In the "complexity" column on the other hand it says
that the operation will be in amortized constant time if the element is
inserted right *after* the hint.
--
Erik Wikstr??m
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]