Условия сортировки в STL, C++ Опции

[first_day]

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

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

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

[volvo]

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

В принципе, можно написать свой критерий сортировки, и создать priority_queue именно с ним, но тогда нужно точно знать ответы на те вопросы, которые я задал...

[first_day]

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

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

[volvo]

Мне интересно как пишутся эти критерии соритровки.

Очень просто. Поскольку 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;
}

Попробуй догадаться, в каком порядке будут выводиться числа из приоритетной очереди?

можно ли из вектора сделать что-то вроде двумерного массива (т.е. не 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;

[first_day]

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

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

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

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

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

[volvo]

Можно ли добавить условие: например при равенстве суммы по неубыванию чисел?

И это можно. Переписываем метод вот так:

    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);
...

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

[first_day]

#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 - 3.05.2008 19:18

[volvo]

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

Может, не стоит опять изобретать велосипед?

[first_day]

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

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

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

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

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

[volvo]

Вот алгоритм 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;
}

[first_day]

Спасибо!