Frage zur Listen und Elementenverteilung

khalderon

Hi,
wie sieht eine Funktion in C++ aus, die eine Liste von Objekten (eigentlich sind diese Zeiger) durchliest und nach einer speizifischen Eigenschaft verteilt die Elemente in 2 anderen Listen. D.h. wir haben eine grosse Liste. Manche Elemente sollen in eine andere Liste verschiebt/kopiert werden. Die andere Elemente, die diese Eigenschaft nicht besitzen, sollen in eine andere Liste kopiert. Ich soll besser STL benutzen.

CStoll

Nur ein Ansatz - verstehen und anpassen mußt du ihn schon selber:

list<data_t> indata,out1,out2;
//fülle indata mit allen betrachteten Objekten

while(!indata.empty())
  if(isok(indata.front())
    out1.splice(out1.end(),indata,indata.begin());
  else
    out2.splice(out2.end(),indata,indata.begin());

(splice() gibt es nur für list - das hängt einzelne Elemente zwischen verschiedenen Listen um)

Bashar

Wenn deine Liste STL-kompatibel ist, also entsprechende Iteratoren anbietet, kannst du den partition-Algorithmus aus der STL anwenden. Die Elemente bleiben dabei allerdings in derselben Liste, nur dass die, die die Eigenschaft haben, nach vorne sortiert werden. Einen Algorithmus, der zwei neue Listen erzeugt, müsstest du selbst schreiben, das ist aber trivial.

Werner Salomon

Bashar schrieb:

Einen Algorithmus, der zwei neue Listen erzeugt, müsstest du selbst schreiben, das ist aber trivial.

Muss man nicht. Die Methode list::splice kann auch das.

#include <algorithm>    // partition
#include <iostream>
#include <iterator>     // back_inserter, ostream_iterator
#include <list>

struct Eigenschaft
{
    bool operator()( int x ) const
    {
        return x % 3 == 0  ||  x % 7 == 0; // nur als Beispiel
    }
};

int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
    std::list< int > l1;
    std::copy( arr, arr + sizeof( arr )/sizeof( *arr ), std::back_inserter( l1 ) );

    // --   hier geht's los
    std::list< int > l2;
    l2.splice( l2.end(), l1, l1.begin(), std::partition( l1.begin(), l1.end(), Eigenschaft() ) );

    // --   zur Kontrolle alles ausgeben
    std::copy( l1.begin(), l1.end(), 
        std::ostream_iterator< int >( std::cout << "Die eine Liste: ", " ") );
    std::cout << std::endl;
    std::copy( l2.begin(), l2.end(), 
        std::ostream_iterator< int >( std::cout << "Die andere (durch 3 oder 7 teilbar): ", " ") );
    std::cout << std::endl;

    return 0;
}

'l1' wird aufgeteilt in 'l2', welches nur die Elemente mit der gewünschten Eigenschaft enthält (hier beispielhaft die Teilbarkeit durch 3 oder 7), und in 'l1' bleiben die anderen zurück.

Gruß
Werner