Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: (STL LIST SORT) Сортировка по некольким критериям  (Прочитано 16122 раз)
0 Пользователей и 1 Гость смотрят эту тему.
tatsu
Гость
« : 18-07-2009 17:57 » 

Здравствуйте!
Столкнулся с такой проблемой при сортировке списка. %-)

Есть структура:

Код:
struct PackObject
{
    bool            Placed;         // Помещен ли на карту текстур
    string          SceneAlias;     // Имя сцены

    string          TexFile;
    int             TexWidth;
    int             TexHeight;
    bool            TexMipMap;
    bool            TexGray;
    bool            TexJpeg;

    string          ObjAlias;          // Имя родительского объекта
    TRect           ObjRect;
    int             AniFrameNumber;    // Порядковый номер кадра
    int             AniFrames;
    int             AniFramesPerLine;
};

А также контейнер list, элемент которого задан соответсвующей структурой.
Код:
typedef list<PackObject>               PackObjectsArray;
typedef list<PackObject>::iterator     PackObjectsIterator;

Требуется отсортировать данный контейнер наполненый некой информацией по
1) Имени сцены "SceneAlias"
2) Аттрибутам текстуры TexMipMap;TexGray;TexJpeg;
3) По размерам текстуры  TexWidth; TexHeight;

ЭТО НЕ ОЗНАЧЕТ СДЕЛАТЬ 3 РАЗНЫХ СОРТИРОВКИ!!! ЭТО ЗНАЧИТ ЧТОБЫ СВЕРХУ ВНИХ ОБЪЕКТЫ БЫЛИ ОТСОРТИРОВАННЫ ПО ДАННЫМ КРИТЕРИЯМ!

Т.е.
1) Scene1  JPEG  MIPMAP GRAY 1000x900
2) Scene1  JPEG  MIPMAP GRAY 800x900
3) Scene1  JPEG  MIPMAP 1000x900
4) Scene1  JPEG  MIPMAP 700x700
5) Scene1  JPEG  GRAY 1500x1500
6) Scene1  JPEG  GRAY 700x700
7) Scene1  JPEG  2000x700
8) Scene1  JPEG  1000x700
8 ) Scene1  100x100
9 ) Scene1  100x50
10) Scene2 .......

Т.е. номера пунктов 3-ех аттрибутов являются как бы приоритетами (важностью) 1) 2) 3)


НО ПРОБЛЕМА НЕ В ТОМ КАК ОТСОРТИРОВАТЬ!!!!!!

Проблема заключается в том что функция PREDICATE для списка LIST отказывается сортировать корректно его элементы!

Вот один из испробованных мною вариантов PREDICATE функции (до этого я пытался делать эту функцию разными способами в том числе перегрузкой скобок ()  и  перегрузкой знака ">" )

Код:
bool PackPred(PackObject &obj1, PackObject &obj2)
{
    bool result = false;

    if (sortmem_apartscenes)
    {
        // Cортируем по имени сцены в алфавитном порядке
        string str1 = obj1.SceneAlias;
        string str2 = obj2.SceneAlias;
        size_t minlen = (str1.length() > str2.length()) ? str2.length() : str1.length();
        for (size_t i = 0; i < minlen; i++)
        {
            if (str1[i] > str2[i])
            {
                result = true;
                break;
            }
        }
        if (str1.length() > str2.length()) result = true;
    }

    // Объекты одной сцены сортируем по параметрам текстуры
    if (sortmem_apartjpeg)
    {
        if ((obj1.TexJpeg) && (!obj2.TexJpeg))  result = true;
    }

    if ((obj1.TexMipMap) && (!obj2.TexMipMap)) result = true;
    if ((obj1.TexGray)   && (!obj2.TexGray))   result = true;

    // Возвращаем результат сравнения размеров
    int width1  = obj1.TexWidth;
    int height1 = obj1.TexHeight;
    int width2  = obj2.TexWidth;
    int height2 = obj2.TexHeight;
    // Хотябы один размер был больше
    if ( ((width1  > width2) && (width1  > height2)) ||
         ((height1 > width2) && (height1 > height2)) ) result = true;*/   
    return result;
};

Пояснения!
1) Переменные bool sortmem_apartscenes и bool sortmem_apartjpeg являются глобальными. Увы от них избавится не вышло а добавлять еще 3 варианта сортировки было бы некрасиво. Перед сортировкой эти переменные устанавливаются в нужное значение.

2) Переменные TexJpeg TexMipMap и TexGray пробовал сравнивать знаком > но все равно безрезультатно.

3) bool result - это якобы варинт написания функции как в Дельфи. Просто во время отладки я заметил очень странную весчь. Оказывается в PREDICATE функции при к примеру "return true" не происходит выход из функции а продолжает обрабатывать всею последующие команды =-O Я не понимать что это за баг?

4) Если проверять по отдельности то разделив на 3-и блока всю функцию сортировки

- мы получим что 1-ый блок с сортировкой по алфавиту, не выполняется (хотя список элементов string успешно сортирует имена файлов но только в другом участке в другом контейнере в моей работе)

- 2 блок кода выполняется только отдельно к примеру только сортировка по JPEG аттрибуту.

- 3 блок сортироки по размерам блестяще выполняется.

ПРИТОМ! Если по всем 3 блокам одновременно я пытаюсь сортировать данный список то у меня получается что
1) По именам сцен сортирует но имена сцен и без того изначально были уже в отсортированном виде еще при добавлении в список элементов (отсортировать в обратном порядке при изменении знака > на  знак < ничего не меняется но если блок убрать то порядок теряется)
2) Также сортирует по именьшению сверху вниз размеров текстур.
Аттрибуты же текстур остаются в произвольном порядке....Жаль


Как это можно вылечить. Может кто уже сталкивался со сложными сортировками?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #1 : 18-07-2009 20:08 » 

Если ты используеш стандартный STL. То нельзя применять алгоритм sort для list. Алгоритм sort требует random access iterator. list не предоставляет такой для доступа к своему содержимому. Используй или vector или deque.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
tatsu
Гость
« Ответ #2 : 18-07-2009 20:21 » 

Если ты используеш стандартный STL. То нельзя применять алгоритм sort для list. Алгоритм sort требует random access iterator. list не предоставляет такой для доступа к своему содержимому. Используй или vector или deque.

Это почему же? Тем более что я использую не std::sort(begin, end, pred) а list.sort(pred)


Вот вызов сортировки и все проходит на ура и работает вот только те так как нужно было бы
        // Cортируем объекты упаковки
        sortmem_apartscenes = apartscenes;
        sortmem_apartjpeg   = apartjpeg;
        PackObjs.sort(PackPred);
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #3 : 18-07-2009 20:39 » new

Ты используеш стандартный STL или чью то интерпретацию онного? В стандартном STL алгоритмы не включены в контейнеры.
« Последнее редактирование: 18-07-2009 20:42 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #4 : 18-07-2009 20:59 » 

Вот кодик я накидал, сортировки по трем параметрам. Применяется стандартный STL.
Код:
#include <iostream>
#include  <vector>
#include <algorithm>
#include <stdlib.h>

using std::vector;
using std::sort;
using std::for_each;
using std::cout;
using std::endl;

struct Some
{
   Some()
   {
      random();
   }
  
   int a;
   int b;
   int c;
   bool operator < (const Some & val) const
   {
      if (a != val.a) return a < val.a;
      if (a != val.b) return a < val.b;
      if (a != val.c) return a < val.c;
      return true;
   }
   void random()
   {
      a=rand();
      b=rand();
      c=rand();
   }
   static void print(const Some &some)
   {
      cout << some.a << ", " << some.b << ", " << some.c << endl;
   }
};

typedef vector<Some> ListSome;

int main()
{
   ListSome listSome;
   for(int i=0; i<25; i++) listSome.push_back(Some());
   cout << "Before sort\n";
   for_each(listSome.begin(), listSome.end(), Some::print);
   sort(listSome.begin(), listSome.end());
   cout << "After sort \n";
   for_each(listSome.begin(), listSome.end(), Some::print);
   return 0;
}
« Последнее редактирование: 18-07-2009 21:03 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
tatsu
Гость
« Ответ #5 : 18-07-2009 21:29 » 

Насчет boost stl и прочих поняти
Все большое спасибо.
Записан
tatsu
Гость
« Ответ #6 : 18-07-2009 21:34 » 

Насчет boost stl и прочих понятий и то как это устроено и где кто неправ я ничего сказать не могу так как я всего лишь новичок.

Все большое спасибо. Ответ найден. Вот цитата с rsdn.ru

Цитата
От:    Jenkas   
Дата:    18.07.09 22:11
Здравствуйте, tatsu, Вы писали:

T>ЭТО НЕ ОЗНАЧЕТ СДЕЛАТЬ 3 РАЗНЫХ СОРТИРОВКИ!!! ЭТО ЗНАЧИТ ЧТОБЫ СВЕРХУ ВНИХ ОБЪЕКТЫ БЫЛИ ОТСОРТИРОВАННЫ ПО ДАННЫМ КРИТЕРИЯМ!

T>Т.е.
T>1) Scene1 JPEG MIPMAP GRAY 1000x900
T>2) Scene1 JPEG MIPMAP GRAY 800x900
T>3) Scene1 JPEG MIPMAP 1000x900
T>4) Scene1 JPEG MIPMAP 700x700
T>5) Scene1 JPEG GRAY 1500x1500
T>6) Scene1 JPEG GRAY 700x700
T>7) Scene1 JPEG 2000x700
T>8) Scene1 JPEG 1000x700
T>8 ) Scene1 100x100
T>9 ) Scene1 100x50
T>10) Scene2 .......

T>Т.е. номера пунктов 3-ех аттрибутов являются как бы приоритетами (важностью) 1) 2) 3)


В вашей функции есть ошибка. Продолжать проверку по след. приоритетному атрибуту стоит только если предидущик атрибуты были равны.

Попробуйте так:
bool PackPred(PackObject &obj1, PackObject &obj2)
{
    if (sortmem_apartscenes)
    {
        string str1 = obj1.SceneAlias;
        string str2 = obj2.SceneAlias;
        if (str1 > str2) {
            return true; //немедленый выход, если больше
        }
        if (str1 < str2) {
            return false; //немедленый выход, если меньше
        }
    }
    //если равно то делаем проверку по след. параметру
    if (sortmem_apartjpeg)
    {
        // Объекты одной сцены сортируем по параметрам текстуры
        if ((obj1.TexJpeg) && (!obj2.TexJpeg))  {
            return true; //немедленый выход, если больше
        }
        if ((!obj1.TexJpeg) && (obj2.TexJpeg))  {
            return false; //немедленый выход, если меньше
        }
    }
    //если равно то делаем проверку по след. параметру
    if ((obj1.TexMipMap) && (!obj2.TexMipMap))  {
        return true; //немедленый выход, если больше
    }
    if ((!obj1.TexMipMap) && (obj2.TexMipMap))  {
        return false; //немедленый выход, если меньше
    }   
    //если равно то делаем проверку по след. параметру
    if ((obj1.TexGray) && (!obj2.TexGray))  {
        return true; //немедленый выход, если больше
    }
    if ((!obj1.TexGray) && (obj2.TexGray))  {
        return false; //немедленый выход, если меньше
    }
    //если равно то делаем проверку по след. параметру
    // Возвращаем результат сравнения размеров
    int width1  = obj1.TexWidth;
    int height1 = obj1.TexHeight;
    int width2  = obj2.TexWidth;
    int height2 = obj2.TexHeight;
    // Хотябы один размер был больше
    if ( ((width1  > width2) && (width1  > height2)) ||
         ((height1 > width2) && (height1 > height2)) )
         return true; //немедленый выход, если больше
    //и т.д.
    return false;
};
Записан
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 19-07-2009 21:07 » 

Я, конечно, к шапочному разбору, но не могу пройти мимо вот этого:
Код:
        if (str1 > str2) {
            return true; //немедленый выход, если больше
        }
        if (str1 < str2) {
            return false; //немедленый выход, если меньше
        }
(уже не хочу комментировать то, что изначально было в авторском варианте в качестве сравнения строк)

Вообще-то, у string есть метод
Код:
int compare ( const string& str ) const;
который возвращает
0 if the compared characters sequences are equal, otherwise a number different from 0 is returned, with its sign indicating whether the object is considered greater than the comparing string passed as parameter (positive sign), or smaller (negative sign).
Второе сравнение совершенно избыточно (и я не уверен, что компилятор придёт к тому же выводу)
Записан
Phodopus
Интересующийся

ru
Offline Offline

« Ответ #8 : 20-07-2009 13:30 » 

Не, избыточным было бы <=, а там просто <, так что вариант с = остается за этими двумя сравнениями
Записан
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #9 : 22-07-2009 04:48 » 

полагаю вот такой код понравился бы Ваду Улыбаюсь
Код:
int res = str1.compare(str2); // тут один раз сравниваем 2 куска памяти.
if (res != 0)
    return res < 0;

Записан

Странно всё это....
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #10 : 22-07-2009 07:01 » 

Phodopus,  насчёт избыточности - да, совсем упустил из виду устройство STL Улыбаюсь Если сравнение разбивается на одинаковые посимвольные операции сравнения в духе
Код:
if (c1 < c2)
    return -1;
if (c2 < c1)
    return 1;
return 0;
тогда выигрыш будет только в том, что происходит 1 проход по массивам, а не 2 (да и то, кэш это минимизирует).

Просто я бы делал это сравнение с использованием ==, но такой подход требует реализации соответствующего оператора и отходит от практики выстраивания отношения порядка через "<", хотя и будет на конкретных char и wchar_t более производительным. Он недостаточно общий Улыбаюсь Хотя я не поручусь, что какая-нибудь реализация не оптимизирует.

LogRus, да, я имел в виду примерно такой код. Он чуть-чуть "навёрнут" в части вычисления возвращаемого результата, но зато содержит одно-единственное сравнение, которое этот результат и определяет.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines