From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16616 invoked by alias); 13 Jan 2005 17:21:04 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 15641 invoked by uid 48); 13 Jan 2005 17:20:25 -0000 Date: Thu, 13 Jan 2005 17:21:00 -0000 Message-ID: <20050113172025.15640.qmail@sourceware.org> From: "pcarlini at suse dot de" To: gcc-bugs@gcc.gnu.org In-Reply-To: <20050113120525.19422.SWElef@post.sk> References: <20050113120525.19422.SWElef@post.sk> Reply-To: gcc-bugzilla@gcc.gnu.org Subject: [Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted X-Bugzilla-Reason: CC X-SW-Source: 2005-01/txt/msg01704.txt.bz2 List-Id: ------- Additional Comments From pcarlini at suse dot de 2005-01-13 17:20 ------- > This is my test program. Thanks. > After giving it some thought I believe that calling the > insert_unique/insert_equal function is wrong. I don't think that any hint > (position) can help to make the running time linear in distance(first,last). > A special function should be writen for this purpose. Why? Are you aware of the fact that insert with hint has amortized *constant* complexity if t is inserted after p? (Table 69) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422