From -4213329007032277214 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,8aaf2e68e0b81f6f X-Google-Attributes: gidf78e5,public From: "Bradd W. Szonye" Subject: Re: Bug in insert range in associative containner in CD2 Date: 1998/01/29 Message-ID: <6aorpk$be8@examiner.concentric.net>#1/1 X-Deja-AN: 320342404 References: <34CF792D.2C52@pratique.fr> X-Original-Date: Wed, 28 Jan 1998 22:05:00 -0500 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft MimeOLE V4.72.2106.4 Organization: Concentric Internet Services X-Auth: PGPMoose V1.1 PGP comp.std.c++ iQBVAwUBNNDS+ky4NqrwXLNJAQGN+QIAyRng6ZggCR0q88MtWH6j6Zhvyar7IR90 OJ565rpi4TgNaU1pYV8UrqGAV4d2X5XUcE4at7bTTfJQ87eBi8e7lg== =ou+z Newsgroups: comp.std.c++ Originator: austern@isolde.mti.sgi.com Valentin Bonnard wrote in message <34CF792D.2C52@pratique.fr>... >The CD2 says in table 7 of Containners that a.insert(i,j) >is linear if [i, j) is ordered. It seems impossible to >implement to me, as it means that if [i, j) = [x], insert >in an associative containner is O(1) ! Well, it's possible for some trees. For example, any in-order iteration over a splay tree is guaranteed O(N), whether for access, insert, or delete. And it's not a special-case algorithm; that's just the way they work. However, a splay tree does not meet other requirements, such as guaranteed O(log N) random access. It is only amortized O(log N). I do wonder whether a standard library would be non-conforming for using a splay tree to implement the associative containers; they are in the spirit if not the letter of the requirements. There's another requirement for associative containers which says approximately that insert is O(1) if you insert relative to an iterator immediately before the insertion point in order. The range insert method apparently takes advantage of this. I'm not sure whether either requirement is actually feasible for a given tree algorithm; algorithmic analysis was never my strong point, I'm afraid, beyond the basics. I just barely get the "telescoping sums" thing. Bradd W. Szonye bradds@concentric.net http://www.concentric.net/~Bradds --- [ comp.std.c++ is moderated. To submit articles: Try just posting with your newsreader. If that fails, use mailto:std-c++@ncar.ucar.edu comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html Comments? mailto:std-c++-request@ncar.ucar.edu ]