[C++] qualche domandina su array e iteratori

[Don[ITA]]

Salve a tutti :)
Per un progetto universitario dovrei realizzare un'implementazione di coda FIFO che utilizzi una struttura dati di tipo array.
Ora ecco le mie perplessità:
-se io avessi una struct fatta così:

struct Dato {
int a;
double b;
string c;
}

e mi creassi un array di tale struttura, dove verrebbe allocato tare array?

Dato dati[100]; //è allocato nello stack o nello heap??? (suppongo stack)
Dato *dati = new Dato[100]; //stessa domanda di prima (suppongo heap)

-come potrei realizzare un iteratore che mi iteri su un array?

Spero di non aver contravvenuto a nessuna regola chiedendovi queste cose :) Ovviamente con la seconda domanda non vi chiedo l'implementazione di un iteratore su array ma soltanto un idea di come realizzarlo :D

Grazie e saluti

[cionci]

Nel primo caso il vettore è allocato nello stack, ma ciò non esclude che l'elemento c possa allocare spazio nello heap (è una string).

Nel secondo caso il puntatore dati è allocato nello stack, la memoria puntata da dati è allocata nello heap.

Spiega meglio il caso in cui ti serve questo iteratore.

[Don[ITA]]

Ok allora la questione degli array è come la supponevo io :D
Quell'iteratore mi serve per un accesso in lettura e scrittura dei dati contenuti nell'array.
Ora non capisco però a cosa mi serva iterare su una coda fifo...dopotutto devo solo aggiungere elementi in coda e prelevarli in testa :mbe:
Può essere che l'iteratore mi serva proprio per la gestione degli inserimenti/estrazioni dei dati?

Grazie per la risposta :D

[cionci]

Ti chiedevo appunto di chiarire meglio la questione dell'iteratore.
Mi sembra di capire che tu non voglia usare gli iteratori del C++, ma crearti un tuo iteratore non "imparentato" con quelli.
Sicuramente puoi costruirti un iteratore per scorrere tutti gli elementi dalla testa alla coda o viceversa.
La Fifo mi immagino che sia circolare...giusto ?

[Don[ITA]]

Non è che non voglio usarli eheh è che non posso :D
Fosse stato per me non mi sarei nemmeno messo a reinventarmi la ruota con un progetto del genere :D dopotutto nelle stl la collezione queue gia esiste :D
Ora vedo di buttare giu del codice che qualche idea mi è venuta :D

Grazie mille per le risposte :)

[Vincenzo1968]

In effetti non hai bisogno di un iteratore. Per implementare una coda tramite array(si può implementare anche con lista concatenata), devi mantenere due indici. Il primo, head, punta al primo elemento; il secondo, tail, punta all'ultimo.

Il codice seguente implementa una coda di interi(è in C ma puoi facilmente adattarlo ;)):


#include <stdio.h>

#define max 50

static int queue[max+1], head, tail;

void queue_put(int v)
{
queue[tail++] = v;
if ( tail > max )
tail = 0;
}

int queue_get()
{
int t = queue[head++];
if ( head > max )
head = 0;
return t;
}

void queue_init()
{
head = tail = 0;
}

int queue_empty()
{
return head == tail;
}

int main()
{
queue_init();

queue_put(5);
queue_put(8);
queue_put(13);
queue_put(21);
queue_put(55);

while ( !queue_empty() )
printf("%d\n", queue_get());

return 0;
}

[Don[ITA]]

Sono riuscito ad implementare sta maledetta coda appoggiandomi su un array circolare che viene riallocato quando è pieno. Ho anche implementato gli iteratori (che ovviamente sono inutili su una coda, ma che il prof ci ha richiesto), ma ora stò maledettamente appeso su una cosa....l'operator=
Vi posto il codice incriminato:
file coda_i.hpp

template <typename T>
coda<T>::coda(const coda<T>& c) : n_elementi(0), max_elementi(5), h_index(0), t_index(0) {
if(c.isEmpty())
return;
n_elementi = c.n_elementi;
max_elementi = c.max_elementi;
dati = new typename coda<T>::dato_t[max_elementi];
for(int i = 0; i < n_elementi; i++) dati[i] = c.dati[i];
h_index = c.h_index;
t_index = c.t_index;
}

template <typename T>
coda<T>& coda<T>::operator=(const coda<T>& c) {
if(this == &c)
return *this;
coda<T> tmp(c); //non lavora correttamente e non sò perchè!!!
tmp.swap(*this);
return *this;
}

template <typename T>
void coda<T>::swap(coda<T>& c) {
std::swap(c.n_elementi, n_elementi);
std::swap(c.max_elementi, max_elementi);
std::swap(c.h_index, h_index);
std::swap(c.t_index, t_index);
std::swap(c.dati, dati);
}


file main.cpp

void testCostruttori() {
coda<char*> c;
c.enqueue("ciao");
c.enqueue("sono");
c.enqueue("una");
c.enqueue("stringa");
cout << c << endl;

coda<char*> c1(c);
c1.dequeue();
cout << c1 << endl;

/*Codice che genera l'errore!!!
coda<char*> c2;
c2 = c1;
c2.dequeue();
cout << c2 << endl;*/
}


Quando tento di eseguire il codice nel main che vi ho postato, l'applicazione esplode!!!
Sono riuscito a risalire all'esatta riga che fallisce ed è quella boldata in doda_i.hpp. Praticamente creo una coda temporanea mediante il copy constructor (che funziona alla grande, l'ho provato miliardi di volte), e poi vado a scambiare i valori della mia coda con quelli della coda temporanea che a fine scope verrà automaticamente distrutta...Il problema è che se vado a stampare quella coda temporanea subito dopo la sua creazione, mi sono accorto che, a differenza delle altre code che creo per copia e che sono perfette, questa contiene un array di dati che è sbagliato!!! Solo che non sò come mai :cry:
Suggerimenti??

Grazie in anticipo

Saluti

[Maurogiuseppe]

Ma a te interessa la coda con puntatori o con vettore circolare? Se ti servono entrambe posso mandarti tutto tramite mail. :D

[Don[ITA]]

Tranco ho risolto tutto :D facevo boiate io eheheh
Cmq a me interessa una coda implementata mediante array circolare sulla quale poi ci devo appoggiare degli iteratori, per poterla usare con gli algoritmi della stl (mi bastano i forward_iterator).
Ora, io ho fatto tutto ma voci di corridoio dicono che la mia implementazione non piaccia molto, praticamente negli iteratori scorro l'array mediante indici, mentre il prof preferirebbe l'utilizzo di puntatori...ora vedo se riesco a tirare fuori il coniglio dal cilindro :D
La mia idea per far contento il prof era questa:
-uso un array circolare per la mia coda
-faccio gli enqueue e dequeue in modo opportuno (sistemando gli indici con il gioco del modulo)
-se la coda è piena la espando (con un nuovo array che poi swappo)
-quando chiamo begin (che ritorna l'iteratore corrispondente alla testa), se l'indice di testa non è in 0, sistemo la coda (sposto tutti gli elementi in modo che la testa stia in 0)
-uso degli iteratori banalissimi che mi incrementano il puntatore del mio array per scorrerlo
Il problema è che sta cosa la posso fare tranzollamente con gli iterator, ma con i const_iterator giustamente non posso modificare nulla della coda (sono appunto const) quindi non posso risistemare l'array...
Devo trovare una soluzione elegante a questo problema visto che l'alternativa è quella di sistemare l'array ad ogni dequeue e quindi dimenticarmi dell'array circolare :cry: