élément sortant la dernière pour les éléments non par défaut constructible

Question

de travail sur une classe d'arbre avec une interface STL-like, j'ai rencontré un problème en utilisant non des éléments par défaut constructible:

Comme je suis la mise en œuvre itérateurs, je besoin d'un élément passé-dernier à tout moment. Mon approche est d'en créer un dans le constructeur, qui affirme que le type de valeur est constructible par défaut.

Existe-t-il une approche pour se débarrasser de cette contrainte?

Answer 1

La fin de la fin ne peut pas être nullptr si votre itérateur est bidirectionnel, end()-- doit être légale.

Il peut être implémenté à la place par une sentinelle, et dans ce cas, la sentinelle ne devrait même pas contenir un élément construit par défaut.

Cela peut être fait en tant que telle

struct link 
{ 
    link *parent, *left, *right; 
}; 

template<typename T> 
struct node : link 
{ 
    T data; 
}; 

template<typename T> 
struct tree : link 
{ 
    // tree itself serves as the sentinel 
    // At initialization parent and childs should all point to the sentinel 
    tree() : parent(this), left(this), right(this) {} 

    // ... 
}; 

Et itérateurs ont pas besoin d'un traitement spécial pour le cas passé final.

// nested within tree 
struct iterator 
{ 
    explicit iterator(link* l) : n(l) {} 
    iterator& operator--() { n = n->parent; return *this; } // or something else 
    auto& operator*() { return reinterpret_cast<node<T>*>(n)->data; } 

    // ... 

    link* n; 
}; 
iterator begin() { return {left}; } // or something else 
iterator end() { return {this}; } 

Answer 2

I a résolu le problème en stockant un autre pointeur vers le noeud racine, à partir de laquelle je peux recréer le dernier élément de constante de temps.