Déplacer une partie d'une QLinkedList

Version imprimable

04/11/2010, 18h24
oc_alex86

Déplacer une partie d'une QLinkedList

Bonjour,

je souhaite pouvoir déplacer une sous-liste d'une QLinkedList vers une autre QLinkedList.
Par exemple, j'ai une liste d'entier positifs triés, et je souhaite déplacer tous les éléments plus petit que 100 dans une autre liste.
Il y a-t-il un moyen efficace de faire cela ?
Il suffit normalement de déplacer deux pointeurs, mais je ne vois pas comment faire cela dans un QLinkedList.

J'ai aussi essayé de faire ça avec std::list, mais je ne vois pas comment utiliser slice pour déplacer une partie de list de begin() à un interateur i vers une autre liste.

Bonjour oc_alex86

Quelques solutions (pour m'amuser avec les algorithmes de la STL :) ) :

Avec std::partition :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <QtCore/QCoreApplication>
#include <QtCore/QLinkedList>
#include <QtCore/QDebug>
 
#include <algorithm>
 
typedef QLinkedList<int> List;
typedef List::const_iterator Iterator;
 
bool isNegative (int i) { return (i < 0); }
 
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
 
    List ll;
    ll << 1 << -2 << 3 << -4 << 5 << -6;
 
    const Iterator middle = std::partition(ll.begin(), ll.end(), isNegative);
 
    qDebug() << "Negatives numbers:";
    for (Iterator it=ll.begin(); it!=middle; ++it)
        qDebug() << *it;
    qDebug() << "Positives numbers:";
    for (Iterator it=middle; it!=ll.end(); ++it)
        qDebug() << *it;
 
    return a.exec();
}

Avec std::remove_copy_if (ne fonctionne pas avec QLinkedList...) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <QtCore/QCoreApplication>
#include <QtCore/QLinkedList>
#include <QtCore/QDebug>
 
#include <algorithm>
 
typedef QVector<int> List;
typedef List::const_iterator Iterator;
 
bool isNegative (int i) { return (i < 0); }
bool isPositiveOrZero (int i) { return (i >= 0); }
 
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
 
    List ll;
    ll << 1 << -2 << 3 << -4 << 5 << -6;
 
    List nn(6); // negatives numbers
    std::remove_copy_if(ll.begin(), ll.end(), nn.begin(), isNegative);
 
    List pn(6); // positives numbers
    std::remove_copy_if(ll.begin(), ll.end(), pn.begin(), isPositiveOrZero);
 
    qDebug() << "Negatives numbers:";
    for (Iterator it=nn.begin(); it!=nn.end(); ++it)
        qDebug() << *it;
    qDebug() << "Positives numbers:";
    for (Iterator it=pn.begin(); it!=pn.end(); ++it)
        qDebug() << *it;
 
    return a.exec();
}

Avec std::for_each :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <QtCore/QCoreApplication>
#include <QtCore/QLinkedList>
#include <QtCore/QDebug>
 
#include <algorithm>
 
typedef QLinkedList<int> List;
typedef List::const_iterator Iterator;
 
struct copy_switch
{
    List& negatives;
    List& positives;
    copy_switch(List& n, List& p) : negatives(n), positives(p) {}
    void operator() (int i) { if (i < 0) negatives.push_back(i); else positives.push_back(i); }
};
 
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
 
    List ll;
    ll << 1 << -2 << 3 << -4 << 5 << -6;
 
    List nn; // negatives numbers
    List pn; // positives numbers
    copy_switch f(nn, pn);
    std::for_each(ll.begin(), ll.end(), f);
 
    qDebug() << "Negatives numbers:";
    for (Iterator it=nn.begin(); it!=nn.end(); ++it)
        qDebug() << *it;
    qDebug() << "Positives numbers:";
    for (Iterator it=pn.begin(); it!=pn.end(); ++it)
        qDebug() << *it;
 
    return a.exec();
}

Et pour finir, une version template :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <QtCore/QCoreApplication>
#include <QtCore/QLinkedList>
#include <QtCore/QDebug>
 
#include <algorithm>
 
typedef QLinkedList<int> List;
typedef List::const_iterator Iterator;
 
template<typename T>
struct copy_switch
{
    T& negatives;
    T& positives;
    copy_switch(const T& in, T& n, T& p) : negatives(n), positives(p) { std::for_each(in.begin(), in.end(), *this); }
    template<typename T2> void operator() (T2 i) { if (i < 0) negatives.push_back(i); else positives.push_back(i); }
};
 
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
 
    List ll;
    ll << 1 << -2 << 3 << -4 << 5 << -6;
 
    List nn; // negatives numbers
    List pn; // positives numbers
    copy_switch<List> f(ll, nn, pn);
 
    qDebug() << "Negatives numbers:";
    for (Iterator it=nn.begin(); it!=nn.end(); ++it)
        qDebug() << *it;
    qDebug() << "Positives numbers:";
    for (Iterator it=pn.begin(); it!=pn.end(); ++it)
        qDebug() << *it;
 
    return a.exec();
}

J'espère que ca peut t'aider

04/11/2010, 23h01
oc_alex86

Merci beaucoup pour ta réponse très détaillée!
J'y découvre plein de fonctions qui m'étaient inconnues.
Néanmoins toutes tes solutions ont un léger problème à mon point de vue, elles nécessitent toutes de parcourir deux fois la liste : une fois pour trouver la position où couper et une fois pour déplacer les éléments.
N'y aurait-il pas un moyen por faire cela en un seul passage (ce qui est très facile avec une implémentation plus bas niveau: on change juste quelques pointeurs)?
05/11/2010, 03h04
gbdivers
Citation:

elles nécessitent toutes de parcourir deux fois la liste

Ca dépend de la méthode...

La première a une complexité en N ou N.logN, donc elle ne parcourt pas exactement 2 fois la liste. (remarque : il vaudrait mieux utiliser std::stable_partition ici au lieu de std::partition, pour conserver l'ordre de départ)

La seconde méthode parcours 1 fois la liste pour les positifs et 1 fois pour les négatifs.

La troisième parcours la liste 1 seule fois

EDIT : je dois être un peu fatigué... j'ai écris des exemples qui séparent positifs vs négatifs :aie: mais bon, je suppose que tu as converti sans problème pour séparer les supérieur à 100 et inférieur à 100.

Remarque 2 : comme ta liste est triée, séparer en 2 liste "sup à 100" et "inf à 100" revient à faire une recherche de la première valeur "sup à 100" :
Code:

1 2 3 const Iterator middle = std::upper_bound(ll.begin(), ll.end(), 100); std::copy(ll.begin(), middle, nn); std::copy(middle, ll.end(), pn);
De plus, si tu ne modifies plus tes listes après le split, tu peux toujours continuer à utiliser une paire d'itérateurs avec 1 seule liste, ça évite de devoir copier la liste.
06/11/2010, 12h10
oc_alex86

Merci beaucoup