[Java] Implementazione del tipo set

[LiLyblack]

Ciao a tutti, mi servirebbe un consiglio sulla scelta del tipo di dato da utilizzare nell'implementazione di una classe Set, dove Set indica tipi mutable, illimitati insieme di Object.

Il mio dubbio è questo: è meglio utilizzare un Vector per memorizzare tutti gli Object (Vector els, per intenderci) oppure un vettore di Object (Object [] els)?
Ed eventualmente per quali motivi?

Tra le specifiche è scritto che "Set può contenere oggetti di qualsiasi tipo, usando nell'implementazione il tipo Object"
Non mi è molto chiaro; significa che sono costretta ad utilizzare un vettore di Object? Oppure più semplicemente si intende che gli elementi che andranno a formare un insieme set sono di tipo object?

Grazie a chi mi risponderà.

Lily

[andbin]

Per 'set', almeno per quanto riguarda il "collections framework" di Java, si intende una collezione di oggetti che non può contenere duplicati.
Come implementare un 'set' dipende da tanti fattori, principalmente dalla efficienza che si vuole ottenere per le principali operazioni come inserimento, ricerca, iterazione ecc....

[LiLyblack]

Nel mio caso Set è un insieme di Object, non contenente duplicati e di tipo mutable.
Chiaramente voglio ottenere le operazioni di insert, delete e search nel miglior tempo possibile.

Stavo riflettendo sul fatto che un vettore di Object non è una buona soluzione, in quanto il tipo di dato da implementare è mutable.
Per questo penso che la soluzione più adeguata sia utilizzare un Vector. Utilizzare un array di Object penso sia una scelta masochista.

Correggetemi se sbaglio

Lily

[andbin]

Originariamente inviato da LiLyblack
Nel mio caso Set è un insieme di Object, non contenente duplicati e di tipo mutable.
Chiaramente voglio ottenere le operazioni di insert, delete e search nel miglior tempo possibile.

Ma conosci il "collections framework" di Java??? Certo ... tu devi implementare un set, non usarne uno già fatto. Ma se conoscessi quel framework, sapresti le differenza tra una e l'altra implementazione.

Originariamente inviato da LiLyblack
Stavo riflettendo sul fatto che un vettore di Object non è una buona soluzione, in quanto il tipo di dato da implementare è mutable.

Usare un array mica vuol dire che la collezione diventa automaticamente immutabile! Semmai vuol solo dire che è inefficiente la ricerca.

La classe java.util.ArrayList è basata appunto su un array. Quando la capacità non è più sufficiente, crea un nuovo array e ricopia gli elementi.

[LiLyblack]

Ma conosci il "collections framework" di Java???

No, non lo conosco; mi documenterò

Usare un array mica vuol dire che la collezione diventa automaticamente immutabile! Semmai vuol solo dire che è inefficiente la ricerca.

Di certo, non diviene immutabile, ci mancherebbe
Ma essendo il mio un tipo mutabile, credo sia preferibile utilizzare un vettore espandibile.

[andbin]

Originariamente inviato da LiLyblack
No, non lo conosco; mi documenterò

- The Collections Framework
- Introduction to the Collections Framework

Originariamente inviato da LiLyblack
Di certo, non diviene immutabile, ci mancherebbe
Ma essendo il mio un tipo mutabile, credo sia preferibile utilizzare un vettore espandibile.

Non è una questione di array o "vettore espandibile" .... devi capire prima la questione della efficienza di una struttura dati.

[LiLyblack]

Grazie per i link.
Per quello che devo fare, sono ancora più convinta che debba usare un Vector.

[andbin]

Originariamente inviato da LiLyblack
Per quello che devo fare, sono ancora più convinta che debba usare un Vector.

E perché allora non ArrayList piuttosto che Vector??

Altra cosa: immagino che quello che devi fare sia un esercizio "didattico" (per scuola/università non so ...) quindi bisogna vedere se ti è permesso (e magari ti è stato chiesto/suggerito) di usare collezioni del framework di Java. Perché una cosa è implementare da zero una collezione, un'altra è basarsi su qualcosa di già fatto. Usare un ArrayList/Vector per un 'set', sebbene possa poi risultare molto inefficiente, è abbastanza banale.

[LiLyblack]

Sì, è un esercizio per l'università.
Non uso gli ArrayList perché è una struttura dati che non conosco e che non si è trattata.. e non penso che l'obiettivo sia quello di introdurle in questo esercizio. Comunque, quello che devo fare io è implementare da zero.

Grazie per aver risposto.

[andbin]

Originariamente inviato da LiLyblack
Non uso gli ArrayList perché è una struttura dati che non conosco e che non si è trattata.. e non penso che l'obiettivo sia quello di introdurle in questo esercizio.

ArrayList e Vector concettualmente fanno la stessa identica cosa, sono entrambe la implementazione di "un array ridimensionabile di oggetti". Il fatto è che Vector è la "vecchia" collezione legacy presente fin dall'inizio di Java e mantenuta ancora oggi per ovvi motivi di compatibilità. ArrayList è la nuova collezione presente da Java 1.2 in poi.
La principale e grossa differenza tra i due è che Vector è synchronized mentre ArrayList non lo è.
Tutto qua.

Originariamente inviato da LiLyblack
Comunque, quello che devo fare io è implementare da zero.

Quindi senza usare alcuna collezione già fatta, giusto?

Allora senza andare a cercare performance o altro, prova a gestirla tramite un normale array. È chiaro che tutta la logica di espansione/ridimensionamento devi implementarla tu. Se inserisci un elemento e la capacità dell'array non è più sufficiente, devi creare un nuovo array più grande e ricopiare gli elementi. Molto probabilmente, credo, è questo che ti si chiede di fare. Altrimenti usare una collezione tipo ArrayList/Vector sarebbe banale e lineare.

Comunque, come suggerimento, prova a scrivere del codice e se hai dubbi posta pure il codice e chiedi aiuto. Finché continuiamo a parlarne non credo che si possa andare molto avanti. Cioè posso darti tutte le informazioni che vuoi sul collections framework e fornirti suggerimenti ma quello che poi conta è che tu riesca a scrivere questa collezione che devi fare.