int main()
{
std::vector<std::pair<char, int>> vector;
vector.push_back(std::make_pair('d', 4));
vector.push_back(std::make_pair('b', 2));
vector.push_back(std::make_pair('e', 5));
vector.push_back(std::make_pair('c', 3));
vector.push_back(std::make_pair('a', 1));
qsort(&vector, vector.size(), sizeof(std::pair<char,int>), comp);
getchar();
}
int comp(const void* pair1, const void* pair2)
{
std::pair<char, int>* p1 = (std::pair<char, int>*)pair1;
std::pair<char, int>* p2 = (std::pair<char, int>*)pair2;
return p2->second - p1->second;
}
[С++]Проблема с сортировкой
Требуется отсортировать сложные объекты, хранящиеся в контейнере vector. Прилагаю код (смоделированный пример), которые получился после штудирования интернета (в том числе msdn), но там все примеры с простым типом (int):
Данный код компилируется, но на выходе получается полная фигня. После процедуры qsort в векторе находится лабуда. пробовал заглянуть в функцию comp во время выполнения, то уже при приведении типов получается фигня. Подскажите, как можно корректно решить данную проблему.
Работаю в MS Visual Studio 2010.
UPD: Изменил ссылку на msdn. По предыдущей ссылке была функция sort, а не текущая qsort. Через sort у меня тоже ничего не получилось. Если получится с ней, то тоже будет хорошо. Ведь они по скорости не отличаются?
UPD2: Сортировать нужно по double, по второму значению.
Код:
Данный код компилируется, но на выходе получается полная фигня. После процедуры qsort в векторе находится лабуда. пробовал заглянуть в функцию comp во время выполнения, то уже при приведении типов получается фигня. Подскажите, как можно корректно решить данную проблему.
Работаю в MS Visual Studio 2010.
UPD: Изменил ссылку на msdn. По предыдущей ссылке была функция sort, а не текущая qsort. Через sort у меня тоже ничего не получилось. Если получится с ней, то тоже будет хорошо. Ведь они по скорости не отличаются?
UPD2: Сортировать нужно по double, по второму значению.
arrjj, я наверное вопрос некорректно задал. Сортировку нужно произвести по второму значению, по double. Наличие составной структуры - ключевой момент в вопросе. Как простой тип отсортировать, я уже понял.
И? Что не получилось то?
Код:
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
bool mysort(pair<char,int> a,pair<char,int> b)
{
return a.second<b.second;
}
int main ()
{
int n;
vector< pair<char, int> > p;
p.push_back(make_pair('b', 2));
p.push_back(make_pair('e', 5));
p.push_back(make_pair('c', 3));
p.push_back(make_pair('a', 1));
sort (p.begin(),p.end(),mysort);
for (n=0; n<5; n++)
cout<<p.at(n).first<<":"<<p.at(n).second<<endl;
return 0;
}
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
bool mysort(pair<char,int> a,pair<char,int> b)
{
return a.second<b.second;
}
int main ()
{
int n;
vector< pair<char, int> > p;
p.push_back(make_pair('b', 2));
p.push_back(make_pair('e', 5));
p.push_back(make_pair('c', 3));
p.push_back(make_pair('a', 1));
sort (p.begin(),p.end(),mysort);
for (n=0; n<5; n++)
cout<<p.at(n).first<<":"<<p.at(n).second<<endl;
return 0;
}
И правда работает.
Я наверно зря зациклился на qsort. Sort как-то проще описан. Спасибо!
А все-таки, можете объяснить, почему мой код, через qsort, не работает?
Я наверно зря зациклился на qsort. Sort как-то проще описан. Спасибо!
А все-таки, можете объяснить, почему мой код, через qsort, не работает?
Вектор не массив. Почитай по ссылкам что я привел.
Цитата: Cybernetic
А все-таки, можете объяснить, почему мой код, через qsort, не работает?
Потому что здесь закралась хитрая ошибка:
Код:
qsort(&vector[0], vector.size(), sizeof(std::pair<char,int>), comp);
&vector[0]
arjj Ответ уже дал, в догонку комментарий.
Обратите внимание, что qsort - C-шная функция (из C library).
А вы с помощью нее пытаетесь отсортировать STL-контейнер vector (STL library), что неверно.
Собственно std::sort из #include <algorithm>
http://www.cplusplus.com/reference/algorithm/sort/
Обратите внимание, что qsort - C-шная функция (из C library).
А вы с помощью нее пытаетесь отсортировать STL-контейнер vector (STL library), что неверно.
Собственно std::sort из #include <algorithm>
http://www.cplusplus.com/reference/algorithm/sort/
Цитата: arrjj
Вектор не массив.
Цитата: grgdvo
Обратите внимание, что qsort - C-шная функция (из C library).
А вы с помощью нее пытаетесь отсортировать STL-контейнер vector (STL library), что неверно.
Зря вы так.
Чем, например, вот здесь - указатель p не сишный?:
Код:
std::vector<int> v;
v.resize(10);
int* p = &v[0];
int size = v.size();
v.resize(10);
int* p = &v[0];
int size = v.size();
Контейнер std::vector выделяет непрерывный блок памяти, и в результате, получив указатель p и размер size, можно скармливать этот блок любому сишному методу.
Т.о., учитывая поправку &vector[0], этот код автора с qsort будет работать:
Код:
#include <vector>
#include <stdio.h>
int comp(const void* pair1, const void* pair2)
{
std::pair<char, int>* p1 = (std::pair<char, int>*)pair1;
std::pair<char, int>* p2 = (std::pair<char, int>*)pair2;
return p2->second - p1->second;
}
int main()
{
std::vector<std::pair<char, int>> vector;
vector.push_back(std::make_pair('d', 4));
vector.push_back(std::make_pair('b', 2));
vector.push_back(std::make_pair('e', 5));
vector.push_back(std::make_pair('c', 3));
vector.push_back(std::make_pair('a', 1));
qsort(&vector[0], vector.size(), sizeof(std::pair<char,int>), comp);
for(int i=0; i<vector.size(); i++)
printf("%c %d\n", vector.first, vector.second);
}
#include <stdio.h>
int comp(const void* pair1, const void* pair2)
{
std::pair<char, int>* p1 = (std::pair<char, int>*)pair1;
std::pair<char, int>* p2 = (std::pair<char, int>*)pair2;
return p2->second - p1->second;
}
int main()
{
std::vector<std::pair<char, int>> vector;
vector.push_back(std::make_pair('d', 4));
vector.push_back(std::make_pair('b', 2));
vector.push_back(std::make_pair('e', 5));
vector.push_back(std::make_pair('c', 3));
vector.push_back(std::make_pair('a', 1));
qsort(&vector[0], vector.size(), sizeof(std::pair<char,int>), comp);
for(int i=0; i<vector.size(); i++)
printf("%c %d\n", vector.first, vector.second);
}
Вы все правильно говорите. Не спорю.
Но здесь больше срабатывает архитектурный принцип.
vector сложный объект и, строго говоря, нам положено о нем знать только то, что доступно через public интерфейс.
Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.
Соответственно правильнее использовать итератор, дабы потом не наступить на грабли невнятной этиологии.
Но здесь больше срабатывает архитектурный принцип.
vector сложный объект и, строго говоря, нам положено о нем знать только то, что доступно через public интерфейс.
Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.
Соответственно правильнее использовать итератор, дабы потом не наступить на грабли невнятной этиологии.
Цитата: grgdvo
vector сложный объект и, строго говоря, нам положено о нем знать только то, что доступно через public интерфейс. Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.
std::vector &operator[] доступен через public и делать для этой операции отдельный метод было бы, как это называется, syntax-sugar. Мало того, это довольно известный и применяемый приём, не лишенный потенциальных проблем при ненадлежащем использовании (как и любой другой вид работы с памятью без GC).
Цитата: grgdvo
Соответственно правильнее использовать итератор, дабы потом не наступить на грабли невнятной этиологии.
Вы всегда используете итератор для работы с std::vector?
Хотя это, конечно, уже оффтопик.
Цитата: cn_venom
Вы всегда используете итератор для работы с std::vector?
Нет, конечно.
Когда нужно получить доступ к конкретному элементу, тогда скобочки.
Когда нужен линейный перебор, тогда итератор. Массивы у меня часто переменной длины, поэтому лишний раз спрашивать и где-то хранить его длину - неохота.
Сортировка через STL кстати обладает еще рядом положительных моментов:
1. Меньше параметров, можно обойтесь всего двумя. qsort требует 4.
2. для std::sort нужно наличие оператора сравнения, кажется < или > - не суть. qsort требует глобальную функцию. При сортировке int - нет проблем std:sort и qsort - здесь равнозначны. При сортировке сложных объектов - я бы выбрал std::sort - поскольку оператор сравнения будет у моего же объекта, а не глобальная функция будет решать какой из них большой, какой меньше. Но это уже вопрос архитектурный, хотя и имеет отношение к сортировке.
А за ссылочку на цитату стандарта, спасибо. Надо будет полистать C++0x или как он там сейчас: C++11.
Цитата: grgdvo
vector сложный объект и, строго говоря, нам положено о нем знать только то, что доступно через public интерфейс.
Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.
Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.
Совместимость vector и мссивов C - часть стандарта: так задумано, интерфейс - указатель на первый элемент контейнера. Тем не менее, не следует использовать в одном языке говнотеки другого без лишней надобности. В данном случае, стандартная сортировка C++ гибче и, почти наверняка, более эффективна.
Цитата: Der Meister
Совместимость vector и мссивов C - часть стандарта: так задумано, интерфейс - указатель на первый элемент контейнера.
Да.
Цитата: Der Meister
Тем не менее, не следует использовать в одном языке говнотеки другого без лишней надобности.
Да, но не надо так презрительно.
Цитата: Der Meister
В данном случае, стандартная сортировка C++ гибче и, почти наверняка, более эффективна.
Гибче с точки зрения C++ да, но не эффективней.
Цитата: aks
Да, но не надо так презрительно.
Гибче с точки зрения C++ да, но не эффективней.
Гибче с точки зрения C++ да, но не эффективней.
Почему?
Цитата: Der Meister
Почему?
Потому что там негде быть эффективней, если речь идет о сортировке объектов.
А я слышал, что шаблоны, в отличие от функций, на которые передаются указатели, хорошо инлайнятся и оптиизируются.