Un iteratore ha un contratto implicito non distruttivo?

10

Diciamo che sto progettando una struttura dati personalizzata come uno stack o una coda (per esempio - potrebbe essere un'altra raccolta arbitraria ordinata che ha l'equivalente logico di push e pop metodi - cioè metodi accessor distruttivi) .

Se stavi implementando un iteratore (in .NET, in particolare IEnumerable<T> ) su questa raccolta che ha fatto scoppiare su ogni iterazione, sarebbe quello di interrompere il contratto implicito di IEnumerable<T> ?

IEnumerable<T> ha questo contratto implicito?

es .:

public IEnumerator<T> GetEnumerator()
{
    if (this.list.Count > 0)
        yield return this.Pop();
    else
        yield break;
}
    
posta Steven Evers 20.02.2012 - 07:03
fonte

4 risposte

11

Credo che un Enumeratore distruttivo vìoli il Principio di Almostonment . Come esempio forzato, immagina una libreria di oggetti business che offre funzioni di convenienza generiche. Scrivo innocentemente una funzione che aggiorna una collezione di oggetti business:

static void UpdateStatus<T>(IEnumerable<T> collection) where T : IBusinessObject
{
    foreach (var item in collection)
    {
        item.Status = BusinessObjectStatus.Foo;
    }
}

Un altro sviluppatore che non sa nulla della mia implementazione o della sua implementazione decide innocentemente di utilizzare entrambi. È probabile che saranno sorpresi dal risultato:

//developer uses your type without thinking about the details
var collection = GetYourEnumerableType<SomeBusinessObject>();

//developer uses my function without thinking about the details
UpdateStatus<SomeBusinessObject>(collection);

Anche se lo sviluppatore è a conoscenza dell'enumerazione distruttiva, potrebbe non pensare alle ripercussioni quando consegna la raccolta a una funzione black-box. Come autore di UpdateStatus , probabilmente non considererò l'enumerazione distruttiva nella mia progettazione.

Tuttavia, è solo un contratto implicito. Le raccolte .NET, incluso Stack<T> , applicano un contratto esplicito con il loro InvalidOperationException - "La raccolta è stata modificata dopo la creazione dell'istanza dell'enumeratore". Potresti obiettare che un vero professionista ha un atteggiamento caveat emptor verso qualsiasi codice che non sia il loro. La sorpresa di un enumeratore distruttivo sarebbe stata scoperta con un test minimo.

    
risposta data 20.02.2012 - 18:07
fonte
1

Una delle sfide di codifica più interessanti che mi sono state date per un'intervista era creare una coda funzionale. Il requisito era che ogni chiamata ad accodamento creava una nuova coda che conteneva la vecchia coda e il nuovo elemento alla coda. Dequeue restituirebbe anche una nuova coda e l'elemento in coda deselezionata come un parametro out.

La creazione di un IEnumerator da questa implementazione sarebbe non distruttiva. E lasciatemi dire che implementare una coda funzionale che si comporta bene è molto più difficile dell'implementazione di uno stack funzionale performante (stack Push / Pop funzionano entrambi sulla coda, perché una coda accoda sulla coda, deseleziona i lavori sulla testa).

Il mio punto è ... è banale creare un Enumeratore di Stack non distruttivo implementando il proprio meccanismo di Puntatore (StackNode & Tt; T >) e utilizzando la semantica funzionale nell'Enumeratore.

public class Stack<T> implements IEnumerator<T>
{
  private class StackNode<T>
  {
    private readonly T _data;
    private readonly StackNode<T> _next;
    public StackNode(T data, StackNode<T> next)
    {
       _data=data;
       _next=next;
    }
    public <T> Data{get {return _data;}}
    public StackNode<T> Next{get {return _Next;}}
  }

  private StackNode<T> _head;

  public void Push(T item)
  {
    _head =new StackNode<T>(item,_head);
  }

  public T Pop()
  {
    //Add in handling for a null head (i.e. fresh stack)
    var temp=_head.Data;
    _head=_head.Next;
    return temp;
  }

  ///Here's the fun part
  public IEnumerator<T> GetEnumerator()
  {
    //make a copy.
    var current=_head;
    while(current!=null)
    {
       yield return current.Data;
       current=_head.Next;
    }
  }    
}

Alcune cose da notare. Una chiamata a push o pop prima dell'istruzione current = _head; Completi ti darebbe uno stack diverso per l'enumerazione rispetto a se non ci fosse il multithreading (potresti voler usare un ReaderWriterLock per salvaguardare questo). Ho reso i campi in StackNode in sola lettura, ma ovviamente se T è un oggetto mutabile, puoi cambiarne i valori. Se si dovesse creare un costruttore Stack che ha preso un StackNode come parametro (e impostare la testa su quello passato nel nodo). Due pile costruite in questo modo non si influenzeranno a vicenda (ad eccezione di un T mutabile come ho detto). Puoi spingere e far saltare tutto ciò che vuoi in una pila, l'altra non cambierà.

E che mio amico è come fai l'enumerazione non distruttiva di uno Stack.

    
risposta data 20.02.2012 - 20:06
fonte
0

Nel tentativo di mantenere le cose "semplici", .NET ha solo una coppia di interfacce generiche / non generiche per cose che sono enumerate chiamando GetEnumerator() e quindi usando MoveNext e Current sull'oggetto ricevuto da ciò, anche se ci sono almeno quattro tipi di oggetti che dovrebbero supportare solo quei metodi:

  1. Cose che possono essere enumerate almeno una volta, ma non necessariamente di più.
  2. Cose che possono essere enumerate un numero arbitrario di volte in contesti free-threaded, ma possono produrre arbitrariamente contenuti diversi ogni volta
  3. Cose che possono essere enumerate un numero arbitrario di volte in contesti free-threaded, ma possono garantire che se il codice che le enumera ripetutamente non chiama alcun metodo di muting, tutte le enumerazioni restituiranno lo stesso contenuto.
  4. Cose che possono essere enumerate un numero arbitrario di volte e sono garantite per restituire lo stesso contenuto ogni volta che esistono.

Ogni istanza che soddisfi una delle definizioni con numero più alto soddisferà anche tutte quelle inferiori, ma il codice che richiede un oggetto che soddisfi una delle definizioni più alte potrebbe interrompersi se viene fornito uno di quelli inferiori.

Sembra che Microsoft abbia deciso che le classi che implementano IEnumerable<T> dovrebbero soddisfare la seconda definizione, ma non sono obbligate a soddisfare nulla di più elevato. Probabilmente, non c'è molta ragione per cui qualcosa che potrebbe soddisfare solo la prima definizione dovrebbe implementare IEnumerable<T> piuttosto che IEnumerator<T> ; se foreach loop potrebbe accettare IEnumerator<T> , avrebbe senso per cose che possono essere enumerate solo una volta per implementare semplicemente quest'ultima interfaccia. Sfortunatamente, i tipi che implementano solo IEnumerator<T> sono meno convenienti da utilizzare in C # e VB.NET rispetto ai tipi che hanno un metodo GetEnumerator .

In ogni caso, anche se sarebbe utile se ci fossero diversi tipi enumerabili per cose che potrebbero dare garanzie diverse, e / o un modo standard per chiedere un'istanza che implementa IEnumerable<T> quali garanzie può fare, nessuna di queste tipi ancora esistenti.

    
risposta data 16.02.2014 - 19:34
fonte
0

Penso che questa sarebbe una violazione del principio di sostituzione di Liskov che afferma,

objects in a program should be replaceable with instances of their subtypes without altering the correctness of that program.

Se avessi un metodo come il seguente che viene chiamato più di una volta nel mio programma,

PrintCollection<T>(IEnumerable<T> collection)
{
    foreach (T item in collection)
    {
        Console.WriteLine(item);
    }
}

Dovrei essere in grado di scambiare qualsiasi oggetto IEnumerable senza alterare la correttezza del programma, ma l'uso della coda distruttiva potrebbe alterare il comportamento del programma in modo estensivo.

    
risposta data 17.02.2014 - 00:01
fonte

Leggi altre domande sui tag