Всем привет, напишу статейку о шаблоне, которого почему-то очень мало информации в интернете, особенно на русском языке.
И так, что такое приоритетная очередь - по сути это обычная очередь, в котором все элементы упорядочены по определенному правилу, которое вы можете задавать сами.
Если в обычной очереди мы можем удалять только верхний элемент, то тут мы можем удалить только элемент с наибольшим приоритетом. В принципе в остальном работа с ним ничем не отличается от обычных очередей, кроме как того, что есть пару неприятных моментов с методами упорядочивания.
Для того, чтоб использовать списки необходимо вверху вписать
#include <queue>
Как и для стеков, наиболее важные функции push, pop и top.
Первый пример:
Код:
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
using namespace std;
int main()
{
priority_queue <int, vector<int>, less<int> > P;
int x;
P.push(13); P.push(51); P.push(100); P.push(1);
while (!P.empty())
{
x = P.top();
cout << x << endl;
P.pop();
}
return 0; }
В этом примере после вывода вся очередь удаляется. Если вам необходимо сохранить очередь, и просто вывести, то рекомендую для этого создать функцию, где будет выводится просто копия. (Реализовано в последнем примере).
В результате выполнения этой программы на экран выведутся числа в порядке убывания. Если нам необходимо, чтоб выводило наоборот, то вместо less<int> написать greater<int>. Третий параметр - функция, по которой собственно происходит сравнивание.
В следующем примере мы создадим свой способ сравнивания элементов.
Код:
// Очередь с приоритетами; P.top() указывает
// на элемент, последняя цифра которого не больше
// последних цифр других элементов.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class CompareLastDigits {
public:
bool operator()(int x, int y)
{
return x % 10 > у%10;
}
}
int main()
{
priority_queue <int, vector<int>, CompareLastDigits> P;
int x;
P.push(12); P.push(1); P.push(100); P.push(17);
while (!P.empty()) { x = P.top();
cout << x << endl;
P.pop();
}
Теперь последний случай, если в очереди у нас находятся элементы нашего собственного класса. Пример возможно будет немного сложноват, если что - милости прошу, задавайте вопросы.
Задание звучит следующим образом:
Цитата:
Задан список участников очереди на печать. Поля: автор, название, объем. Преобразовать эту очередь соответственно приоритету в списке. Построить шаблон функции для вывода на экран информации про всех участников очереди.
Код:
// OOP_9.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
using namespace std;
// Сам клас
class Print_List
{
public:
static int count;
string Name, Author;
int size;
int n;
Print_List (int sizep=100, string Authorp="No_Name", string Namep = "No_Name")
{
size = sizep;
Author = Authorp;
Name = Namep;
count++;
n=count;
};
friend std::ostream &operator<<(std::ostream &out, Print_List &P) {
out<<"Size: "<<P.size<<" Author: "<<P.Author<<" Title: "<<P.Name<<" Priority: "<<P.n<<"\n";
return out;
};
// По этой функции происходит построение
bool operator()(Print_List x, Print_List y)
{
return x.n>y.n;
} ;
// Сравнивание
bool operator < (Print_List &d2)
{
return n<d2.n;
};
bool operator > (Print_List &d2)
{
return n>d2.n;
};
bool operator >= (Print_List &d2)
{
return n>=d2.n;
};
bool operator <= (Print_List &d2)
{
return n<=d2.n;
};
};
// Счетчик созданых экземпляров
int Print_List::count = 0;
template <class T>
void out(T t)
{
T P = t;
Print_List x;
while (!P.empty())
{
x = P.top();
cout << "Retrieved element: " << x ;
P.pop();
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int i, stime;
long ltime;
ltime = time(NULL);
stime = (unsigned) ltime/2;
srand (stime);
list <Print_List> l1;
for (int i=0; i<9; i++)
{
string s1, s2;
char s[200];
itoa(i, s, 10);
s1 = "AUTHOR " + string(s);
s2 = "TITLE " + string(s);
Print_List a(10*(i+1), s1, s2);
a.n=rand();
cout<<a;
l1.push_back(a);
}
priority_queue <Print_List, vector<Print_List>, Print_List> A, B;
list <Print_List>::iterator p;
p=l1.begin();
while (p!=l1.end())
{
Print_List a = *p;
A.push(a);
p++;
}
// Вывод приоритетного списка
cout<<"Outputing priority list\n";
out (A);
system("PAUSE");
return 0;
}
Оператор по своей сути является обычной функцией, но все они выполняются только
Оператор по своей сути является обычной функцией. Все операторы выполняются в строго определенном порядке, который задан их приоритетностью.
Рассмотрим выражение
int v = 2+2*2;
Если мы вначале выполним операцию сложения, то получим 8, если умножения, то получим 6.
Таблица приоритетов:
Приоритет
Оператор
[table 1 5 1] Приоритет|Оператор|Значение
1|+ (унарный)| Ничего не изменяет
1|- (унарный)|Множит на -1
2|++ (унарный)|Инкремент, увеличивает на 1
2|-- (унарный)|Декремент, уменьшает на 1
3|* (бинарный)|Умножение
3|/ (бинарный)|Деление
3|% (бинарный)|Остаток
4|+ (бинарный)|Сложение
4|- (бинарный)|Вычитание
5|=, *=, %=, +=, -= (специальные)|Присвоение
[/table]
Из таблицы сверху видно, что приоритет операции умножения выше, чем у операции сложения. А что, если в одной строке будут операторы одинакового приоритета? В таком случае они будут выполняться, как и в математике, слева направо.
int v = 8 / 4 / 2; // Получим 1
В выражении
x / 100 + 32
x делится на 100, потом к нему добавляется 32. А если нам нужно сменить порядок выполнения операций, то мы просто ставим скобки.
x/(100+32). В общем то и все.
Использование символьных массивов
Как известно массивы можно сделать любого типа, но строковые массивы имеют особое место и играют очень важную роль.
Слова из нашей речи могут быть записаны как массивы, под каждый символ выделяется одна ячейка массива.
Пример использования массива символов.
Код:
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
void displayArray (chat sArray[], in n)
{
for (int i=0; i<n; i++)
cout <<sArray[i];
}
int main ()
{
char Name[] = {'S','o','f','t','E','n','g','i','n','e','s','.','r','u'};
displayArrray (Name, 14);
cout<<endl;
system ("PAUSE");
return 0;
}
В программе был создан массив, фиксированного размера, в котором содержится название этого сайта. Он потом передается в функцию displayArray(), где отображается.
Программа работает абсолютно нормально, но если мы изменим длину строки, то уже возникнут определенные неудобства. Было б удобно, если б мы могли однозначно определить конец строки, тогда для вывода нам б не потребовалось знать его длину.
Создание строки символов.
Для таких целей в С++ существует специальный символ – ‘\0’. Его следует использовать для отметки конца строки.
Пример
В функции display () мы выводим все символы, пока не встретим нулевой символ. Такая функция более универсальна, и даже если в процессе обработки строки мы изменим ее длину, то нам не обязательно ее знать.
Строка символов – символьный массив, в конце которого есть специальный символ – нулевой. Очень распространённо называть их просто строками, хотя в С++ есть для таких вещей специальный тип – string.
Нулевой символ, выбран в качестве завершающего не просто так, ведь в нулевое значение преобразуется в логическое значение false, а все не нулевые конвертируются в true. А если к теме, то это значит, что можно написать так:
for (int i=0; sArray; i++)
Идентифицировать строку в С++ можно и более удобным способом – двойными кавычками. То есть мы могли написать так:
CharName[] = “SoftEngines.ru”
Управление строками
Для работами с строками в С++ существуют стандартные функции, вот некоторые из них:
[table 1 5 1] int strlen ([строка]) | Возвращает длину строки (без нулевого)
char* strcat ([строка 1], [строка 2]) |Присоединяет строку 2 к концу строки 1
char* strcpy ([строка 1], [строка 2]) | Копирует строку 1 в строку 2
char* strncat ([строка 1], [строка 2], n)| Присоединяет nсимволов строки 2 к строке 1 (nили меньше)
char* strncpy ([строка 1], [строка 2])| Копирует n(или меньше) символов строки 2 к строке 1
char* strstr ([строка 1], [строка 2])| Находит первое вхождение строки 2 в строку 1
intstrcmp ([строка 1], [строка 2])|Сравнивает строки
int stricmp ([строка 1], [строка 2])| Сравнивает строки без учета регистра символов
[/table]
Для того, чтоб все эти функции были вам доступны надо вверху прописать
#include <string.h>
Пример
Код:
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
#include <string.h>
void display (char sArray[]);
{
for (int i=0; sArray[i]!=0; i++)
cout << sArray[i];
}
int main ()
{
char s1[256];
cout <<"Input s1: ";
cin.getline (s1,128); //Безопасный способ считывания строк
char s2[256];
cout <<"Input s2: ";
cin.getline (s2, 128); //Безопасный способ считывания строк
char ss[256];
strncpy (ss, s1, 128); // Добавили строку в буфер
strncat (ss, ' - ', 4);
strncat (ss, s2, 128);
// Вывод на экран
cout << "\n" << ss<< endl;
system ("PAUSE");
return 0;
}
Ждите следующих уроков. Дальше будем рассказывать про string.
В приложенных файлах вы можете скачать этот урок в формате .pdf
Эта статья написана чуть чуть не тактично, скорее не для постоянных читателей а для пользователей, которые попали из поиска.
И так, все операторы в C# перегружаются самыми обычными способами, почти без особых нюансов. Нюансы заключаются вот в чем, операторы <, > <=, >= ==, !=
Перегружаются только в паре. То есть если вы перегрузили >, то перегрузите и <. Данное правило не лишено смысла и особых проблем не делает, а вот операторы ==, != кроме того, как тоже подлежат этому правилу, так еще и требуют перегрузку методов Equals(), GetHashCode(). Как это делать будет видно из примера ниже:
Код:
class Vector
{
double x; //Координаты
double y;
public Vector(double r1, double r2)
{
x = r1;
y = r2;
}
public override bool Equals(object obj)
{
if (((Vector)obj).x == this.x && ((Vector)obj).y == this.y)
{
return true;
}
else
{
return false;
}
}
public override int GetHashCode()
{
return this.GetHashCode();
}
public static bool operator ==(Vector m1, Vector m2)
{
return m1.Equals(m2);
}
public static bool operator !=(Vector m1, Vector m2)
{
return !m1.Equals(m2);
}
}
Рейтинг языков программирования - такая вещь, за которой должен следить каждый программист, который пытается остаться в деле, следить за последними тенденциями информационных технологий.
Ведь можно выучить досконально много всяких вещей, а зарплата то все равно пропорциональна не количеству знаний, а количеству полезной информации в вашей голове.
Сделать четкую выборку достаточно сложно, ведь учесть все проекты, все вакансии достаточно сложно... в каждой страны свои тенденции, свои требования, своя культура программирования, поэтому, наверное, наиболее надежный способ - анализ запросов в поисковых системах, и так смотрим.
