std::partition – cppreference.com

Aus cppreference.com

definiert in Header `<algorithm>`

`template< class BidirIt, class UnaryPredicate > BidirectionalIterator partition( BidirIt first, BidirIt last, UnaryPredicate p ); template< class ForwardIt, class UnaryPredicate > ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );`		(bis C + +11) (seit C++11)

Ordnet die Elemente im Bereich [first, last) derart, daß alle Elemente für die das Prädikat p kehrt true vorausgehen, für die die Elemente Prädikats p kehrt false. Relative Reihenfolge der Elemente ist nicht erhalten .

Original:

Reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. Relative order of the elements is not preserved.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Parameter

first, last	-	der Bereich von Elementen neu zu ordnen Original: the range of elements to reorder The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
p	-	unary predicate which returns `true` wenn das Element sollte vor anderen Elementen bestellt werden Original: if the element should be ordered before other elements The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. . The signature of the predicate function should be equivalent to the following: `bool pred(const Type &a);` The signature does not need to have `const &`, but the function must not modify the objects passed to it. The type `Type` must be such that an object of type `ForwardIt` can be dereferenced and then implicitly converted to `Type`.
Type requirements
-`BidirIt` must meet the requirements of `BidirectionalIterator`.
-`ForwardIt` must meet the requirements of `ValueSwappable` and `ForwardIterator`. However, the operation is more efficient if `ForwardIt` also satisfies the requirements of `BidirectionalIterator`

Rückgabewert

Iterator auf das erste Element der zweiten Gruppe .

Original:

Iterator to the first element of the second group.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Komplexität

Genau last-first Anwendungen des Prädikats und höchstens last-first Swaps. Wenn ForwardIt erfüllt die Anforderungen der BidirectionalIterator höchstens (last-first)/2 Swaps fertig sind .

Original:

Exactly last-first applications of the predicate and at most last-first swaps. If ForwardIt meets the requirements of BidirectionalIterator at most (last-first)/2 swaps are done.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Mögliche Implementierung

template<class BidirIt, class UnaryPredicate>
BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p)
{
    while (1) {
        while ((first != last) && p(*first)) {
            ++first;
        }
        if (first == last--) break;
        while ((first != last) && !p(*last)) {
            --last;
        }
        if (first == last) break;
        std::swap(*first++, *last);
    }
    return first;
}

Beispiel

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

bool is_even(int i) { return i % 2 == 0; }

int main()
{
    std::vector<int> v;
    for (int i = 0; i < 10; ++i) v.push_back(i);
    
    std::cout << "Original vector:\n    ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    
    // Partition the vector
    std::vector<int>::iterator p =
        std::partition(v.begin(), v.end(), std::ptr_fun(is_even));
    
    std::cout << "\nPartitioned vector:\n    ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nBefore partition:\n    ";
    std::copy(v.begin(), p,       std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nAfter partition:\n    ";
    std::copy(p,         v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Possible output:

Original vector:
    0 1 2 3 4 5 6 7 8 9 
Partitioned vector:
    0 8 2 6 4 5 3 7 1 9 
Before partition:
    0 8 2 6 4 
After partition:
    5 3 7 1 9

Siehe auch


	bestimmt, ob der Bereich von der gegebenen Prädikat partitioniert ist Original: determines if the range is partitioned by the given predicate The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (Funktions-Template) [edit]

	trennt Elemente in zwei Gruppen unter Beibehaltung ihrer relativen Ordnung Original: divides elements into two groups while preserving their relative order The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (Funktions-Template) [edit]