From -3374223610842583859 X-Google-Thread: f78e5,542d58b3f0251594 X-Google-NewGroupId: yes X-Google-Attributes: gid7894ca11fe,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news1.google.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!news.alt.net From: =?ISO-8859-1?Q?Daniel_Kr=FCgler?= Newsgroups: comp.std.c++ Subject: Re: Why doesn't stable_partition_copy exist? Date: Wed, 15 Sep 2010 12:15:04 CST Organization: http://groups.google.com Lines: 48 Sender: std-c++-request@ruralroute.cs.rpi.edu Approved: austern@google.com Message-ID: <0ff966f3-d7cc-4ab7-b1ed-03b2c96d925a@a30g2000vbt.googlegroups.com> References: < 6bbe4666-5457-4f87-9445-acd7d1e6994e@z34g2000pro.googlegroups.com> NNTP-Posting-Host: netlab.cs.rpi.edu Content-Type: text/plain; charset=ISO-8859-1 To: (Usenet) Return-Path: X-Hash: SCt|3e3cf11f94129aed04548f4cffe973b08fb6eb88|412e9e1b442c71cdad525c8052aea487 X-Countries: United States X-SMTP-From: accepted assassin.cs.rpi.edu [128.113.126.17] (assassin.cs.rpi.edu) {United States} DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=cs.rpi.edu; h=date :to:sender:message-id:from:subject:references:content-type; s= default; i=128.113.126.17@cs.rpi.edu; t=1284570904; x= 1285175704; l=1752; bh=0gF6N8+fZJhZ4n/tAYHe24P4Gaw=; b=n7nTqdIIo EztBYpHe9bEuoSTCH8tOCwp/zcIc4psW8AqUf1EY/97MVt2NvrCGYsVnS2OPwEH1 rOG8cohNVW4R/hZBAKocu4mi5lTu7uOl8mhRbeToA0gNXuebCZfLnw+K76naFHZ5 MQqzLgwCky/ZG8Cu0KdHF3iGg1y/eiotJU= DomainKey-Signature: a=rsa-sha1; c=nofws; d=cs.rpi.edu; h=date:to:sender :message-id:from:subject:references:content-type; q=dns; s= default; b=munUeXqSzeOzXaJMr16c4rncQpECDDa5RceKNq+af4dcmIGgCHYI3 MqShG1Xk3aigoY+Dm/PtXFe7VIprXoveNjXACROY9v859grkTiWQS6UAlkjq5a35 v9hIkbrIAm9J5bVnqjf+3wPXDh93FVJV85/lpp6EX8q+ZhO5oqFrXQ= X-Spam-Report: Spam Report from cliffclavin.cs.rpi.edu (SA:3.2.5): -1.8 ALL_TRUSTED Passed through trusted hosts only via SMTP 0.2 SUBJECT_FUZZY_TION Attempt to obfuscate words in Subject: 3.4 HEADER_SPAM Bulk email fingerprint (header-based) found -0.9 BAYES_00 BODY: Bayesian spam probability is 0 to 1% [score: 0.0000] 0.2 SARE_HEAD_HDR_APPROV Message headers used which identify spam -0.1 AWL AWL: From: address is in the auto white-list X-Spam-Info: 0.9, local; ALL_TRUSTED,AWL,BAYES_00,HEADER_SPAM,SARE_HEAD_HDR_APPROV, SUBJECT_FUZZY_TION X-Spam-Scanned-By: cliffclavin.cs.rpi.edu using SpamAssassin 3.2.5 X-Virus-Scanned-By: cliffclavin.cs.rpi.edu X-Original-Date: Tue, 14 Sep 2010 16:21:03 -0700 (PDT) X-Submission-Address: std-c++@netlab.cs.rpi.edu X-Scanned-By: MIMEDefang 2.67 on 128.113.126.25 Xref: g2news1.google.com comp.std.c++:2954 On 14 Sep., 22:49, Jared wrote: > N3092 defines partition, stable_partition, and partition_copy. The > algorithms differ in where they store their results and the relative > ordering thereof. > > The rationale for providing a _copy version of an algorithm is based > on whether or not the complexity of the operation would dominate the > copy. It seems like this rationale ought to be in play for > stable_partition. > > Is this a hole or is this algorithm somehow redundant or otherwise > inappropriate? It is redundant, because partition_copy is already stable: Both destinations are filled by conserving the original ordering. In fact you can implement a simple stable_partition if you have a buffer of the same size as the to-be-partitioned sequence by writing [untested]: template ForwardIterator1 stable_partition_with_buffer(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, Predicate pred) { std::pair res = std::partition_copy(first1, last1, first1, first2, pred); return std::copy(first2, res.second, res.first); } It satisfies the criteria for stable partitioning, because both the relative order of the elements satisfying the predicate and that of those not satisfying the predicate remains preserved. HTH & Greetings from Bremen, Daniel Kr=FCgler -- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@netlab.cs.rpi.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ]