class deque, constructeurs et fonctions de bases.

Version imprimable

Bonjour,

Je suis étudiant en informatique, et cette année nous avons une matière dédié au C++, pour la fin de l'année (écourter par la situation actuelle), nous avons un projet, à faire sur un sujet donné par notre professeur.
L'objectif est de recréer la class deque de la STL à partir des signatures de fonction donné par notre professeur (et avec les Template) .

Mon problème, j'ai compris ce qu'était un deque (tableau 2D) cependant je n'arrive pas à comprendre les signatures du profs et débuter le sujet.

Si quelqu'un veux bien m'expliquer comment tout cela fonctionne, et peut être me donner des pistes pour démarrer. ( et aussi comprendre l’intérêt du sujet comme la class deque existe déjà et qu'il suffit de l'importer).

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 
 
#ifndef C_DEQUE_H
#define C_DEQUE_H
#include <cstdio>
#include <functional>
#include <initializer_list>
 
 
template <class T> class deque {
public:
    // ne pas toucher
    using value_type = T;
    using size_type = size_t;
    static T dummy;  // pour renvoyer une lvalue lorsque demandé
 
    // à implémenter
    deque() {}
    explicit deque( size_type count ) {}
    deque( size_type count, const T& value ) {}
    template< class InputIt > deque( InputIt first, InputIt last) {}
    deque( const deque& other ) {}
    deque( deque&& other ) {}
    deque( std::initializer_list<T> init ) {}
    ~deque() {}
 
    deque& operator=( const deque& other ) { return *this; }
    deque& operator=( deque&& other ) { return *this; }
    deque& operator=( std::initializer_list<T> ilist ) { return *this; }
 
    void assign( size_type count, const T& value ) {}
    template< class InputIt > void assign( InputIt first, InputIt last ) {}
    void assign( std::initializer_list<T> ilist ) {}
 
    T& at( size_type pos ) { return dummy; }
    const T& at( size_type pos ) const { return dummy; }
 
    T& operator[]( size_type pos ) { return dummy; }
    const T& operator[]( size_type pos ) const { return dummy; }
 
    T& front() { return dummy; }
    const T& front() const { return dummy; }
 
    T& back() { return dummy; }
    const T& back() const { return dummy; }
 
    bool empty() const { return false; }
 
    size_t size() const { return 0; }
 
    void clear() {}
 
 
    void push_back( const T& value ) {}
    void push_back( T&& value ) {}
 
    template< class... Args > void emplace_back( Args&&... args ) {}
 
    void pop_back() {}
 
    void push_front( const T& value ) {}
    void push_front( T&& value ) {}
 
    template< class... Args > void emplace_front( Args&&... args ) {}
 
    void pop_front() {}
 
    void resize( size_type count ) {}
    void resize( size_type count, const value_type& value ) {}
 
    void swap( deque& other ) {}
 
    friend bool operator==( const deque& lhs, const deque& rhs ) { return true; }
    friend bool operator!=( const deque& lhs, const deque& rhs ) { return true; }
    friend bool operator<(  const deque& lhs, const deque& rhs ) { return true; }
    friend bool operator<=( const deque& lhs, const deque& rhs ) { return true; }
    friend bool operator>(  const deque& lhs, const deque& rhs ) { return true; }
    friend bool operator>=( const deque& lhs, const deque& rhs ) { return true; }
 
    // iterateur classique
    class iterator {
    public:
        explicit iterator() {}
        iterator(const iterator&) {}
        iterator& operator++() { return *this; }
        iterator operator++(int) { return *this; }
        bool operator==(iterator other) const { return false; }
        bool operator!=(iterator other) const { return false; }
        T& operator*() const { return dummy; };
        //// birectionnel
        // iterator& operator--();
        // iterator operator--(int);
        //// random access
        // bool operator<(const iterator&)  const;
        // bool operator<=(const iterator&) const;
        // bool operator>(const iterator&)  const;
        // bool operator>=(const iterator&) const;
        // iterator& operator+=(const int n)
        // iterator& operator-=(const int n)
        // int& operator[](int n);
        // const int& operator[](int n) const;
    };
    iterator begin() { return iterator(); }
    iterator end() { return iterator(); }
 
    // iterateur constant
    class const_iterator {
    public:
        explicit const_iterator() {}
        const_iterator(const const_iterator&) {}
        const_iterator(const iterator&) {}
        const_iterator& operator++() { return *this; }
        const_iterator operator++(int) { return *this; }
        bool operator==(const_iterator other) const { return false; }
        bool operator!=(const_iterator other) const { return false; }
        const T& operator*() const { return dummy; };
        //// birectionnel
        // iterator& operator--();
        // iterator operator--(int);
        //// random access
        // bool operator<(const iterator&)  const;
        // bool operator<=(const iterator&) const;
        // bool operator>(const iterator&)  const;
        // bool operator>=(const iterator&) const;
        // iterator& operator+=(const int n)
        // iterator& operator-=(const int n)
        // int& operator[](int n);
        // const int& operator[](int n) const;
    };
    const_iterator cbegin() { return const_iterator(); }
    const_iterator cend() { return const_iterator(); }
    const_iterator begin() const { return const_iterator(); }
    const_iterator end() const { return const_iterator(); }
 
    // methode necessitant des itérateurs
    iterator insert( const_iterator pos, const T& value ) { return iterator(); }
    iterator insert( const_iterator pos, T&& value ) { return iterator(); }
    iterator insert( const_iterator pos, size_type count, const T& value ) { return iterator(); }
    template< class InputIt > iterator insert( iterator pos, InputIt first, InputIt last) { return iterator(); }
    iterator insert( const_iterator pos, std::initializer_list<T> ilist ) { return iterator(); }
 
    iterator erase( const_iterator pos ) { return iterator(); }
    iterator erase( const_iterator first, const_iterator last ) { return iterator(); }
 
    template< class... Args > iterator emplace( const_iterator pos, Args&&... args ) { return iterator(); }
 
    // autres itérateurs
    /*
    class reverse_iterator {};
    reverse_iterator rbegin(); //
    reverse_iterator rend();   //
    class const_reverse_iterator {};
    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const;
    const_reverse_iterator crbegin() const;
    const_reverse_iterator crend() const;
    */
};
 
template<class T> void swap( deque<T> &lhs, deque<T> &rhs ) {}
 
template <class T> T deque<T>::dummy = 0;
#endif //C_DEQUE_H

merci à tous.

06/04/2020, 00h23
dalfab

Bonjour,

Tout d'abord, un deque n'est pas un tableau 2D. C'est un tableau 1D comme std::vector sauf qu'il est mieux adapté que lui pour faire des ajouts ou suppressions en début de tableau et un peu moins rapide en accès direct à un élément.

Ensuite, je ne comprends pas bien ta question. Il faut implémenter toutes les fonctions à partir de la ligne 18. Pour plus de détails sur le but des fonctions, il faut se référer à leur objectif officiel documentation std::deque.

Avant de commencer l'implémentation, il te faut définir la structure interne des données. Tu devrais trouver des infos dans le web. Si on ne t'impose pas de respecter la contrainte Insertion or removal of elements at the end or beginning - constant O(1) et que toute la STL est autorisée, il suffit utiliser en interne un std::vector.

Quant à l'intérêt pédagogique. Ça me parait beaucoup de code à écrire pour peu de chose à retenir. Je dirais intérêt proche de 0 mais je ne suis pas ton prof. Le seul intérêt serait sur l'ensemble du code à écrire pour tester que ton code marche, là il y aurait des choses formatrices.
06/04/2020, 10h16
YumiKi_

Citation:

Envoyé par dalfab

Bonjour,

Avant de commencer l'implémentation, il te faut définir la structure interne des données. Tu devrais trouver des infos dans le web. Si on ne t'impose pas de respecter la contrainte Insertion or removal of elements at the end or beginning - constant O(1) et que toute la STL est autorisée, il suffit utiliser en interne un std::vector.

Bonjour, la problématique, c'est qu'on à pas le droit d'utiliser les autres class de la STL, comme std::vector. ducoup, je pensez faire une structure deque, mais j'arrive pas à faire correspondre ma structure avec la signature, des constructeurs.
De plus, je ne comprend pas l'utilité de initializer_list dans le dernier constructeur avant le destructeur.
06/04/2020, 10h59
foetus

C'est ballot :wow: très ballot :wow: ultra ballot :wow:

Parce qu'en C++, tu ne peux pas utiliser la fonction realloc (<- lien cplusplus.com en anglais) avec le couple new - delete.
:mrgreen: donc pour coder un tableau avec une taille variable soit tu vas détruire tout ton tableau et le recréer en le recopiant soit utiliser une bonne vieille liste chaînée C

Et pour "initializer_list" c'est le constructeur qui est appelé ... avec une liste d'initialisation :wow: std::deque q = {1, 2, 3};.
:whistle: je pense que ce constructeur, tu peux le laisser tomber, parce que tu vas passer un certain temps avec tes pointeurs et tes recopies :aie:
06/04/2020, 11h25
YumiKi_

Et si je décidé d'utiliser le langage C, à la place du C++, pour le projet, avec du-coup la possibilité d'utiliser malloc et realloc, ca donnerai quoi ? les class templates marcherai toujours ?
06/04/2020, 11h48
foetus

Citation:

Envoyé par YumiKi_

class templates marcherai toujours ?

Ben non :wow: template : C++, constructeur/ destructeur : C++, classe (+ encapsulation + héritage) : C++ :zoubi:

Et 1 autre chose, les listes d'initialisation sont une fonctionnalité du C++ moderne (>= C++11)
06/04/2020, 19h17
Pyramidev
Bonjour,

Citation:

Envoyé par YumiKi_

Mon problème, j'ai compris ce qu'était un deque (tableau 2D) cependant je n'arrive pas à comprendre les signatures du profs et débuter le sujet.

Citation:

Envoyé par dalfab

Tout d'abord, un deque n'est pas un tableau 2D. C'est un tableau 1D comme std::vector sauf qu'il est mieux adapté que lui pour faire des ajouts ou suppressions en début de tableau et un peu moins rapide en accès direct à un élément.

Du point de vue de l'utilisateur, std::deque est un tableau 1D. Cependant, dans une implémentation typique, std::deque encapsule un tableau de tableaux tel que tous les sous-tableaux ont la même taille. Donc il encapsule bien un tableau 2D.

Citation:

Envoyé par YumiKi_

Bonjour, la problématique, c'est qu'on à pas le droit d'utiliser les autres class de la STL, comme std::vector.

std::deque encapsulera donc soit un pointeur de tableaux, soit un pointeur de pointeurs.

Remarque : s'il faut implémenter un std::deque à la fois performant et compatible avec les types qui n'ont pas de constructeur par défaut, alors il y a aussi besoin de savoir faire des placement new et des appels explicites au destructeur, typiquement sur des emplacements mémoire de type std::aligned_storage_t<sizeof(T), alignof(T)>. Il s'agit de concepts avancés du C++ qui ne sont normalement jamais utilisés par le commun des mortels.

Mais peut-être que ton professeur s'attend simplement à ce que les élèves fassent une implémentation compatible avec les types qui ont un constructeur par défaut et des affectations de copie et de mouvement. Alors, ton std::deque pourrait encapsuler un pointeur de tableaux d'objets de type T.

EDIT 20h03 : ah, en fait, vu que le prof a écrit :
Code:

1 2 3 4 // ne pas toucher using value_type = T; using size_type = size_t; static T dummy; // pour renvoyer une lvalue lorsque demandé
et :

Code:

template <class T> T deque<T>::dummy = 0;

alors, à cause de cette initialisation à coup de = 0, cette implémentation de std::deque ne pourra de toute façon pas être compatible avec tous les types T avec lesquels elle aurait dû être compatible, à moins que ton prof ne t'autorise à supprimer cette variable dummy à la fin.