Re[8]: Однообразность в STL
От: sergey_shandar США http://getboost.codeplex.com/
Дата: 25.08.04 14:44
Оценка:
Здравствуйте, _nn_, Вы писали:

_>>Согласен, но у меня просто аллергия на дефайны .

__>Почему ?

Не знаю, появилась после поиска интересных ошибок... Не хотелось бы это говорить (думаю все эти дыры в макросах ты уже сам знаеш), ОБЯЗАТЕЛЬНО найдеться такой человек, который напишет что то вроде:
#define begin_end(c) c.begin(), c.end()

bool y;
std::vector<int> x, y;
std::sort(begin_end(flag ? x: y));


__>Мне кажется что в данном случае гараздо проще использовать макрос чем определять десяток функций, к которым может еще что-нибудь добавиться, вдобавок этот макрос можно пихать везде, а не к только определенным функциям.


Кому как, для меня важнее надежность и понятность кода .
getboost.codeplex.com
citylizard.codeplex.com
Re[9]: Однообразность в STL
От: _nn_  
Дата: 25.08.04 14:47
Оценка: :)
Здравствуйте, sergey_shandar, Вы писали:

_>Здравствуйте, _nn_, Вы писали:


_>>>Согласен, но у меня просто аллергия на дефайны .

__>>Почему ?

_>Не знаю, появилась после поиска интересных ошибок... Не хотелось бы это говорить (думаю все эти дыры в макросах ты уже сам знаеш), ОБЯЗАТЕЛЬНО найдеться такой человек, который напишет что то вроде:

_>
_>#define begin_end(c) c.begin(), c.end()

_>bool y;
_>std::vector<int> x, y;
_>std::sort(begin_end(flag ? x: y));
_>


__>>Мне кажется что в данном случае гараздо проще использовать макрос чем определять десяток функций, к которым может еще что-нибудь добавиться, вдобавок этот макрос можно пихать везде, а не к только определенным функциям.


_>Кому как, для меня важнее надежность и понятность кода .


Если использовать оккуратно проблем не будет.
Сколько людей используют BEGIN_MSG_MAP(BEGIN_MESSAGE_MAP) и не сталкиваются с трудностями

А насчет begin_end(flag?x:y) то это просто макрос исправить
#define begin_end(c) (c).begin(), (c).end()
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re: Однообразность в STL
От: Павел Кузнецов  
Дата: 25.08.04 20:56
Оценка: 2 (1)
_nn_:

> Напрашивается вопрос почему не сделать функцию sort в векторе.

> Или же почему не сделать функцию sort еще и так:
>
> template<typename TContainer>
> void sort(TContainer& c);
>

> А потом перегружать для нужных контейнеров.
> И тогда не будет проблемы выше.

Но появится другая: изменения семантики и вычислительной сложности будут происходить молча. Скажем, по этой же причине в std::list нет operator[].
Posted via RSDN NNTP Server 1.9 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[5]: Однообразность в STL
От: Кодт Россия  
Дата: 26.08.04 07:17
Оценка:
Здравствуйте, _nn_, Вы писали:

К>>Потому что сортировка списка меняет порядок обхода, не меняя сами элементы. А сортировка массива — обменивает значения.


К>>Криворукий эскиз быстрой сортировки над forward-итерируемым массивом. Заметьте, даже не над bidirectional.


__>Это не аргумент против добавления такой удобной вещи


Что не аргумент? Криворукость? Или то, что сортировка списка не меняет содержимое элементов, а быстрая сортировка меняет?

Ну так чтож. Бери мой код, отладь и пользуйся.
Перекуём баги на фичи!
Re[6]: Однообразность в STL
От: _nn_  
Дата: 27.08.04 07:08
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, _nn_, Вы писали:


К>>>Потому что сортировка списка меняет порядок обхода, не меняя сами элементы. А сортировка массива — обменивает значения.


К>>>Криворукий эскиз быстрой сортировки над forward-итерируемым массивом. Заметьте, даже не над bidirectional.


__>>Это не аргумент против добавления такой удобной вещи


К>Что не аргумент? Криворукость? Или то, что сортировка списка не меняет содержимое элементов, а быстрая сортировка меняет?

Я имел ввиду что можно сделать это.

К>Ну так чтож. Бери мой код, отладь и пользуйся.

Попробую
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re[4]: Однообразность в STL
От: sergey_shandar США http://getboost.codeplex.com/
Дата: 28.08.04 14:00
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Криворукий эскиз быстрой сортировки над forward-итерируемым массивом. Заметьте, даже не над bidirectional.

К>
...
К>      swap(*splitter,*it);
...


Тогда лучше здесь вместо std::swap использовать std::iter_swap(splitter, it), так как std::iter_swap может быть специализирован для std::list<T>::iterator.
getboost.codeplex.com
citylizard.codeplex.com
Re[2]: Однообразность в STL
От: Olivia Россия  
Дата: 06.12.04 19:37
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, _nn_, Вы писали:


К><>


К>std::sort это — изначально — разновидность быстрой сортировки контейнеров с произвольным доступом (массивы, std::vector).

К>std::list::sort использует алгоритм сортировки двухсвязных списков.
К>std::set/map/multiset/multimap вообще сортировать нельзя.

К>Для контейнеров с медленным произвольным доступом (по forward iterator'у) можно написать разновидность быстрой сортировки. Но вроде бы ни в одной версии STL этого не сделали.


К>В принципе, можно сделать функцию-диспетчера, которая различала бы тип контейнера и выполняла ту или иную сортировку.

К>
К>template<class V, class A, class P>
К>void sort_container(std::vector<V,A>& cont, P pred)
К>{
К>  std::sort(cont.begin(), cont.end(), pred);
К>}

К>template<class V, class A, class P>
К>void sort_container(std::list<V,A>& cont, P pred)
К>{
К>  cont.sort(pred);
К>}

К>template<class C>
К>void sort_container(C& cont)
К>{
К>  sort_container(cont, std::less<typename C::value_type>());
К>}
К>


У меня вопрос в таком случае. Расскажите, пожалуйста, почему std::multimap нельзя сортировать, ведь алгоритм сортировки применим ко всем контейнерам.
И подскажите, плизз, как обойти эту проблему: у меня задание вывести данные из multimap, упорядоченные по определенному критерию (не ключ).
Заранее благодарна.
Re[3]: Однообразность в STL
От: Кодт Россия  
Дата: 07.12.04 09:48
Оценка:
Здравствуйте, Olivia, Вы писали:

O>У меня вопрос в таком случае. Расскажите, пожалуйста, почему std::multimap нельзя сортировать, ведь алгоритм сортировки применим ко всем контейнерам.


Не ко всем. STL выделяет последовательности (vector, deque, list) и ассоциативные контейнеры (set, map, multiset, multimap).

Элементы ассоциативных контейнеров уже упорядочены по ключу. Поэтому дополнительная сортировка к ним неприменима.

O>И подскажите, плизз, как обойти эту проблему: у меня задание вывести данные из multimap, упорядоченные по определенному критерию (не ключ).


Есть несколько вариантов:
1) изначально хранить в структуре, поддерживающей несколько порядков в контейнере — bimap, boost::multi_index...
2) сделать "слепок" контейнера и отсортировать. Вместо копирования значений можно брать указатели/итераторы исходного контейнера.
Перекуём баги на фичи!
Re[4]: Однообразность в STL
От: Olivia Россия  
Дата: 07.12.04 12:52
Оценка:
Здравствуйте, Кодт, Вы писали:

Большое спасибо за ответ.

К>Есть несколько вариантов:

К>1) изначально хранить в структуре, поддерживающей несколько порядков в контейнере — bimap, boost::multi_index...
К>2) сделать "слепок" контейнера и отсортировать. Вместо копирования значений можно брать указатели/итераторы исходного контейнера.

В первом случае, могли бы наглядно показать как это делается
вот мой класс
class Temp
{
public:
char s[50];
int age;

Temp();
Temp(const Temp &T);
Temp(char t_s[50],int t_age);
~Temp();
};
Как тогда будет выглядеть сама функция сортировки, она же там требует три параметра.
Во втором случае. Я не знакома с понятием слепок контейнера, где бы мне можно было почитать об этом. И я так понимаю во втором случае сортировка будет производиться по итераторам?
Я просто не могу понять сам механизм, ведь данные в ассоциативных контейнерах хранятся в упорядоченном виде по ключу, каким образом они будут упорядычиваться, если применить один из предложенных вариантов.
И какой из вариантов наиболее эффективен?
Re[5]: Однообразность в STL
От: Кодт Россия  
Дата: 07.12.04 13:47
Оценка:
Здравствуйте, Olivia, Вы писали:

O>Здравствуйте, Кодт, Вы писали:


O>Большое спасибо за ответ.


К>>Есть несколько вариантов:

К>>1) изначально хранить в структуре, поддерживающей несколько порядков в контейнере — bimap, boost::multi_index...
К>>2) сделать "слепок" контейнера и отсортировать. Вместо копирования значений можно брать указатели/итераторы исходного контейнера.

O>В первом случае, могли бы наглядно показать как это делается

O>вот мой класс
O>class Temp
O>{
O>    public:
O>    char s[50];
O>    int age;
        
O>    Temp();                                             
O>    Temp(const Temp &T);                                
O>    Temp(char t_s[50],int t_age);
O>    ~Temp();
O>};

O>Как тогда будет выглядеть сама функция сортировки, она же там требует три параметра.

Вот здесь http://www.boost.org/libs/multi_index/doc/tutorial.html
рассказывается о том, как создавать многоиндексные контейнеры.
Кстати, пример там практически один в один с твоим

O>Во втором случае. Я не знакома с понятием слепок контейнера, где бы мне можно было почитать об этом. И я так понимаю во втором случае сортировка будет производиться по итераторам?

O>Я просто не могу понять сам механизм, ведь данные в ассоциативных контейнерах хранятся в упорядоченном виде по ключу, каким образом они будут упорядычиваться, если применить один из предложенных вариантов.

Слепок в данном случае — это коллекция (вектор/список/множество) элементов, содержащихсч в исходном контейнере.
Если копировать элементы дорого, то можно и нужно формировать коллекцию посредников — указателей, итераторов и т.п.
Имхо, наиболее эффективным по скорости будет вектор указателей — единожды выделяется блок памяти, за линейное время туда копируются указатели на элементы, и наконец, выполняем сортировку.
bool less_name_fn(const Temp& l, const Temp& r); // по полю s
bool less_age_fn (const Temp& l, const Temp& r); // по полю age

struct less_name { bool operator()(const Temp& l, const Temp& r) const { return less_name_fn(l,r); } };

typedef std::set<Temp, less_name> temps_by_name;


struct less_ptr_age { bool operator()(const Temp* l, const Temp* r) const { return less_age_fn(*l,*r); } };

void print_by_age(const temps_by_name& temps)
{
  tyepdef std::vector<Temp*> temp_ptrs_by_age;
  temp_ptrs_by_age v; v.reserve(temps.size());

  for(temps_by_name::const_iterator i = temps.begin(); i!=temps.end(); ++i)
    v.push_back(&*i);

  std::stable_sort(v.begin(), v.end(), less_ptr_age()); // ещё и порядок имён сохраним

  for(temp_ptrs_by_age::const_iterator j = v.begin(); j!=v.end(); ++j)
    cout << (*j).s << " : " << (*j).age << endl;
}


O>И какой из вариантов наиболее эффективен?


Зависит от того, как часто тебе нужно перечислять элементы по вторичному индексу.
Перекуём баги на фичи!
Re[6]: Однообразность в STL
От: Аноним  
Дата: 08.12.04 10:07
Оценка:
Здравствуйте, Кодт, Вы писали:

Спасибо за ответ, но из ваших примеров я не могу применить ничего к своему, потому что у меня объявлен multimap и в нем уже хранятся данные:

multimap <int, Temp, less<int> > m;
multimap<int, Temp, less<int> >::iterator it;

m.insert(pair <const int, Temp> (6,Temp("Koloskov",45)));
m.insert(pair <const int, Temp> (1,Temp("Dmitriev",42)));
m.insert(pair <const int, Temp> (3,Temp("Grekova",32)));
m.insert(pair <const int, Temp> (9,Temp("Isaeva",27)));
m.insert(pair <const int, Temp> (5,Temp("Kondratiev",64)));

print_by_name();
for(it = m.begin(); it != m.end(); it++)
cout << (*it).first << " " << (*it).second.s << " " << (*it).second.age <<endl;

Можно ли как-нибудь хранить, например, мой мультимэп в другом контейнере, т.е. как бы вложенная одна в другую структура получается, например — vector<m> v. Возможен ли такой вариант, это будет очень просто я думаю, только надо придумать как это реализовать...
Re[7]: Однообразность в STL
От: Кодт Россия  
Дата: 08.12.04 11:59
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Спасибо за ответ, но из ваших примеров я не могу применить ничего к своему, потому что у меня объявлен multimap и в нем уже хранятся данные:


Нужно лишь немножко подумать, а не копировать в лоб.

Что такое мультимап? Это реляционная таблица с неуникальным ключом.
Что значит дополнительная сортировка? Это добавление в таблицу ещё одной колонки с другим неуникальным ключом.
Поэтому если задача выборки в разных порядках встаёт часто — заводим структуру из 3 полей:
— первичный ключ (ключ мультимапа)
— альтернативный ключ
— данные (класс Temp)
В роли альтернативного ключа могут выступать сами данные или их члены.

Для единовременной сортировки — делаем слепок. Замени в моём коде set на multimap, и учти, что элемент мультимапа — это std::pair<const key_type,value_type>. То есть для доступа к значениям, нужно делать не (*it), а (it->second).

Вот и всё.
Перекуём баги на фичи!
Re[8]: Однообразность в STL
От: Olivia Россия  
Дата: 08.12.04 14:43
Оценка:
Приветик, Кодт.
Большое спасибо за ответ, но у меня еще теперь такой вопрос ты под чем писал этот код, потому что у меня какая-то фигня получается, честно... (может у меня руки кривые, что скорее всего ) ты можешь мне на почту прислать написанную с твоим кодом элементарную програмку, чтобы я ее проверила под VC++ 6.0
Мой e-mail: olivia84@mail.ru
Re[8]: Однообразность в STL
От: 1darkangel1 Украина  
Дата: 09.12.04 10:05
Оценка:
Hello, Кодт!
You wrote on Wed, 08 Dec 2004 11:59:31 GMT:

К> Что такое мультимап? Это реляционная таблица с неуникальным ключом.

К> Что значит дополнительная сортировка? Это добавление в таблицу ещё одной
К> колонки с другим неуникальным ключом. Поэтому если задача выборки в
К> разных порядках встаёт часто — заводим структуру из 3 полей: — первичный
К> ключ (ключ мультимапа) — альтернативный ключ
К> — данные (класс Temp)
К> В роли альтернативного ключа могут выступать сами данные или их члены.

К> Для единовременной сортировки — делаем слепок. Замени в моём коде set на

К> multimap, и учти, что элемент мультимапа — это std::pair<const
К> key_type,value_type>. То есть для доступа к значениям, нужно делать не
К> (*it), а (it->second).

Если нельзя использовать стороние библиотеки или компилятор совсем дохлый, то по другому не сделаешь. Но если можно взять boost, то multi_index это очень сильное уменьшение головных болей как писателю так и читателю. Я сам был вынужден делать вышеописанным способом, так как небыло тогда еще этого boost::multi_index в релизе, но доки уже были и я там встретил решение вышеописанной задачи. Так что лучше, если можно, не париться, а сразу взять multi_index и забыть о проблемах.

With best regards, Konstantin Litvinenko. E-mail: darkangel@malva.ua
Posted via RSDN NNTP Server 1.8
Re[8]: Однообразность в STL
От: Olivia Россия  
Дата: 14.12.04 10:50
Оценка:
Здравствуйте, Кодт, Вы писали:

У меня возникли проблемы с кодом, который вы мне прислали на e-mail. Там в коде я пыталась поправить ключ multimap'а int на char*, ничего не получилось... Я написала вам письмо с просьбой помочь, но, вероятно, вы его не получили или просто не прочитали... Так вот просьба была следующей в той проге, которую вы пересылали мне на мыло, я пробовала заменить ключ int на char* ввозникли некоторые проблемы с перегрузкой оператора () и << Пожалуйста, можете проверить исправленный код у себя и поправить, и прислать мне.
Re[9]: Однообразность в STL
От: Shady Россия  
Дата: 14.12.04 11:19
Оценка:
Здравствуйте, Olivia, Вы писали:

O>Здравствуйте, Кодт, Вы писали:


O>У меня возникли проблемы с кодом, который вы мне прислали на e-mail. Там в коде я пыталась поправить ключ multimap'а int на char*, ничего не получилось... Я написала вам письмо с просьбой помочь, но, вероятно, вы его не получили или просто не прочитали... Так вот просьба была следующей в той проге, которую вы пересылали мне на мыло, я пробовала заменить ключ int на char* ввозникли некоторые проблемы с перегрузкой оператора () и << Пожалуйста, можете проверить исправленный код у себя и поправить, и прислать мне.

Оливия, не могли бы вы детально рассказать, что у вас за проблема. Я так понял в multimap'е храняться объекты класса Temp? Что является ключом? По каким критериям надо сортировать?
Рассказав всё это мне, я может вам помогу.
... << RSDN@Home 1.1.4 beta 3 rev. 240>>
"Man feed machine
Machine feed man"
Peter Gabriel — OVO — The Tower That Ate People
Re[9]: Однообразность в STL
От: Кодт Россия  
Дата: 14.12.04 13:19
Оценка: +1
Здравствуйте, Olivia, Вы писали:

O>У меня возникли проблемы с кодом, который вы мне прислали на e-mail. Там в коде я пыталась поправить ключ multimap'а int на char*, ничего не получилось... Я написала вам письмо с просьбой помочь, но, вероятно, вы его не получили или просто не прочитали... Так вот просьба была следующей в той проге, которую вы пересылали мне на мыло, я пробовала заменить ключ int на char* ввозникли некоторые проблемы с перегрузкой оператора () и << Пожалуйста, можете проверить исправленный код у себя и поправить, и прислать мне.


Вообще говоря, это классические грабли.
1) Строковые литералы имеют тип const char* (для совместимости с Си он иногда приводится к char*, но это жестоко)
2) Время жизни строк-ключей? Если это не литералы, то придётся вручную их прибивать
3) Операция сравнения? По умолчанию, map/multimap/set/multiset сравнивает значения ключей. А у тебя значения — это не содержимое строк, а указатели на них. Две одинаковых строки по разным адресам — и ку-ку.

Что делать?
Быстрый ответ: использовать объекты-строки. Например, std::string.
Я думаю, твои проблемы это решит.
Перекуём баги на фичи!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.