Discussion :

[Nesquik75]

Bonsoir,

Je dois dans le cadre de mes études développer un solveur de RubiksCube. Les structures de données sont imposées et doivent être obligatoirement être réécrites donc pas de std::list .

J'ai donc commencé l'écriture d'une classe List (liste simplement chainée) mais je bute sur l'implémentation des iterateurs. J'aimerais en effet rendre l’utilisation des listes le plus transparent possible et ne pas avoir à bricoler par ci par là. Le problème est que je suis complétement perdu pour implémenter leur fonctionnement.

Voici ma classe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
template <typename T> class Cell
{
    public :
 
    Cell();
    Cell(T info);
    ~Cell();
 
    T GetInfo();
 
    void SetNext(Cell<T>* next);
    Cell* GetNext();
 
    private :
 
    Cell* m_next;
    T m_info;
};
 
template <typename T> class List
{
    public :
 
    List();
    List(const List<T>& Copy);
    List(const std::initializer_list<T>& content);
 
    ~List();
 
    std::size_t GetLength();
    Cell<T>* GetLast();
 
    class iterator
    {
        friend class List<T>;
 
        public:
 
        iterator& operator++();
 
        private :
 
        Cell<T>* m_current;
    };
 
    iterator begin() const;
    iterator end() const;
 
    private :
 
    void AddCell(T info);
 
    std::size_t m_length;
    Cell<T>* m_head;
};

Sachant que cette liste ne sera utilisée que pour former des listes de listes circulaires d'entiers :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
List<List<std::size_t>> list;
list = {{3, 30, 46, 19}, {6, 33, 47, 20}, {9, 36, 48, 21}, {39, 37, 43, 45}, {38, 40, 44, 42}};
 
for(auto fIt = list.begin(); fIt != list.end(); ++ fIt)
    for(auto sIt = fIt->begin(); sIt != fIt->end(); ++ sIt)
        // Utilitaion de *sIt de type size_t

J'ai tenté cette implémentation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T> typename List<T>::iterator List<T>::begin() const
{
    return m_head;
}
 
template <typename T> typename List<T>::iterator List<T>::end() const
{
    return GetLast();
}
 
template <typename T> List<T>::iterator::operator T*() const
{
    return &(m_current->GetInfo());
}
 
template <typename T> typename List<T>::iterator& List<T>::iterator::operator++()
{
    m_current->SetNext(m_current->GetNext());
    return *this;
}

Et j'obtiens des erreurs lors de la compilation :

||=== CubeSolver, Debug ===|
es\CubeSolver\dev\list.cxx||In member function 'List<T>::iterator List<T>::begin() const [with T = unsigned int] ': |
es\CubeSolver\dev\main.cpp:30|55|instantiated from here|
es\CubeSolver\dev\list.cxx|57|error: could not convert 'this->List<unsigned int>::m_head' from 'Cell<unsigned int>* const' to 'List<unsigned int>::iterator'|
es\CubeSolver\dev\list.cxx||In member function 'List<T>::iterator List<T>::end() const [with T = unsigned int] ': |
es\CubeSolver\dev\main.cpp:30|75|instantiated from here|
es\CubeSolver\dev\list.cxx|62|error: could not convert 'nullptr' from 'std::nullptr_t' to 'List<unsigned int>::iterator'|
es\CubeSolver\dev\list.cxx||In member function 'List<T>::iterator::operator T*() const [with T = unsigned int]': |
es\CubeSolver\dev\main.cpp:30|75|instantiated from here|
es\CubeSolver\dev\list.cxx|67|error: lvalue required as unary '&' operand|
es\CubeSolver\dev\list.cxx||In member function 'List<T>::iterator List<T>::begin() const [with T = unsigned int]': |
es\CubeSolver\dev\list.cxx|58|warning: control reaches end of non-void function [-Wreturn-type]|
es\CubeSolver\dev\list.cxx||In member function 'List<T>::iterator List<T>::end() const [with T = unsigned int]': |
es\CubeSolver\dev\list.cxx|63|warning: control reaches end of non-void function [-Wreturn-type]|
es\CubeSolver\dev\list.cxx||In member function 'List<T>::iterator::operator T*() const [with T = unsigned int]': |
es\CubeSolver\dev\list.cxx|68|warning: control reaches end of non-void function [-Wreturn-type]|
||=== Build finished: 3 errors, 3 warnings ===|

Je comprends les erreurs qui pour la majeure partie m'indiquent que je ne renvoie pas un iterator dans les méthodes begin() et end(). Malheureusement, je ne vois pas comment faire autrement.


Merci de me soumettre toute remarque qui permettrait d'améliorer la compréhension ou performance de mon code.

Merci d'avance

[Dalini71]

Si c'est juste pour parcourir ta liste, pourquoi t’embêter à simuler le comportement des iterators ? Ça n'a pas vraiment d’intérêt si tu n'as qu'un seul type de conteneur.

Pourquoi ne pas simplement parcourir ta liste à coups de GetNext() ?

[Nesquik75]

Je dois implémenter les listes dans un contexte de projet et d'entrainement. Peut être que l’intérêt est limité mais cela fera un plus pour mon projet et facilitera l'écriture de code STL-like.

[Flob90]

Pour tes erreurs : tu dis que tes fonctions retournent un iterator et dans l'implémentation tu retournes un pointeur, le compilateur râle. Rajoutes un constructeur et ca devrait meiux aller.