VPF::Сортировка элементов в TList - Форум программистов

Нитонисе

Дата 10.11.2009, 23:38 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

Нужно отсортировать элементы в TList. Знаю что есть функция Sort, но не пойму как она работает. В списке предполагаются целые числа.

Может быть посоветуете и другой путь решения задачи? Мне нужен некий контейнер, который бы хранил целые числа, очень хорошо если бы этот контейнер умел убивать дупликаты, в крайнем случае умел сортировать... желательно контейнер из классов билдера, вот я остановился пока на TList, пусть он не убивает дупликаты, но хотя бы сортирует.

SenkraD

Дата 11.11.2009, 09:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 933
Регистрация: 3.2.2006
Где: Украина::Киев

Репутация: 9
Всего: 23

Нитонисе, чем STL не подходит:

Код

#include <list>
#include <algorithm>

std::list<int> intergers;

integers.push_back(1);
integers.push_back(10);
integers.push_back(5);
integers.push_back(3);
integers.push_back(5);
integers.push_back(9);
integers.push_back(1);

integers.sort(std::less<int>());
integers.unique(std::equal<int>());

Ошибки не исключены писал с коленки - прийду на работу пофикшу

--------------------

Имеющий язык - да не убоится спросить!

Нитонисе

Дата 11.11.2009, 11:34 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

Наверное подходит, просто я с контейнерами STL раньше не работал, мне просто удобнее работать с классами билдера.

mrbrooks

Дата 11.11.2009, 12:28 (ссылка)

(нет голосов)

Загрузка ...

трололомен

Профиль
Группа: Завсегдатай
Сообщений: 4259
Регистрация: 4.10.2006
Где: Дол Гулдур

Репутация: 167
Всего: 306

Цитата(Нитонисе @ 10.11.2009, 23:38

)

Нужно отсортировать элементы в TList. Знаю что есть функция Sort, но не пойму как она работает.

работает достаточно просто. Необходимо указатель на функцию сравнения. Вот здесь начинается самое интересное - заканчивается гламурный быдлокодинг (как бэ) и начинаем уже чуточку мыслить. Подход на самом деле стандартный.

Код


#include <memory>
//---------------------------------------------------------------------------
int __fastcall MyCompare(void *a, void *b)
{
    int *ia = static_cast<int *>(a);
    int *ib = static_cast<int *>(b);
    return  (*ia > *ib)? 1: ((*ia < *ib)?-1:0);
}
//---------------------------------------------------------------------------
void __fastcall TForm::ButtonClick(TObject *Sender)
{
std::auto_ptr<TList>list(new TList);
int arr[5] = {10,5,0,22,3}; 
for (int j = 0; j < 5; j++) list->Add(&arr[j]);
list->Sort(MyCompare);

//для проверки выведем в Мемо
for (int i = 0; i < list->Count; i++)
{
    int *j = static_cast<int *>(list->Items[i]);
    Memo->Lines->Add(*j);
}
}
//---------------------------------------------------------------------------

Цитата(Нитонисе @ 10.11.2009, 23:38

)

Мне нужен некий контейнер, который бы хранил целые числа, очень хорошо если бы этот контейнер умел убивать дупликаты, в крайнем случае умел сортировать... желательно контейнер из классов билдера, вот я остановился пока на TList, пусть он не убивает дупликаты, но хотя бы сортирует.

как заметил камрад SenkraD контейнеры из STL достаточно кошерный выход.

Нитонисе

Дата 11.11.2009, 13:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

mrbrooks, вы тоже используете инструментарий С++. Я вобщем-то не могу себя причислить к спецам, потому использую приемы программирования на своем низком уровне. Признаю что ваши решения эффективнее, но мне с этим просто нужно разбираться)) Не могли бы вы более понятно расписать (прокомментировать) вот этот пример, заменив сортировку по алфавиту, на сортировку чисел.

Код


int __fastcall CompareNames(void *Item1, void *Item2)

{
  return CompareText(((TComponent *)Item1)->Name, ((TComponent *)Item2)->Name);

}

void __fastcall TForm1::Button1Click(TObject *Sender)

{
  List1->Sort(CompareText);
}

Это сообщение отредактировал(а) Нитонисе - 11.11.2009, 13:09

mrbrooks

Дата 11.11.2009, 13:15 (ссылка)

(нет голосов)

Загрузка ...

трололомен

Профиль
Группа: Завсегдатай
Сообщений: 4259
Регистрация: 4.10.2006
Где: Дол Гулдур

Репутация: 167
Всего: 306

Цитата(Нитонисе @ 11.11.2009, 13:09

)

Не могли бы вы более понятно расписать (прокомментировать) вот этот пример, заменив сортировку по алфавиту, на сортировку чисел.

камрад. То что ты привел и я - это одно и тоже. Что моя функция MyCompare, что твоя CompareNames возвращает int, в случае когда
Item1 > Item2 = 1
Item1 == Item2 = 0
Item1 < Item2 = -1

В своем коде для чисел я описывал все это сам, в приведенном тобой для строк - это все успешно заменяет функция CompareText. Вот и все.

Нитонисе

Дата 11.11.2009, 13:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

mrbrooks, значит если нет стандартной функции сравнения чисел, то нужно ее написать. Я так понял что ты ее и написал, просто мне не совсем понятен код. Но эта функция должна возвращать одно из трех значений: -1,0,1. Так?

SenkraD

Дата 11.11.2009, 13:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 933
Регистрация: 3.2.2006
Где: Украина::Киев

Репутация: 9
Всего: 23

да. Вы вообще читали документацию к TList::Sort?

--------------------

Имеющий язык - да не убоится спросить!

Нитонисе

Дата 11.11.2009, 13:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

Цитата(SenkraD @ 11.11.2009, 13:25

)

да. Вы вообще читали документацию к TList::Sort?

Что из хелпа смог перевести, то и прочитал. Меня просто смутила функция CompareText. Ее в примере использовали, но она нигде не объявлена. Стало быть какая-то стандартная функция и теперь все более менее понятно. Надо сделать функцию сравнения чисел.

SenkraD

Дата 11.11.2009, 13:45 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 933
Регистрация: 3.2.2006
Где: Украина::Киев

Репутация: 9
Всего: 23

у мя щас под рукой Builder нет, но помойму тут предельно ясно написано,
что нуно сделать и как

Код

Sorting a TList
by Kent Reisdorph

The TList class is great for storing objects of any type. You can store structures, classes, integers, doubles, and well, just about any type of data. Frequently, you may need a sorted list; TList has a Sort method that allows you to sort the list. Unfortunately, the Sort method is a bit confusing at first and often misunderstood. In this article, we'll show you how to use the Sort method to sort your lists, no matter what they contain.

  
The Sort method
You use the Sort method of TList to sort the list. That's not too surprising, is it? The declaration for Sort looks like this:
void __fastcall Sort(TListSort
    Compare Compare);
The single parameter for the Sort method is a pointer to a comparison function, which will be called for every item in the list. We'll talk more about the comparison function in a minute.

Once you've created a comparison function, you can call Sort with the following lines:

 
TList* list = new TList;
// Add some items to the list.
list->Sort(Comparison
    Function);
Believe it or not, that's all there is to calling the Sort method. Obviously, there must be more to calling Sort than these few lines of code. There is, of course, so let's examine the comparison function. Then we'll return to the Sort method.

  
The comparison function
The comparison function does all of the work of sorting the list. It accepts two items from the list and returns a value. The comparison function must be of type TListSortCompare, which is declared as follows:
typedef int __fastcall 
    (*TListSortCompare)
  (void * Item1, void * Item2);
That declaration might not mean much to you, so let me clarify a bit. The comparison function follows a specific function signature. Here's a sample declaration for a comparison function:
int __fastcall Sorter(void* Item1, 
    void* Item2);
As you can see, the function has two parameters. The two parameters are pointers to two of the objects in the list. (It doesn't matter to you which two items in the list are being passed in, just how you compare the two.) 

Notice that both parameters are void pointers. Since a TList just stores a list of pointers, that's exactly what you get in the comparison function. Put another way, TList doesn't know what it contains, so it just gives you two pointers and leaves it up to you to decide what to do with them. You'll cast the void pointers to something useful, compare the two items, then return a value based on the comparison.

The comparison function must be either a regular function or, if the function is a member of a class, it must be declared as static. The easiest approach is to just make it a regular function. 
Sorting simple data
The value returned from the comparison function determines how the list is sorted. Table A shows what you should return from the comparison function. 

Table A: Return value from the comparison function.Condition    Return Value
Item1 = Item2    0
Item1 > Item2    Any positive number
Item1 < Item2    Any negative number


We'll look at a simple example to illustrate the point. Let's say you had a list of integers that you wanted to sort. In that case, the comparison function would look like this:

 
int __fastcall SortInt
    void* Item1, void* Item2)
{
  int X1 = (int)Item1;
  int X2 = (int)Item2;
  return X1 - X2;
}
Because the list contains integers, we must cast the void pointers to an int to get the actual value of the item. (As I've said in past articles, I'm a big fan of the C++ casting operators over the old C-style casts. However, in this case, you don't gain anything by using the C++ casting operator, static_cast, so the C-style cast is perfectly acceptable.) 

Now look at the return statement in this function. If X1 is greater than X2, then a positive value will be returned. If X1 is less than X2, then the return statement produces a negative value. When X1 and X2 are equal, the return value is 0: A single statement takes care of it all. 

This one statement sorts the list of integers in ascending order. But what if you want to sort the integers in descending order? Not a problem; just reverse the variables in the return statement:

 
return X2 - X1;
The list is now sorted in descending order. To sort the list in either ascending or descending order, you'll have to use two separate comparison functions (or implement a global variable that holds the sort direction). 

  
Sorting complex objects
You can sort complex objects as well as simple objects. For example, you may have a list of classes that you want to sort. In that case, the sort is only slightly more complex than it would be if you were sorting integral data types. So what do you use as a sort criteria when sorting classes? That's up to you. Since you know what your class contains, you can sort it in any way you like. 

Let me give you an example of a class that contains an integer data member. First, we'll look at this class:

 
class MyNumberClass {
  public:
    MyNumberClass(int data) 
    { Data = data; }
    int Data;
  // More of the class here.
};
Now, let's say you had a list of MyNumberClass objects. To sort the list in ascending order, you'd write a comparison function like this:

 
int __fastcall IntSort
    (void* Item1, void* Item2)
{
  MyNumberClass* MC1 = 
    (MyNumberClass*)Item1;
  MyNumberClass* MC2 = 
    (MyNumberClass*)Item2;
  return MC1->Data - MC2->Data;
}
Notice that this function differs only slightly from the integer sorting function you saw earlier. First, the void pointers are cast to MyNumberClass pointers, then the Data member of the two objects is used to perform the comparison. Similarly, if you had a class that contained an AnsiString data member, you could sort the list like this:
int __fastcall StrSort
    (void* Item1, void* Item2)
{
  MyStringClass* MS1 = 
    (MyStringClass*)Item1;
  MyStringClass* MS2 = 
    (MyStringClass*)Item2;
  return MS1->Text.AnsiCompare
    (MS2->Text);
}
Although these are pretty simple cases, my point is that you can sort any type of object --in any way you wish. Deciding how the objects should be sorted is completely up to you. All you have to do is return 0, a positive number, or a negative number from the comparison routine.

Listing A contains the main form unit of a program that demonstrates sorting TList container classes. The program sorts two types of classes: one by an integer value and the other according to a string data member. (We are showing only the CPP file. The header is all C++Builder-generated, so there's no point in showing it here.) 

The program's main form contains two buttons. The first button sorts the list of integer-based classes, and the second button sorts a list of string-based classes. Both ascending and descending sorting routines are provided. The results of the sort are displayed in a memo, so you can see the result. 

To create this program, place a Memo component and two buttons on a form. Then enter the code below. Alternatively, you can download the code from our Web site at www.cobb.com/cpb ; click on the Source Code hyperlink. 

Listing A: LISTSORT.CPP
//-------------------------
\    --------------------
#include <vcl.h>
#pragma hdrstop

#include "SortU.h"
//-------------------------
    --------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//-------------------------
    --------------------
__fastcall TForm1::TForm1
    (TComponent* Owner)
  : TForm(Owner)
{
}
//-------------------------
    --------------------

// A class that contains 
    an int data member.
class MyNumberClass {
  public:
    MyNumberClass(int data) 
    { Data = data; }
    int Data;
};

// A class that contains a 
    String data member.
class MyStringClass {
  public:
    MyStringClass(String text) 
    { Text = text; }
    String Text;
};

// The ascending sort function 
    for MyNumberClass.
int __fastcall
SortAscending(void* Item1, void* Item2)
{
  MyNumberClass* MC1 = 
    (MyNumberClass*)Item1;
  MyNumberClass* MC2 = 
    (MyNumberClass*)Item2;
  return MC1->Data - MC2->Data;
}

// The descending sort function 
    for MyNumberClass.
int __fastcall
SortDescending(void* Item1, void* Item2)
{
  MyNumberClass* MC1 = 
    (MyNumberClass*)Item1;
  MyNumberClass* MC2 = 
    (MyNumberClass*)Item2;
  return MC2->Data - MC1->Data;
}

// The ascending string sort function
// for MyStringClass.
int __fastcall
StringSortAscending
    (void* Item1, void* Item2)
{
  MyStringClass* MS1 = 
    (MyStringClass*)Item1;
  MyStringClass* MS2 = 
    (MyStringClass*)Item2;
  return MS1->Text.AnsiCompare
    (MS2->Text);
}

// The descending string sort function
// for MyStringClass.
int __fastcall
StringSortDescending
    (void* Item1, void* Item2)
{
  MyStringClass* MS1 = 
    (MyStringClass*)Item1;
  MyStringClass* MS2 = 
    (MyStringClass*)Item2;
  return MS2->Text.AnsiCompare
    (MS1->Text);
}

void __fastcall
TForm1::Button1Click(TObject *Sender)
{
  // Create a TList and fill it
     with instances
  // of the MyNumberClass class.
  TList* list = new TList;
  list->Add(new MyNumberClass(100));
  list->Add(new MyNumberClass(1));
  list->Add(new MyNumberClass(23));
  list->Add(new MyNumberClass(54));
  list->Add(new MyNumberClass(77));
  list->Add(new MyNumberClass(89));
  list->Add(new MyNumberClass(12));
  list->Add(new MyNumberClass(17));
  list->Add(new MyNumberClass(22));
  list->Add(new MyNumberClass(94));
  list->Add(new MyNumberClass(87));
  list->Add(new MyNumberClass(55));
  list->Add(new MyNumberClass(33));
  list->Add(new MyNumberClass(62));

  // Sort the list in ascending order and
  // display the results in the memo.
  list->Sort(SortAscending);
  Memo1->Text = "Ascending Sort";
  for (int i=0;i<list->Count;i++) {
    MyNumberClass* mc =
      (MyNumberClass*)list->Items[i];
    Memo1->Lines->Add("Item " +
      String(i) + ": " + String
    (mc->Data));
  }
  Memo1->Lines->Add("");
  Memo1->Lines->Add("");

  // Sort the list in descending order and
  // display the results in the memo.
  list->Sort(SortDescending);
  Memo1->Lines->Add
    ("Descending Sort");
  for (int i=0;i<list->Count;i++) {
    MyNumberClass* mc =
      (MyNumberClass*)list->Items[i];
    Memo1->Lines->Add("Item " +
      String(i) + ": " + String
    (mc->Data));
  }
  for (int i=0;i<list->Count;i++) {
    MyNumberClass* mc =
      (MyNumberClass*)list->Items[i];
    delete mc;
  }
  delete list;
}
//-------------------------
    --------------------
void __fastcall TForm1::Button2Click
    (TObject *Sender)
{
  // Create a TList and fill it with instances
  // of the MyNumberClass class.
  TList* list = new TList;
  list->Add(new MyStringClass
    ("Hello there!"));
  list->Add(new MyStringClass
    ("What's going on?"));
  list->Add(new MyStringClass
    ("This is a test."));
  list->Add(new MyStringClass
    ("Nothing new here!"));
  list->Add(new MyStringClass
    ("TurboPower Software"));
  list->Add(new MyStringClass
    ("Borland International"));
  list->Add(new MyStringClass(
    "A short string."));
  list->Add(new MyStringClass
    ("Hello again!"));
  list->Add(new MyStringClass(22));
  list->Add(new MyStringClass(94));
  list->Sort(StringSortAscending);

  // Sort the list in ascending order and
  // display the results in the memo.
  Memo1->Text = "Ascending Sort";
  for (int i=0;i<list->Count;i++) {
    MyStringClass* mc =
      (MyStringClass*)list->Items[i];
    Memo1->Lines->Add(mc->Text);
  }
  Memo1->Lines->Add("");
  Memo1->Lines->Add("");

  // Sort the list in descending order and
  // display the results in the memo.
  list->Sort(StringSortDescending);
  Memo1->Lines->Add
    ("Descending Sort");
  for (int i=0;i<list->Count;i++) {
    MyStringClass* mc =
      (MyStringClass*)list->Items[i];
    Memo1->Lines->Add(mc->Text);
  }

  // Delete all the objects and then
  // delete the list itself.
  for (int i=0;i<list->Count;i++) {
    MyStringClass* mc =
      (MyStringClass*)list->Items[i];
    delete mc;
  }
  delete list;
}

сомнееваюсь, что офдоки сильно отличаются

--------------------

Имеющий язык - да не убоится спросить!

Нитонисе

Дата 11.11.2009, 14:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

SenkraD, хм, такое я не видел, может плохо искал.
А в функцию сравнения передаются указатели void, может можно туда передовать указатели типа int, если я int сравниваю?

SenkraD

Дата 11.11.2009, 14:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 933
Регистрация: 3.2.2006
Где: Украина::Киев

Репутация: 9
Всего: 23

нет - иначе сигнатура не подойдёт (вернее без каста не подойдёт).

Это сообщение отредактировал(а) SenkraD - 11.11.2009, 14:15

--------------------

Имеющий язык - да не убоится спросить!

mrbrooks

Дата 11.11.2009, 14:13 (ссылка)

(нет голосов)

Загрузка ...

трололомен

Профиль
Группа: Завсегдатай
Сообщений: 4259
Регистрация: 4.10.2006
Где: Дол Гулдур

Репутация: 167
Всего: 306

Цитата(Нитонисе @ 11.11.2009, 14:02

)

такое я не видел, может плохо искал.

очень даже возможно.

Цитата(Нитонисе @ 11.11.2009, 14:02

)

А в функцию сравнения передаются указатели void, может можно туда передовать указатели типа int, если я int сравниваю?

в какую? в том примере, где строки сравниваются smile

попробуй - но это будет лол.

Добавлено через 2 минуты и 34 секунды

Цитата(SenkraD @ 11.11.2009, 14:13

)

P.S. Хотя я бы её сделал шаблоной с использованием предикатов

хорошая мысль.

Нитонисе

Дата 11.11.2009, 14:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

Вот такая функция сравнения

Код


int __fastcall SortInt(void *Item1, void *Item2)
{
int X1 = (int)Item1;
int X2 = (int)Item2;
return X2 - X1;
}

И вот так инициализируется сортировка

Код


List->Sort(SortInt);

Нитонисе

Дата 11.11.2009, 17:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

Почему-то сортировка работает некорректно.

Код


struct TLoading
{
int x1,x2;
float value;
};

TList *List = new TList;

// заношу в структуру Loading три позиции
Loading->x1 = 0;
Loading->x2 = 2;
Loading->value = 1;
List->Add(Loading);
Loading = new TLoading;
Loading->x1 = 0;
Loading->x2 = 6;
Loading->value = 1.5;
List->Add(Loading);
Loading = new TLoading;
Loading->x1 = 4;
Loading->x2 = 5;
Loading->value = 2;

// элементы структур x1 b x2  - заношу в список X
TList *X = new TList;
for (int i=0; i < List->Count; i++)
  {
    Loading = (TLoading *)List->Items[i];
    int *add = &Loading->x1;
    X->Add(add);
    add = &Loading->x2;
    X->Add(add);
  }

X->Sort(SortInt);
 
// вывод в Memo
for (int i=0; i < X->Count; i++)
  {
    int x = *((int*)X->Items[i]);
    Memo1->Lines->Add(IntToStr(x));
  }

Результат в Memo "2,0,6,0,5,4".
Почему сортировка прошла некорректно?

SenkraD

Дата 11.11.2009, 17:23 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 933
Регистрация: 3.2.2006
Где: Украина::Киев

Репутация: 9
Всего: 23

потому что компаратор не правильный!!! - мой косяк - в той статье ошибка
нуно так

Код

int __fastcall SortInt(void *Item1, void *Item2)
{
    int X1 = static_cast<int*>(Item1);
    int X1 = static_cast<int*>(Item2);
    return X2 - X1;
}

--------------------

Имеющий язык - да не убоится спросить!

Нитонисе

Дата 11.11.2009, 17:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 917
Регистрация: 5.11.2009

Репутация: 2
Всего: 2

Не совсем так. Переделал.

Код


int __fastcall SortInt(void *Item1, void *Item2)
{
int X1 = *(static_cast<int*>(Item1));
int X2 = *(static_cast<int*>(Item2));
return X1 - X2;
}

Хотя смысл static_cast<int*> не совсем понимаю))

SenkraD

Дата 11.11.2009, 17:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 933
Регистрация: 3.2.2006
Где: Украина::Киев

Репутация: 9
Всего: 23

Нитонисе, смысл в том что ты явно указываеш каст + этот каст,
в отличии от С-стайл каста, может уведомить об ошибке на этапе компиляции +
повышается читабельность кода

--------------------

Имеющий язык - да не убоится спросить!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C++ Builder \| Следующая тема »