Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

[С++]Проблема с сортировкой

10K
26 января 2012 года
Cybernetic
106 / / 22.07.2009
Требуется отсортировать сложные объекты, хранящиеся в контейнере vector. Прилагаю код (смоделированный пример), которые получился после штудирования интернета (в том числе msdn), но там все примеры с простым типом (int):
Код:
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;
}


Данный код компилируется, но на выходе получается полная фигня. После процедуры qsort в векторе находится лабуда. пробовал заглянуть в функцию comp во время выполнения, то уже при приведении типов получается фигня. Подскажите, как можно корректно решить данную проблему.

Работаю в MS Visual Studio 2010.

UPD: Изменил ссылку на msdn. По предыдущей ссылке была функция sort, а не текущая qsort. Через sort у меня тоже ничего не получилось. Если получится с ней, то тоже будет хорошо. Ведь они по скорости не отличаются?

UPD2: Сортировать нужно по double, по второму значению.
277
26 января 2012 года
arrjj
1.7K / / 26.01.2011
Код:
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

char values[] = { 'h', 'o', 'y', 'q', 't', 'z' };

int main ()
{
  int n;
  vector<unsigned char> p(values, values+6);
  sort (p.begin(),p.end());
  for (n=0; n<6; n++)
     cout<<p.at(n)<<"\t";
  cout<<endl;
  return 0;
}


sort
qsort
10K
26 января 2012 года
Cybernetic
106 / / 22.07.2009
arrjj, я наверное вопрос некорректно задал. Сортировку нужно произвести по второму значению, по double. Наличие составной структуры - ключевой момент в вопросе. Как простой тип отсортировать, я уже понял.
277
26 января 2012 года
arrjj
1.7K / / 26.01.2011
И? Что не получилось то?
Код:
#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;
}
10K
26 января 2012 года
Cybernetic
106 / / 22.07.2009
И правда работает.
Я наверно зря зациклился на qsort. Sort как-то проще описан. Спасибо!

А все-таки, можете объяснить, почему мой код, через qsort, не работает?
277
26 января 2012 года
arrjj
1.7K / / 26.01.2011
Вектор не массив. Почитай по ссылкам что я привел.
24K
07 февраля 2012 года
cn_venom
11 / / 23.01.2007
Цитата: Cybernetic

А все-таки, можете объяснить, почему мой код, через qsort, не работает?



Потому что здесь закралась хитрая ошибка:

 
Код:
qsort(&vector[0], vector.size(), sizeof(std::pair<char,int>), comp);


&vector[0]
412
08 февраля 2012 года
grgdvo
323 / / 04.07.2007
arjj Ответ уже дал, в догонку комментарий.
Обратите внимание, что qsort - C-шная функция (из C library).
А вы с помощью нее пытаетесь отсортировать STL-контейнер vector (STL library), что неверно.
Собственно std::sort из #include <algorithm>
http://www.cplusplus.com/reference/algorithm/sort/
24K
08 февраля 2012 года
cn_venom
11 / / 23.01.2007
Цитата: 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();


Контейнер 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);
}
412
09 февраля 2012 года
grgdvo
323 / / 04.07.2007
Вы все правильно говорите. Не спорю.
Но здесь больше срабатывает архитектурный принцип.

vector сложный объект и, строго говоря, нам положено о нем знать только то, что доступно через public интерфейс.
Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.
Соответственно правильнее использовать итератор, дабы потом не наступить на грабли невнятной этиологии.
24K
09 февраля 2012 года
cn_venom
11 / / 23.01.2007
Цитата: grgdvo

vector сложный объект и, строго говоря, нам положено о нем знать только то, что доступно через public интерфейс. Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.



std::vector &operator[] доступен через public и делать для этой операции отдельный метод было бы, как это называется, syntax-sugar. Мало того, это довольно известный и применяемый приём, не лишенный потенциальных проблем при ненадлежащем использовании (как и любой другой вид работы с памятью без GC).

Цитата: grgdvo

Соответственно правильнее использовать итератор, дабы потом не наступить на грабли невнятной этиологии.



Вы всегда используете итератор для работы с std::vector?

Хотя это, конечно, уже оффтопик.

412
10 февраля 2012 года
grgdvo
323 / / 04.07.2007
Цитата: cn_venom

Вы всегда используете итератор для работы с std::vector?


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

Сортировка через STL кстати обладает еще рядом положительных моментов:
1. Меньше параметров, можно обойтесь всего двумя. qsort требует 4.
2. для std::sort нужно наличие оператора сравнения, кажется < или > - не суть. qsort требует глобальную функцию. При сортировке int - нет проблем std:sort и qsort - здесь равнозначны. При сортировке сложных объектов - я бы выбрал std::sort - поскольку оператор сравнения будет у моего же объекта, а не глобальная функция будет решать какой из них большой, какой меньше. Но это уже вопрос архитектурный, хотя и имеет отношение к сортировке.

А за ссылочку на цитату стандарта, спасибо. Надо будет полистать C++0x или как он там сейчас: C++11.

341
10 февраля 2012 года
Der Meister
874 / / 21.12.2007
Цитата: grgdvo
vector сложный объект и, строго говоря, нам положено о нем знать только то, что доступно через public интерфейс.
Как вы видите указатель наружу vector не показывает (его конечно можно получить), а показывает итератор.

Совместимость vector и мссивов C - часть стандарта: так задумано, интерфейс - указатель на первый элемент контейнера. Тем не менее, не следует использовать в одном языке говнотеки другого без лишней надобности. В данном случае, стандартная сортировка C++ гибче и, почти наверняка, более эффективна.

240
13 февраля 2012 года
aks
2.5K / / 14.07.2006
Цитата: Der Meister
Совместимость vector и мссивов C - часть стандарта: так задумано, интерфейс - указатель на первый элемент контейнера.


Да.

Цитата: Der Meister

Тем не менее, не следует использовать в одном языке говнотеки другого без лишней надобности.


Да, но не надо так презрительно.

Цитата: Der Meister

В данном случае, стандартная сортировка C++ гибче и, почти наверняка, более эффективна.


Гибче с точки зрения C++ да, но не эффективней.

341
13 февраля 2012 года
Der Meister
874 / / 21.12.2007
Цитата: aks
Да, но не надо так презрительно.
Гибче с точки зрения C++ да, но не эффективней.

Почему?

277
13 февраля 2012 года
arrjj
1.7K / / 26.01.2011
Цитата: grgdvo

2. для std::sort нужно наличие оператора сравнения, кажется < или > - не суть. qsort требует глобальную функцию.



sort
sort две версии, одна хочет operator <, вторая может использовать глобальный метод сравнения.

240
13 февраля 2012 года
aks
2.5K / / 14.07.2006
Цитата: Der Meister
Почему?


Потому что там негде быть эффективней, если речь идет о сортировке объектов.

341
14 февраля 2012 года
Der Meister
874 / / 21.12.2007
А я слышал, что шаблоны, в отличие от функций, на которые передаются указатели, хорошо инлайнятся и оптиизируются.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог