Newsgroup: it.comp.lang.c++
Titolo: Dubbi sui vector

Salve sto facendo qualche prova per imparare ad usare il tipo vector.
Ho scritto un piccolo programmino che dovrebbe permettere di inserire degli
elementi in un vector<int>, l'inserzione è fatta in modo che gli elementi
risultino ordinati. Dico dovrebbe perchè ovviamente non funziona, con il 
debugger ho potuto constatare che questo è dovuto al fatto che gli iterator
che uso non risultano correttamente inizializzati, in particolare risultano
sempre uguali a NULL. Il codice è il seguente:
#include <iostream>
#include <vector>
using namespace std;
void insert_sorted(vector<int> &v,int x)
{
   bool insert = false;
   vector<int> ::iterator i ;
   i = v.begin();
   while ( (i!=v.end()) || (!insert))
   {
      if (x<=(*i))
	 i++;
      else
         insert =true;
   }
   v.insert(i,x);
}
int main()
{
   vector<int> v;
   int scelta=0;
   while(scelta!=2)
   {
      cout<<"[1] Inserisci elemento"<<endl;
      cout<<"[2] Quit"<<endl;
      cin>>scelta;
      if (scelta==1)
      {
	 cout<<"Elemento :";
	 int elem;
	 cin>>elem;
	 insert_sorted(v,elem);
      }
      cout<<"Vettore :";
      vector<int>:: iterator i;
      for (i=v.begin();i!=v.end();i++)
	 cout<<*i<<",";
      cout<<endl;
   }
}
In particolare l'errore si verifica all'interno del while contenuto nella 
funzione, infatti alla prima iterazione non dovrebbe proprio entrare nel
corpo del while e andare direttamente alla inserzione, però a causa del 
problema sugli iteratori invece ci entra e l'errore si verifica al tentativo
di dereferencing dell'iteratore.
-- 
  _  _ >>Now on Linux<<  _     || ICQ number.................Non lo uso
 | \| |___ _____ ___ ___|_|___ || Home-Page ................Non ce l'ho
 | .` | -_|     | -_|_ -| |_ -||| E-Mail................Non l'avrai mai
 |_|\_|___|_|_|_|___|___|_|___||| Un Nemesis che ha pochi e-contatti ;)

 corpo del while e andare direttamente alla inserzione,
ma se all'inizio insert vale false allora !insert vale true e quindi nel
while ci entra per forza all'inizio
forse devi mettere && invece di ||
Pela

Pela ha scritto : 

Beh in parte avevi ragione, l'algoritmo era sbagliato, per farlo funzionare
l'ho dovuto modificare cosě :
void insert_sorted(vector<int> &v,int x)
{
   bool insert = false;
   vector<int> ::iterator i ;
   i = v.begin();
   while (!insert)
   {
      if (i==v.end())
      {
	 v.insert(i,x);
	 insert=true;
      }
      else if (x<=(*i))
	 i++;
      else
      {
	 v.insert(i,x);
	 insert =true;
      }
   }
}
Anche se cosě non mi piace molto, ho l'impressione che si potrebbe scrivere
in una forma piů compatta, ma al momento mi manca l'ispirazione.


 l'ispirazione.
 void insert_sorted(vector<int> &v,int x)
 {
   vector<int> ::iterator i = v.begin();
   while( i != v.end() && x < *i ) ++i;  
   v.insert(i,x);
 }

 Salve sto facendo qualche prova per imparare ad usare il tipo vector.
Ti consiglio di studiare la documentazione delle funzioni membro
"reserve()" e "push_back()", e dell'algoritmo "sort()". Secondo gli
esperti e' quasi sempre meglio inserire alla rinfusa e poi ordinare.
Ciao,
Nicola


beh in effetti questo e' addirittura piu' compatto di quanto mi 
aspettassi :)
Ho un solo dubbio pero', alla prima iterazione cioe' quando il vector e'
vuoto, *i non dovrebbe avere senso giusto? Pero' non ricevo errori
perche' viene valutata prima la condizione i!=v.end() che risulta falsa
e dato la && l'altra condizione non viene proprio valutata giusto?
A questo punto poi devo farmi una domanda, il vector e' adatto anche a
contenere tipi di lunghezza variabile? in pratica io dovrei fare un
vector di pacchetti RTP (che sono rappresentati da struct che tra i 
vari
campi hanno un char * rappresentante il payload, che ha lunghezza 
variabile. tutto questo perche' devo creare un buffer con questi 
pacchetti.
Un Nemesis e le reminiscenza del passato.
-- 
  _  _  >>Now at work<<  _     || ICQ number.................Non lo uso
 | \| |___ _____ ___ ___|_|___ || Home-Page ................Non ce l'ho
 | .` | -_|     | -_|_ -| |_ -||| E-Mail................Non l'avrai mai
 |_|\_|___|_|_|_|___|___|_|___||| Un Nemesis che ha pochi e-contatti ;)


beh io ho letto un po' la documentazione e se non ricordo male la 
funzione sort ha una complessita' del tipo  N*log(N), mentre l'algoritmo
di inserzione in ordine che ho scritto io e' lineare.
Inoltre ci sono altre cose da considerare, queste prove sono finalizzate
a qualcosa di piu' complesso, il mio fine e' di bufferizzare delle
struct,
e di ordinare rispetto ad un particolare campo di queste, non so se con
sort si possa fare, inoltre ho la necessita' che il vettore sia sempre
ordinato, quindi dovrei fare sempre il push_back + sort, e penso che 
sarebbe troppo pesante. Infine c'e' da dire che probabilmente la
stragande maggioranza dei numeri che mi arrivano saranno gia in ordine e 
quindi non dovro' nemmeno scorrere il vector per trovare la posizione in
cui inserire, percui penso che questa soluzione sia la migliore. Devo
solo cercare una funzione che mi permetta di estrarre, e cancellare,
l'ultimo elemento della lista (quello piu' piccolo che quindi secondo
l'algoritmo attuale si trova in ultima posizione)
Tuttavia data la mia scarsa esperienza con i container della STL mi
farebbe piacere sentire anche i vostri pareri, su quale sia la soluzione
migliore.
-- 
  _  _  >>Now at work<<  _     || ICQ number.................Non lo uso


 ordinato
Sei sicuro che non sia meglio uno std::set, allora?
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

 l'algoritmo di inserzione in ordine che ho scritto io e' lineare.
lineare per ogni inserimento, cioe' O(n^2) nel caso pessimo 
(inserimento sempre in coda), per inserire n elementi: hai infatti 
n(n+1)/2 iterazioni

 wrote in message
news:Pine.LNX.4.10.101102...@c64.comm2000.it...

oppure:
void insert_sorted(vector<int> &v,int x)
{
  v.insert(find(v.begin(),v.end(),bind2nd(less<int>(),x),x);
}
o meglio ancora (due versioni equivalenti a seconda di cosa considerate
leggibile, io preferisco la seconda anche se va a capo nelle chiamate e
negli assegnamenti):
#include <algorithm>
#include <functional>
tamplate <class Sequence>
void insert_sorted( Sequence &seq, Sequence::const_reference val )
{
  typedef std::less<Sequence::value_type> OpLess;
  std::binder2nd<OpLess> lessThanVal = std::bind2nd( OpLess(), val );
  Sequence::iterator at = std::find( seq.begin(), seq.end(),
lessThanVal );
  seq.insert( at, val );
}
ovvero:
#include <algorithm>
#include <functional>
tamplate <class Sequence>
  void insert_sorted( Sequence &seq, Sequence::const_reference val )
  {
    Sequence::iterator at =
        std::find(
            seq.begin(),
            seq.end(),
            std::bind2nd( std::less<Sequence::value_type>(), val )
        );
    seq.insert( at, val );
  }
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556


Si pero' come dicevo sopra il io devo avere la lista sempre ordinata,
cioe' se faccio N inserimenti devo fare anche N ordinamenti, e quindi
siamo sempre li.
Piuttosto, sarebbe interessante sapere il peso di insert(), visto
che mi trovo ad inserire quasi sempre in testa ne risulta che tutti gli
altri elementi devo shiftare verso destra, ora non so come e' 
implementatoil vector, ma se e' implementato come un array allora lo 
shift ci deve essere veramente, mentre se e' implementato come una 
linked-list allora basterebbe spostare qualche puntatore con conseguente
guadagno di prestazioni. Forse a questo punto mi converrebbe usare al 
posto di vector il tipo list.


 Sei sicuro che non sia meglio uno std::set, allora?
No, nel senso non ne sono sicuro visto che non conosco set :)
Magari se mi puoi dire quali sono i suoi vantaggi...


   }
Non mi vergogno di dire che non c'ho capito una mazza ^___^;;;
Pero' e' bello vedere che ci sono tanti modi diversi per risolvere uno
stesso problema.
Presumo che le tue soluzioni cmq da un punto di vista computazionale
siano equivalenti alla mia o a quella di Max M., cioe' la singola
inserzione richiede una complessita' del tipo o(N), giusto?
-- 
  _  _  >>Now at work<<  _     || ICQ number.................Non lo uso
 | \| |___ _____ ___ ___|_|___ || Home-Page ................Non ce l'ho
 | .` | -_|     | -_|_ -| |_ -||| E-Mail................Non l'avrai mai
 |_|\_|___|_|_|_|___|___|_|___||| Un Nemesis che ha pochi e-contatti ;)

 Magari se mi puoi dire quali sono i suoi vantaggi...
Mantiene un insieme di istanze, tenendole (guarda guarda) sempre
ordinate, e garantendo un tempo di inserzione O(N lnN).  Puoi fornire
tu, nella dichiarazione, un oggetto funzionale che definisca il
criterio di ordinamento (strict weak ordering).


 criterio di ordinamento (strict weak ordering).
Ummm, sembra interessante, dopo gli do un'occhiata.


 Ummm, sembra interessante, dopo gli do un'occhiata.
Gli ho dato un'occhiata, pero' nella descrizione leggo
... it is also a Unique Associative Container, meaning that no two 
elements are the same. 
Quindi in pratica mi sembra di capire che non posso inserire due oggetti
caratterizzati dalla stessa chiave di ordinamento, e questo non mi va 
bene.


 bene.
Allora usa i multiset
Ciao
Gaetano.
-- 
Posted from 
dell-01.mm.eutelsat.org
 [194.214.173.17] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 bene.
Usa un multiset, allora.


 siamo sempre li.
no, siamo al punto che ti conviene usare std::set se non hai elementi 
ripetuti o std::multiset se hai elementi ripetuti.
entrambi usano una binary_search() per l'inserzione che garantisce 
tempi Nlog2(N) per N inserzioni, e risultano automaticamente ordinati.

 inserzione richiede una complessita' del tipo o(N), giusto?
Dovresti poterti rispondere da solo.


bene.
Infatti, gli std::set non ti permettono di inserire due elementi
uguali(il secondo ti viene automaticamente scartato), quindi gli
std::multiset  sono più appropriati.
Il Ghenio
-----
These are my parting words to you:
those who give up are doomed!
-----

 ordinato, quindi dovrei fare sempre il push_back + sort,
Questo č un altro discorso. Ma allora credo che ti convenga avere una
operazione di
inserimento O(log(N)) invece che una O(N). Quindi usa un set o un
multiset.


 ordinate, e garantendo un tempo di inserzione O(N lnN).
Sicuro che non fosse semplicemente O(lnN) ?


 posto di vector il tipo list.
Ti conviene multiset.
Comunque se il motivo per passare a list invece che vector è che
inserisci in testa, allora ti conviene deque. Soprattutto se poi fai
accessi random. O meglio ancora invertire l'ordine del vettore e
lavorare in coda. Ma ripeto: credo proprio ti convenga miltiset.


 lavorare in coda. Ma ripeto: credo proprio ti convenga miltiset.
Beh viste le numerose segnalazioni credo proprio che la soluzione 
migliore sia multiset, in realta' per il momento l'emergenza e'
rientrata
quindi non mi serve piu', pero' piu' in la potrebbe tornari utile.
Grazie a tutti per le risposte.


 multiset.
Come fa ad essere O(log(N)) usa una ricerca binaria?


 Come fa ad essere O(log(N)) usa una ricerca binaria?
Usa un R/B Tree. Quindi di fatto l'inserimento corrisponde ad una
ricerca binaria.


 Come fa ad essere O(log(N)) usa una ricerca binaria?
si, di solito si usa binary_search per l'inserzione, ma non e' 
specificato, dice solo che l'insert deve essere di complessita' 
logaritmica (table 69)

 ricerca binaria.
vuoi dire che deve usare un rbtree "per forza"?
dove lo si specifica?

"Aloha" <aha...@laugh.doh> wrote in message
news:1457855.y...@iol.it...

Mi avevi chiesto se l'inserimento era O(log N) perchè usava una ricerca
dicotomica. Ci sono due risposte:
1) l'inserimento è O(log N) perchè richiesto dallo standard, come fa a
farlo sono cavoli suoi.
2) la struttura sottostante è nella stragrande maggioranza dei casi un
R/B Tree, quindi di fatto inserimento = ricerca binaria.
Non deve usare un rbtree per forza. Ma deve fare inserimenti, ricerche e
cancellazioni in O(log N) e questo lo si ottiene di solito con un
rbtree.


 rbtree.
anche con un semplice albero binario, o una dicotomica su una lista 
ordinata

 ordinata
Senza un meccanismo di bilanciamento non c'e' garanzia che l'albero non
degeneri e la ricerca su una lista e' comunque lineare, non avendo
accesso diretto.
Ciao,
Nicola

 accesso diretto.
si, e' piu' corretto dire un array ordinato, anche se nel riallocare si 
perderebbe efficienza

 ordinata
Su una lista, anche se ordinata, è difficile fare una ricerca dicotomica
visto che l'accesso è sequenziale. Su un vettore puoi fare la ricerca
... ma non l'inserzione e la cancellazione. Su un albero binario
semplice la ricerca (e quindi le altre operazioni) sono dicotomiche solo
se l'albero è bilanciato. Un rbtree altro non è che un semplice albero
binario con intrinseco nell'inserimento e nella cancellazione un
algoritmo di ribilanciamento.


"Aloha" <aha...@laugh.doh> wrote in message
news:24493860....@iol.it...

Entrambe i casi non sarebbero standard. Perrchè lo standard impone che
sia la ricerca che l'inserimento che la cancellazione siano sempre O(log
N).
