Newsgroup: it.comp.lang.c++
Titolo: Ordinamento stringhe

Sto usando il Borland C++ Builder 3 e le VCL per scrivere una semplice
applicazione. In particolare, devo risolvere il problema di gestire una
lista di stringhe e di ordinarla secondo la lunghezza delle stesse (quindi
non in modo alfabetico). Ho fino ad ora usato la classe TStringList che
permette automaticamente di tenere ordinata una tale lista, ma l'unico
criterio disponibile e' quello alfabetico ascendente. Ho visto che esiste
anche una classe piu' generica chiamata TList che permette di definire un
criterio arbitrario di ordinamento della lista (ma non capisco come si
faccia), pero' non mi sembra altrettanto adeguata, visto che poi devo
"riversare" il contenuto della lista di stringhe in una listbox (e con un
oggetto TStringList questo e' molto facile).
Qualcuno sa come risolvere questo problema senza dover stare a riscrivere un
algoritmo di ordinamento su misura?
grazie per l'aiuto
Davide Martinenghi

Ciao Davide, non dovrebbe essere difficile usare TList. Ti spiego come
farlo:
TList::Sort() effettua un QuickSort sulla lista basandosi sul risultato
della
funzione Compare definita come segue:
typedef int __fastcall (*TListSortCompare)(void * Item1, void * Item2);
void __fastcall Sort(TListSortCompare Compare);
Compare deve ritornare un valore < 0 se Item1 e' minore di Item2, 0 se sono
uguali e > 0 se Item1 e' maggiore di Item2.
Siccome a te interessa che l'ordinamento sia fatto sulla lunghezza della
stringa,
devi confrontare le lunghezze di due stringhe e far ritornare il valore
esatto.
Ora, il problema e' che TList funziona con tipi void * e non con oggetti
(come
AnsiString), per cui e' necessario incapsulare la stringa all'interno di un
tipo C
come una struct:
typedef struct ASItem_tag {
    AnsiString Item;
} ASItem;
typedef ASItem* pASItem;
In questo modo e' possibile confrontare le lunghezze delle stringhe nella
funzione
Compare, effettuando il cast al tipo pASItem:
int __fastcall MyCompare(void *Items1, void *Items2)
{
    return (pASItem(Items1)->Item.Length() -
pASItem(Items2)->Item.Length());
}
Naturalmente viene meno la comodita' di TStringList, per questo devi gestire
da
solo l'inserimento delle stringhe ordinate nella ListBox. Facciamo un
esempio:
in un form (nome Form1) inserisci un TListBox (nome ListBox1), un campo
TEdit
(nome Edit1) nel quale inserire le frasi da aggiungere al ListBox1 e un
pulsante
(nome Button1) alla pressione del quale avviene l'inserimento del testo
contenuto
in Edit1 all'interno di ListBox1. Questo e' il codice completo; il grosso
della
operazione (inseriemento e ordinamento) avviene nella funzione che gestisce
l'evento
OnClick su Button1.
//--------------------------------
MAIN.H ---------------------------------------------
class TForm1 : public TForm
{
__published: // IDE-managed Components
    TListBox *ListBox1;
    TEdit *Edit1;
    TButton *Button1;
    void __fastcall Button1Click(TObject *Sender);
private: // User declarations
    TList *MyList;
public:  // User declarations
    __fastcall TForm1(TComponent* Owner);
};
//--------------------------------------------------------------------------
-
extern PACKAGE TForm1 *Form1;
//--------------------------------------------------------------------------
-
int __fastcall MyCompare(void *Items1, void *Items2);
typedef struct ASItem_tag {
    AnsiString Item;
} ASItem;
typedef ASItem* pASItem;
//--------------------------------
MAIN.CPP ---------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
    MyList = new TList;
}
//--------------------------------------------------------------------------
-
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    pASItem newItem = new ASItem;
    newItem->Item = Edit1->Text;
    try {
        MyList->Add(newItem);
    }
    catch (Exception &exception)
    {
        Application->ShowException(&exception);
    }
    MyList->Sort(MyCompare);
    ListBox1->Items->Clear();
    for (int i = 0; i < MyList->Count; i++)
        ListBox1->Items->Add(pASItem(MyList->Items[i])->Item);
}
//--------------------------------------------------------------------------
-
int __fastcall MyCompare(void *Items1, void *Items2)
{
    return (pASItem(Items1)->Item.Length() -
pASItem(Items2)->Item.Length());
}
//--------------------------------------------------------------------------
-
Spero di esserti stata d'aiuto. Ciao e a risentirci :-)
Silvia G.  < silv...@XXX.net -- sostituire 'XXX' con 'usa' per risposte in
email >


 tipo C come una struct:
Ma TList non si occupa di gestire solamente un insieme di puntatori, di
qualsiasi tipo?
Perchè non funziona con la classe AnsiString, o meglio con puntatori di
tipo AnsiString ?
A dir la verità non ho mai provato.
Per brevità non riporto qui il tuo codice, però mi pare che manchi
l'istruzione per liberare la memoria allocata da MyList. Magari il
Builder lo fa da solo, ma così, tanto per essere sicuri:
if(MyList) delete MyList;
magari in OnDestroy del form principale.
Seconda cosa. In un articolo su 'CPB Developer's Journal': "The right
list for the right job", Kent Reisdorph parlava proprio di TList e della
necessità di deallocare tutti gli oggetti referenziati dai puntatori che
'contiene', nonostante la funzione Clear() ,stando all'help, dovrebbe
fare tutto da sè.
Ecco cosa dice:
"Do you delete or do I?
It's important to note that the TList class doesn't "own" the objects it
stores. In other words, you're responsible for freeing the memory
associated with each object in the list. The VCL documentation is
somewhat confusing on this issue. Depending on how you read the
documentation for Tlist, you might conclude that TList will free the
memory associated with each object in the array when the list itself is
deleted. This is not the case. It's your responsibility to delete all
the objects in the container before deleting the container itself. The
same is true if you delete a particular item from the list—you must
delete the object. In short, don't assume anything."
Quindi:
for (int i=0;MyList->Count;i++) { 
     pASItem mo = (pASItem)MyList->Items[i];
     delete mo;
     MyList->Items[i] = 0;
}
MyList->Clear();
delete MyList;
Ciao e a presto.
Roberto Gerola.

dama wrote:
[Ordinamento stringhe in base alla lunghezza]
Ecco una alternativa usando STL a quanto proposto da Silvia.
Piccola premessa: non sono un esperto nell'uso di STL. La sto studiando
proprio in questi giorni.
Sentitevi liberi di 'innondare' il mio codice di correzioni o migliorie
: sono qui anche per imparare  :-).
Quello che segue è stato reso possibile anche da quanto postato da Alex
Martelli nel thread 'Esempi di C++'
(messaggi di cui conservo triplice copia in cassaforte al titanio in
atmosfera controllata! :-) )
--Unit1.h:
//---------------------------------------------------------------------------
#ifndef Unit1H
#define Unit1H
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<string> TStringhe;
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:	// IDE-managed Components
    TButton *Button1;
    TListBox *ListBox1;
    void __fastcall Button1Click(TObject *Sender);
private:	// User declarations
public:		// User declarations
    __fastcall TForm1(TComponent* Owner);
};
inline int confronta(const string& stringa1, const string& stringa2);
inline void copia(const string& stringa);
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
--Unit1.cpp:
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------
inline int confronta(const string& stringa1, const string& stringa2){
 //definisco la modalità di ordinamento delle stringhe
 return stringa1.length()<stringa2.length();
}
//---------------------------------------------------------------------------
inline void copia(const string& stringa){
 //inserisco le stringhe nella listbox
 //ho dovuto passare un char*, perchè TStrings non accetta il tipo
string
 Form1->ListBox1->Items->Add(stringa.c_str());
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 TStringhe Stringhe; //contenitore delle stringhe
 //inserisco le stringhe
 Stringhe.push_back("Pippo Pippo");
 Stringhe.push_back("22");
 Stringhe.push_back("55555");
 Stringhe.push_back("666666");
 Stringhe.push_back("1");
 Stringhe.push_back("333");
 Stringhe.push_back("4444");
 //ordino le stringhe
 sort(Stringhe.begin(),Stringhe.end(),confronta);
 //pulisco la listbox
 ListBox1->Clear();
 //copio le stringhe nella listbox
 //non so se si riesce a fare anche con copy.. temo di no
 for_each(Stringhe.begin(),Stringhe.end(),copia);
 }
//---------------------------------------------------------------------------
Effettivamente mi sembra molto più elegante che usare TList.
Ciao




--Unit1.h:





#endif
--Unit1.cpp:
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop




 //ordino le stringhe
 sort(Stringhe.begin(),Stringhe.end(),confronta);


Ciao

Builder lo fa da solo, ma così, tanto per essere sicuri:
Magari ci fosse una Garbage Collection come in Java!!! Sia lodato il dio
Sole (Sun).
Il codice era solo esemplicativo, gia' e' troppo che c'era il try prima di
MyList->Add(newItem);
Ognuno poi e' libero di apportare le modifiche e miglioramenti del caso.
Comunque grazie per avermelo fatto notare e grazie per l'articolo preso da
CPB, avevo dei dubbi che un solo delete non bastasse, e infatti...
A proposito, come ti arriva CPB, a casa come rivista o lo prendi da
Internet?
Ciao e buon lavoro a tutti.
Stefano Tempesta
s.tem...@usa.net
--------------------------------
<<< Think indipendent,
cos' indipendent you can't be >>>

Grazie innanzitutto per le risposte al mio messaggio, mi sono state molto
utili.
A questo punto mi chiedo se si possa trovare una documentazione per le STL
più facilmente "navigabile" rispetto ai file per Word inclusi nel pacchetto
del Borland C++ Builder. Su internet sono riuscito a trovare un manuale
HTML:
http://www.sgi.com/Technology/STL/
Non esiste un Help per windows delle STL?
Il mio problema originario aggiungeva poi un ulteriore vincolo: la lista di
stringhe non ammette duplicati. Una prima banale (e non soddisfacente)
soluzione consiste nel controllare che tale stringa non sia presente nel
vettore con un find:
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    // inserisco la stringa
    TStringhe::iterator res = find(Stringhe->begin(), Stringhe->end(),
Edit1->Text.c_str());
    if (res==Stringhe->end()) Stringhe->push_back(Edit1->Text.c_str());
    //ordino il vettore
    sort(Stringhe->begin(),Stringhe->end(),ordinamento);
    //pulisco la listbox
    ListBox1->Clear();
    //copio le stringhe nella listbox
    for_each(Stringhe->begin(),Stringhe->end(),copia);
}
dove nella classe TForm1 è stato definito
TStringhe *Stringhe;
e tutte le altre definizioni sono come dal precedente messaggio.
La complessità di find è lineare, mentre sarebbe auspicabile una complessità
logaritmica per un problema di questo tipo. Inoltre programmare
esplicitamente con una if il vincolo di unicità non è molto elegante. Qual è
allora il tipo di dati (contenitore) che meglio si addice a questo caso
(forse è set?) e come usarlo?
Ciao e grazie
Davide

    }
Seconda domanda. Poniamo che la parola vada aggiunta alla lista alla
pressione del tasto di invio, anziché alla pressione del pulsante. Mi viene
in mente che questo si potrebbe fare gestendo l'evento di pressione di un
tasto con una funzione come questa:
void __fastcall TForm1::Edit1KeyPress(TObject *Sender, char &Key)
{
if (Key=='\r')
    {
    // procedura di inserimento della stringa nella lista
    //...
}
Questo funziona, tuttavia il computer emette quella specie di beep sordo che
segnala che, di fatto, il carattere non č stato accettato dall'oggetto
TEdit. E' possibile eliminare l'emissione di questo beep o bisogna
utilizzare un altro controllo?
E' possibile, inoltre, controllare i caratteri immissibili nel controllo
TEdit secondo criteri che varino dinamicamente? Ad esempio, poniamo che
l'utente possa scrivere una stringa i cui caratteri appartengano ad un dato
insieme di lettere e che una volta che una lettera č stata inserita non puň
essere immessa una seconda volta. Le maschere di TMaskEdit mi sembrano
gestibili solo in modo statico, e cioč vanno decise alla creazione del
controllo e non possono essere cambiate man mano che vi si inseriscono
caratteri. Come fare?
Grazie ancora per l'attenzione e chiedo scusa per aver posto domande che
esulano ormai dal soggetto "ordinamento stringhe" e che quindi avrei forse
dovuto mettere fuori da questo thread (non sono ancora molto avvezzo alle
politiche dei newsgroup).
Davide

vettore con un find:
Sí, ma la struttura-dati naturale da usare per un insieme di
oggetti ordinato e senza ripetizioni é un set<T>; inserendo
un elemento in un set, viene automaticamente bloccato se
giá presente, e in qualunque momento puoi scorrere dal
begin all'end e ottenere gli elementi in ordine sortato.
set<T> é facilissimo da usare; al costruttore é vuoto, poi,
usa il metodo insert() per inserire possibili nuovi membri,
e in qualunque momento i metodi begin() ed end(), ed un
iterator, per scandirlo.
Alex

 Internet?
Siii.. magari potessi permettermi di abbonarmi. Gli unici articoli che
ho sono quelli che Inprise pubblica sul suo sito per i poveracci come me
... in pratica uno al mese.
Ciao
Roberto

 }
 
Funziona se fai:
int __fastcall MyCompare(void *Items1, void *Items2)
{
  return (((AnsiString*)Items1)->Length() -
((AnsiString*)Items2)->Length());
}
oppure
typedef AnsiString* pAnsiString;
int __fastcall MyCompare(void *Items1, void *Items2)
{
    return (pAnsiString(Items1)->Length() -
pAnsiString(Items2)->Length());
}
Ciao
Roberto

oggetti ordinato e senza ripetizioni é un set<T>;
ho provato ad usarlo ma non riesco ad eliminare alcuni messaggi di warning.
Ecco le porzioni di codice in questione:
// nel file main.h
// ...
using namespace std;
// tra parentesi, a cosa serve esattamente la linea qui sopra?
inline bool confronta(const string& stringa1, const string& stringa2);
struct ordine{  bool operator()(string& s1, string& s2) const  {
    return confronta(s1, s2);  }};
typedef set<string,ordine> Insieme;
class TForm1 : public TForm
{
// .......
private: // User declarations
    Insieme *insieme;
};
// nel file main.cpp
// ...
// confrontiamo prima la lunghezza e poi l'ordinamento alfabetico
inline bool confronta(const string& s1, const string& s2)
{
    int r;
    if ((r=s1.length()-s2.length())!=0) return r>0;
    else return s1<s2;
}
// da qualche parte si inizializza
// insieme = new Insieme;
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    insieme->insert(Edit1->Text.c_str());
    ListBox1->Clear();
    for_each(insieme->begin(),insieme->end(),copia);
}
la presenza della chiamata ad insert genera 6 messaggi di warning
provenienti dal file tree.cc del tipo:
[C++Warning] tree.cc(211): Temporary used for parameter 's1' in call to
'ordine::operator
()(std::basic_string<char,std::char_traits<char>,std::allocator<char> >
&,std::basic_string<char,std::char_traits<char>,std::allocator<char> > &)
const'.
L'eseguibile funziona perfettamente, ma questi warning sono fastidiosi. Come
eliminarli?
Grazie per l'aiuto.
Davide

Sorry, ignorate pure il messaggio precedente. Avevo dimenticato di mettere
la parola "const" davanti a string&.
Davide

Perfetto, funziona! Grazie!
Ma che casino con queste conversioni, basta saltare una parentesi...
Comunque scherzavo sul fatto di criticare il codice, anzi... ogni critica
costruttiva e' sempre ben accetta: siamo qui per confrontarci e migliorarci
l'un l'altro.
Grazie di nuovo!


eliminarli?
E' assolutamente fondamentale abituarsi a definire const tutto
quello che const deve essere (gli argomenti passati _per valore_
sono un caso diverso; il metodo o funzione che accetta argomenti
per valore ne riceve esplicitamente una "copia", quindi non c'e`
ragione di rendere const quella copia; ma se sono in gioco dei
puntatori o delle reference [compreso il puntatore implicito this]
l'uso corretto e completo di const e' veramente cruciale).
In astratto sarebbe bello che il C++ usasse const *per default*, e
una keyword "var" per chiedere esplicitamente che un dato
argomento sia modificabile; purtroppo, la sfortunata scelta dei
default (in cui la *mancanza di const* e' quel che dice "questo
devo poterlo modificare") fu resa necessaria dai vincoli sul C++
di mantenere compatibilita` con il linguaggio C.
Alex

essere immessa una seconda volta. [...] Come fare?
Sempre in OnKeyPress, assegna il valore 0 ai Key che non vuoi vengano
accettati. Per esempio, il seguente codice evita l'immissione della lettera
'a'.
    if (Key == 'a') Key = 0;
That's all, folks! Ciao, hai visto questo thread come e' diventato lungo?
Complimenti!
--


Ciao a tutti!
Ho il problema di dover ordinare una serie di stringhe (CString)
Esse contengono 5 caratteri che descrivono un orario (es: 10:23)
Devo ordinarle  in modo crescente....
Sapete darmi una mano?
Ha senso usare gli operatori  > e < ??
				Grazie 
						Cap