IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Условия сортировки в STL, C++
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


А можно ли в priority_queue (ну и в ее подобных) в критерие сортировки указать (если равно чему-то то не соритровать)? Например, мне нужно сформировать heap, но чтобы первый элемент не был равен X.

P.S. И вот еще такой вопрос созрел: можно ли из вектора сделать что-то вроде двумерного массива (т.е. не 1 строка, а 2 например)? если да, то как, и как потом с этим работать?

Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Погоди. Что значит, если элемент равен чему-то, то "не сортировать"? Не заноси этот элемент в очередь, если он равен X и все. Допустим, занес ты элемент в очередь, и сейчас метод top() должен его вернуть. Что будем делать? Ничего не возвращать? Вытащим этот элемент из начала очередь и засунем опять в конец?

В принципе, можно написать свой критерий сортировки, и создать priority_queue именно с ним, но тогда нужно точно знать ответы на те вопросы, которые я задал...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Цитата
Допустим, занес ты элемент в очередь, и сейчас метод top() должен его вернуть. Что будем делать? Ничего не возвращать? Вытащим этот элемент из начала очередь и засунем опять в конец?


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


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
Мне интересно как пишутся эти критерии соритровки.
Очень просто. Поскольку std::less - это структура, унаследованная от std::binary_function, то пишем свою структуру - наследника этой же STL-евской:

#include <fstream>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;

template <class T>
struct my_sort: public binary_function<T, T, bool> {

// функция должна быть константной, поскольку так же из константной и вызывается
int s(int value) const {
int sum = 0;
while(value > 0) {
sum += value %10;
value /= 10;
}
return sum;
}

// вот, собственно, что нам и требовалось:
bool operator() (const T& first, const T& second) const {
return s(first) > s(second);
}
};

int main() {
const int n = 10;
int arr[10] = {121, 311, 37, 114, 555, 436, 2117, 128, 979, 234};
priority_queue< int, vector<int>, my_sort<int> > q;
for(int i = 0; i < n; i++) {
q.push(arr[i]);
}

while (q.size() > 0)
{
int value = q.top(); q.pop();
cout << value << endl;
}
return 0;
}
Попробуй догадаться, в каком порядке будут выводиться числа из приоритетной очереди? smile.gif

Цитата
можно ли из вектора сделать что-то вроде двумерного массива (т.е. не 1 строка, а 2 например)? если да, то как
Можно, вот так, например:

	vector< vector<int> > mx(2, vector<int>());
mx[0].push_back(10);
mx[1].push_back(20);
cout << mx[0][0] << endl << mx[1][0] << endl;
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Спасибо. smile.gif Числа выведутся по неубыванию суммы цифр, а при совпадении суммы - случайно? Можно ли добавить условие: например при равенстве суммы по неубыванию чисел?

vector< vector<int> > mx(2, vector<int>());

Можно ли теперь этот вектор "поместить" в приорететную очередь? Или может это можно сделать иначе... Вот, что нужно:
(Это нужно для реализации Дейкстры с приорететной очередью. С массивами я делал, но так быстрее. Если будет понятнее, могу выложить код простой Дейкстры и указать что нужно заменить.)

Например у меня есть два "типа" данных - один кратчайшее расстояние до вершины, а второй - номер вершины. Эти расстояния должны находиться в очереди и на каждом шаге алгоритма извлекаться минимаьное, но в тоже время нужно как-то хранить информацию до какой вершины это расстояние.

Как это лучше сделать: отдельно вершины, а в очереди расстояния или все вместе можно как-то в очередь поместить?


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Цитата
Можно ли добавить условие: например при равенстве суммы по неубыванию чисел?
И это можно. Переписываем метод вот так:
    bool operator() (const T& first, const T& second) const {
int one = s(first), two = s(second);
return (one == two) ? (first > second) : (one > two);
}


Цитата
Можно ли теперь этот вектор "поместить" в приорететную очередь?
Да пойми ты, в очередь можно поместить все, что угодно. Скажем, для вышеописанной матрицы (вектора из векторов) можно сделать так:
...
priority_queue< vector< vector<int> > > q1;
q1.push(mx);
...

и все будет работать. Вопрос в том, надо ли оно... Приводи свою реализацию Дейкстры, посмотрим, что можно заменить, и вообще, как ускорить. Только приводи вместе с исходными данными (если они есть, конечно).
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


#include <fstream>
using namespace std;
int main ()
{
bool flag=true;
const int MAXN=100;
int sm[MAXN][MAXN], //матрица смежности
b[MAXN]={0}, //множества
d[MAXN], //расстояния
i,j,p,n,s,f;
ifstream in("input.txt");
ofstream out("output.txt");
in>>n>>s>>f;
s--; //из какой
f--; //в какую
for(i=0;i<n;d[i]=-1,b[i]=2,i++); //расстояния до всех -1, все принадлежат к 3 множеству
b[s]=0; //начальную вершину в 1 множество
d[s]=0; //расстояние до нее 0

/*1 множество - минимальное расстояние найдено
2-расстояние найдено, но не известно минимально ли оно,
3-пути нет*/

for(i=0;i<n;i++)
for(j=0;j<n;j++)
in>>sm[i][j];
for(i=0;i<n;i++) //нахожу соседей начальной вершины
if (sm[s][i]>0)
{
b[i]=1;
d[i]=sm[s][i];
}
while (flag)
{
flag=false;
int m=-1; //бесконечность
for(i=0;i<n;i++) //нахожу минимум из расстояний от началной вершины до вершин из 2 множества
if (b[i]==1 && (d[i]<m || m==-1))
{
m=d[i];
p=i;
}
b[p]=0; //переношу эту вершину в 1 множество
for(i=0;i<n;i++) //пробегаюсь по соседям этой вершины
if (sm[p][i]!=-1) //если путь есть
{
if (b[i]==2)
b[i]=1;
if (b[i]==1)
{
if (d[i]==-1)
d[i]=d[p]+sm[p][i];
else
d[i]=min(d[i],d[p]+sm[p][i]); //выбираю минимум из того, что было и что нашел
}
}
for(i=0;i<n;i++)
if (b[i]==1)//если есть вершины второго множества продолжаем
flag=true;
}
out<<d[f];
return 0;
}


Вход:
3 1 2
0 -1 2
3 0 -1
-1 4 0
выход: 6

-1 означает отсутствие пути.

С такими ограничениями все, конечно, работает. Но вдруг попадется задача с бОльшими да и просто интересно сделать...

Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






На TopCoder выложена, кстати, реализация Дейкстры с использованием priority_queue<> и с использованием set<>...

Может, не стоит опять изобретать велосипед?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Велосипед изобретать может и не нужно, а понять как колеса крутятся хочется. smile.gif

Почитал эту реализацию, но... не понятно очень много. Непонимание начинается с typedef, а дальше не совсем понятно как обращаются к элементам очереди; по какому полю идет соритровка (я догадываюсь, что должна идит по полю с расстоянием), но какое оно: первое, второе?

если можете, поясните пожалуйста, как поместить в очередь эту pair, и как потом обращаться к элементам...

P.S. Попробую почитать то, что выше, может поможет smile.gif

Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Вот алгоритм T.Budd-а, подправленный Sedgewick-ом, и перенесенный мной на описанную задачу (я не стал заморачиваться со вводом матрицы, не думаю, что это будет проблемой):

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

class Destination {
public:
int destination; // куда путь держим - номер узла
unsigned int distance; // расстояние до этого узла

// конструктор класса Destination
Destination(int dt, unsigned int ds): destination(dt), distance(ds) {
}

bool operator < (const Destination& right) const {
return distance > right.distance;
} // изменяем порядок приоритетной очереди на "первый - меньший"
};

// карта, содержит мин. дистанцию от каждого узла до всех остальных
typedef map<int, unsigned int> nodeInfo;
typedef map<int, nodeInfo> graph; // а это свяжет каждый узел с соседями...

void dijkstra(graph& theMap, int start_from, nodeInfo& minDistance)
{
priority_queue <Destination> que;
que.push(Destination(start_from, 0));

// пока очередь не пуста:
while(!que.empty()) {
// забираем мин. путь из очереди
int newNode = que.top().destination;
int dist = que.top().distance;
que.pop();

// если этот узел ранее не посещался
if(minDistance.count(newNode) == 0) {
// посетим-ка его...
minDistance[newNode] = dist;
// и все узлы, доступные из него добавим в очередь
nodeInfo::iterator start = theMap[newNode].begin();
nodeInfo::iterator stop = theMap[newNode].end();

for(; start != stop; ++start) {
int destNode = (*start).first;
unsigned int destDistance = (*start).second;
que.push(Destination(destNode, dist + destDistance));
}
}
}
}
int main() {
graph g;

// отсутствие пути задается числом 100000, поскольку это unsigned int...
g[0][0] = 0; g[0][1] = 100000; g[0][2] = 2;
g[1][0] = 3; g[1][1] = 0; g[1][2] = 100000;
g[2][0] = 100000; g[2][1] = 4; g[2][2] = 0;

nodeInfo dests;
dijkstra(g, 0, dests);
nodeInfo::iterator it = dests.begin(), stop = dests.end();
for( ; it != stop ; it++ ) {
std::cout << "расстояние до " << it->first << " равно " << it->second << '\n';
}
return 0;
}

 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Спасибо!


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 17.01.2021 2:09
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name