SEWiki - Вклад участника [ru]

Участник:Alexey.Gurevich

2011-09-18T18:38:34Z

Alexey.Gurevich:

== Алексей Гуревич ==
[mailto:alexeigurevich@gmail.com alexeigurevich@gmail.com]

[[Файл:Gurevich.JPG|200px|right]]

''Образование''

* 2010-наст.вр. Санкт-Петербургский академический университет РАН (магистратура)
* 2006-2010 Санкт-Петербургский государственный политехнический университет, Факультет технической кибренетики, кафедра Информационных и управляющих Систем (бакалавриат)
* 2002-2006 Лицей "Физико-техническая школа" Академического университета РАН

''Опыт работы''

* 07/2011-наст.вр. [http://bioinf.spbau.ru/ Лаборатория алгоритмической биологии], intern
* 03/2009-07/2010 СПбГПУ, каф. ИУС, researcher (Java)

Исключения

2011-06-01T07:51:57Z

Alexey.Gurevich: /* Исключения */

== Обработка ошибок ==
В программах всегда возникают ошибки. Их надо уметь обрабатывать, иначе часто мы будем беспокоить пользователя по пустяку. Рассмотрим основные способы обработки ошибок.

== Обработка кода возврата ==
Из каждой функции возвращаем код, в котором содержится дополнительная информация о результате работы функции.
Программист функции задает семантику этого кода. Одним из его значений должен быть "успех". Результат функции возвращается через параметр, передаваемый по ссылке.
Такой подход увеличивает колличество кода. Нужно проверять код возврата. В зависимости от проекта, этот код может понадобиться проверять каждый раз после вызова функции.
Также пользователь функции должен знать семантику кода возврата. Для кода возврата можно не создавать отдельную переменную в сигнатуре функции.
Можно возвращать значение, которое не входит в множество допустимых значений. Например, результат функции всегда положительный, но мы возвратим отрицательное число, если что-то пошло не так.
Тогда вызов будет короче, но мы совместим ответственности - результат будет отвечает и за ошибки. Если множество значений функции в перспективе может расшириться, то этот способ не подходит.

== Глобальная переменная errno ==
Все функции в случае возникновения ошибки записывают ее код в глобальную переменную errno. Проверять errno может понадобиться после каждого вызова.
При таком подходе мы можем строить выражения из вызовов функций. Использование глобальной переменной требует синхронизации в многопоточных приложениях.

== SEH, Signals ==
Платформенно зависимые исключения и сигналы от ОС. Например деление на 0, извлечение квадратного корня из отрицательного числа, разъименование нулевого указателя, порча стека и т.п.
Обычно говорят о том, что дальнейшее выполнение программы не имеет смысла, потому часто явно не обрабатываются в программах. 24/7/365 сервисы обычно требуют обработки таких исключений.
Это отдельная большая тема.

== Assert ==
Это утверждения, логические условия, истинность которых проверяется либо во время выполнения, либо во время компиляции (static assert).
Если статическое утверждение во время компиляции ложно, то возникает ошибка компиляции. Если во время вполнения утверждение ложно, то
в стандартный поток ошибок выводится текст этого утверждения и программа завершается.
Assert'ы отключаются, если при компиляции определен символ NDEBUG.

Пример:

<source lang="cpp">
#include <cassert>
assert(1 + 1 == 2 && "working with field which charcteristic > 2");
</source>

Строка с комментарием к assert'у "working with ..." - это ненулевой char const *, потому он всегда True и не влияет на результат логического И.

== Исключения ==
Исключение - событие, возникающее во время выполнения программы. Обычно обозначает что-то негативное. Существуют различные точки зрения на то, когда нужно использовать исключения.
Некоторые используют их, когда произошло малейшее нарушение работы программы (например ошибка конвертации строки в число), а другие только в случае если дальнейшее выполнение программы не имеет смысла.

Работа с исключениями состоит из следующих этапов:
* Выполнено условие, при котором стоит сообщить внешнему коду о произошедшей ошибке.
* Бросается исключение.
* Исключение всплывает по стеку вызовов программы до первой точки, в которой это исключение может быть обработано.
* В обработчике исключения можно выполнить все действия для восстановления программы и продолжить ее выполнение или если это не возможно в данном месте кода, бросить новое исключение дальше по стеку.
* Если исключение не было обработано и всплыло выше функции main, то вызывается обработчик unexpected, который по умолчанию завершает выполнение программы.

Некоторые моменты:
* Если исключение поймано (обработано), то вызовутся деструкторы всех объектов, которые лежали на стеке от места бросания до места обработки.
* Если мы выделим память в куче, а затем кинем исключение, то выделенная память не будет освобождена (деструктор указателя ничего не делает).
* Реальный механизм работы исключений и его накладные расходы зависит от разрядности процессора и ОС.

Рассмотрим базовый синтаксис работы с исключениям ив C++:

<source lang="cpp">
try
{
if (a == 0)
throw 0;
int res = 10/a;
}
catch(int ex)
{
if (ex == 0)
std::cerr << "division by zero" << std::endl;
}
catch(float ex)
{
if (ex >= 0)
std::cerr << "float" << std::endl;
}
</source>

* Оператор <code>try {}</code> показывает границы блока кода, в котором мы хотим ловить исключения. Исключения будут ловиться не только в самом блоке,
но и ниже по стеку вызовов - во всех функциях, вызванных из блока <code>try</code>.
* Оператор <code>catch(...){}</code> определяет код-обработчик исключения, который выполняется в случае если оно было кинуто в <code>try</code>. Аргумент <code>...</code> означает что будут ловиться все исключения.
Если мы хотим перехватить исключение какого-то конкретного типа, то в аргументе <code>catch</code> объявляют переменную этого типа. Для классов и структур используется константная ссылка.
* Оператор <code>throw</code> принимает экземпляр типа, который мы хотим кинуть.

Давайте поймем почему код, который бросает примитивные типы плох?
В обработчике <code>catch</code> нам приходится проверять какое целое значение было кинуто, чтобы понять что с ним делать.
Мы можем определить отдельный класс для каждого исключения и бросать уже объекты этих классов.
Это избавит нас от необходимости проверять еще какую-то информацию, неявно передаваемую в кидаемом экземпляре примитивного типа.
Для удобства в стандартной библиотеки <code>stl</code> уже есть класс исключений <code>std::exception</code>, объявленный в файле <code><exception></code>. Для поддержания единообразности кода на C++, следует наследовать свои классы исключений от него. Также у <code>std::exception</code> есть виртуальный метод <code>what()</code>, который удобно использовать для возвращения информации об исключении
в удобном для прочитывания человеком формате. Также стандартная библиотека определяет некоторые другие классы, например <code>std::logic_error, std::runtime_error, std::bad_alloc</code>.

Нужно помнить, что при выборе блока <code>catch</code>, который соответствует кинутому исключению, приведение типов не происходит. Одновременно может быть активно только одно исключение, поэтому если во время всплытия исключения по стеку
до того как исключение найдет свой обработчик, кинется еще одно исключение, программа полностью закончит свое выполнение. Теперь давайте вспомним какой код выподняется
во время всплытия исключения - происходят вызовы всех деструкторов. Если хотябы один деструктор кинет исключение, то программа полностью завершится. Поэтому деструкторы не должны кидать исключений.
Теперь представим себе что будет, если кинуть исключение в конструкторе - до завершения конструктора объект не считается созданным, потому в случае падения исключения в конструкторе, деструктор создаваемого объекта
не будет вызван. То есть если мы уже выделили какой-то ресурс в конструкторе, а потом в нем возникло исключение, то ресурс не будут освобожден.
Поэтому надо писать конструкторы так, чтобы при возникновении в нем исключения, можно было освободить занятые ресурсы и сообщить об исключении дальше.
Напомним также, что при нормальной работе программы оператор <code>delete</code> не кидает исключений, а оператор <code>new</code> может.
Напишем класс, который освободит выделенную память если произошло исключение в конструкторе.
Здесь же используется специальный синтаксис для перехвата исключений в списке инициализации.

<source lang="cpp">
struct A
{
int* p1;
int* p2;

A(size_t p1_sz, size_t p2_sz)
try
: p1(new int[p1_sz])
, p2(0)
{
try
{
p2 = new int[p2_sz];
}
catch(...)
{
delete[] p1; //only p1 allocated
throw;
}
}
catch(...)
{
//no memory allocated
throw;
}

~A()
{
delete[] p1;
delete[] p2;
}
};
</source>

Упражнение:
Опеределить сколько исключений может быть брошено в следующем участке кода, если a и b - экземпляры произвольных типов данных.

<source lang="cpp">
if (a + b == c + d)
{
return a * b;
}
</source>

Подсказка: учтите что вызываются операторы приведения типов, +, *, ==.

== Гарантии, которые может предоставлять код по отношению к исключениям ==
Далее будет удобно оперировать понятием объекта, но все сказанное также относится и к обычным функциям.
Код, который мы пишем и используем, при возникновении внутри себя исключений может вести себя по разному. Это поведение и определяют уровни гарантий исключений.
Они специфицируют каким будет поведение кода и каково будет состояние объекта по отношению к внешнему миру, после возникновения в нем исключения. Рассмотрим их.

* Гарантия отсутствия исключений. Такая гарантия специфицирует, что либо ошибок нет, либо все ошибки обрабатываются и объект выполняет все требуемые функции.
* Строгая гарантия исключений (транзакционность). Объект после обработки ошибки возвращается в состояние перед вызовом метода, в котором она возникла. Если мы выполняем ввод\вывод, то гарантировать строгую гарантию невозможно без очень сложных мероприятий.
* Базовая гарантия. После обработки исключения оказываемся в любом другом согласованном состоянии.

Напишем неполный класс массива, который реализует строгую гарантию исключений при копировании через конструктор.
<source lang="cpp">
template<typename T>
struct Array
{
Array(size_t size)
: size_(size)
, data_(new T[size])
{}

Array(Array const & src)
{
T* old_data = data_;
size_t old_size = size_;
try
{
data_ = new T[src.size_];
size_ = src.size_;
for(size_t i = 0; i < size_; ++i)
data_[i] = src.data_[i];
}
catch(...)
{
delete data_;
data_ = old_data;
size_ = old_size;
}
}

private:
T* data_;
size_t size_;
};
</source>

Обсуждение:Исключения

2011-06-01T07:45:43Z

Alexey.Gurevich:

Мне кажется, что вместо 24/7/365 стоит написать просто 24/7. Так как в году 365 '''дней''' (и то только в чуть больше чем 75% случаев), а не '''недель'''.

Обсуждение:Исключения

2011-06-01T07:43:59Z

Alexey.Gurevich: Новая страница: «Мне кажется, что вместо 24/7/365 стоит написать просто 24/7. Так как в году 365 '''дней''' (и то только…»

Мне кажется, что вместо 24/7/365 стоит написать просто 24/7. Так как в году 365 '''дней''' (и то только в менее чем 75% случаев), а не '''недель'''

Приведение типов. RTTI

2011-05-30T18:13:22Z

Alexey.Gurevich:

==Приведение типов==
Приведение типов делится на C style cast и C++ style cast
===Приведение в стиле C===
Синтаксис приведения:
* (тип_к_которому_приводим) переменная
* тип_к_которому_приводим (переменная)

Примеры:
<source lang="cpp">
int i = 10;
double d = (double) i;
float f = float(i);
char const* ch = "hello";
string str = (string) ch;
</source>

===Приведение в стиле С++===
В С++ для приведения типов используются следующие функции:
* const_cast
* reinterpret_cast
* static_cast
* dynamic_cast
Во всех случаях синтаксис приведения будет выглядеть следующим образом:
..._cast <тип_к_которому_приводим> (переменная)

Рассмотрим первые три более подробно (dynamic_cast рассматривается в разделе RTTI).
====const_cast====
Добавляет/убирает у объекта константность. Если убрать константность у объекта, который был объявлен как константный, то при записи может возникнуть undefined behavior (в зависимости от типа объекта).

Рассмотрим ситуацию, когда нам может пригодиться const_cast.
Предположим у нас класс A, в котором хранятся элементы типа Т. Пусть требуется реализовать метод get (константный и не константный), который по индексу i будет возвращать i-ый элемент. Можно описать реализацию только одного метода (константного), а второй реализовать через вызов первого при помощи const_cast:
<source lang="cpp">
T const& get (int i) const;
T& get (int i) {
return const_cast<T&> (const_cast<A const*> (this).get(i) );
}
</source>
====reinterpret_cast====
Приводит любой указатель к любому указателю.

Пример:
<source lang="cpp">
struct Point3 {
double x;
double y;
double z;
};
...
Point3* p = ...;
double* p_x = reinterpret_cast<double*> (p);
</source>
Замечание: приведенный пример отработает корректно в случае если структура Point3 плотно упакована в памяти (см. опции компилятора).
====static_cast====
Используется для приведения
* числовых типов (аналогично C-style cast)
* указателей и ссылок для классов связанных наследованием
* пользовательских преобразований
Преобразование выполняется в момент компиляции и run-time проверки (как это есть в dynamic_cast) приведения типов нет, поэтому сложные приведения типов следует делать очень аккуратно.

Пример:
<source lang="cpp">
struct A {};
struct B : A {};
...
B* b;
A* a = static_cast<A*> (b);
b = static_cast<B*> (a);
</source>

Замечание: static_cast меняет указатель в зависимости от того какое у классов наследование (в отличии от reinterpret_cast), поэтому если будет forward declaration, то static_cast выдаст ошибку (на этапе компиляции):
<source lang="cpp">
struct A;
struct B;
B* b;
A* a = static_cast<A*>(b); // ошибка!
</source>

----
Общее замечание по разделу Приведение типов:
При программировании на С++ рекомендуется использовать C-style cast только в случаях приведения элементарных типов друг к другу.

==RTTI==
RTTI расшифровывается как Run-time type information. Это механизм, позволяющий определять тип объекта в момент выполнения программы. В С++ данный механизм реализуется при помощи следующих элементов:
* оператор dynamic_cast (используется для преобразования полиморфных типов)
* оператор typeid (для точного определения типа объекта)
* класс type_info (для хранения информации, возвращаемой оператором typeid)

Рассмотрим применение и синтаксис typeid и type_info на примере:
<source lang="cpp">
#include <typeinfo>
...
A* a;
type_info& ti = typeid(a);
std::cout << ti.name() << std::endl;
</source>
Более сложный пример:

<source lang="cpp">
#include <typeinfo>
struct A {};
struct B : A {};
...
A* a = new B();
typeid(a); // A*
typeid(*a); // B
</source>

У класса type_info помимо метода name (возвращающего строку - char*, характеризующую тип объекта) и операторов равенства/неравенства есть еще метод before, который позволяет упорядочивать экземпляры type_info и хранить их, например, в map.

===dynamic_cast===
Позволяет приводить указатель или объект одного типа к указателю или ссылке на другой класс (связанный с первым через наследование).
В отличии от static_cast выполняется в run-time.
При ошибке приведения к указателю на тип dynamic_cast возвращает нулевой указатель, при ошибке приведения к ссылке на тип выбрасывается исключение bad_cast.

Пример использования:
<source lang="cpp">
struct A {
virtual void f() {}
};
struct B : A {
virtual void f() {}
};

...
A* pa = new B;
A* pa2 = new A;

B* pb = dynamic_cast<B*>(pa); // pb указывает на B
B* pb2 = dynamic_cast<B*>(pa2); // pb2 указывает на А, а не на В!

pb->f();
pb2->f(); // ошибка на этапе исполнения!
</source>

Замечание: При приведении к указателю на void возвращается указатель на начало блока.

----
Общие замечания по разделу RTTI:
* почти всегда можно обойтись без RTTI и чаще всего использование этого механизма говорит об ошибке проектирования
* на этапе отладки применение RTTI бывает полезно.

Приведение типов. RTTI

2011-05-30T17:40:09Z

Alexey.Gurevich: Новая страница: «==Приведение типов== Приведение типов делится на C style cast и C++ style cast ===Приведение в стиле C=== С…»

Конспекты С++

2011-05-30T08:46:32Z

Alexey.Gurevich: /* 2 семестр (зима-весна 2011) */

== 1 семестр (осень-зима 2010) ==

* [[ Как происходит компиляция|Как происходит компиляция. Алексей Давыдов. 08.09.2010]]
* [[ Указатели и ссылки|Указатели и ссылки. Екатерина Полищук. 10.09.2010]]
* [[ Динамическое распределение памяти|Динамическое распределение памяти. Алексей Гуревич. 17.09.2010]]
* [[ Классы|Классы. Курьян Кристина. 08.10.2010]]
* [[ Перегрузка операторов|Перегрузка операторов. Мария Фомкина. 12.11.2010]]
* [[ Множественное наследование, дружба|Множественное наследование, дружба Евгений Баталов. 02.12.2010]]

== 2 семестр (зима-весна 2011) ==

* [[ Напоминание про inline и static. Синглтон.|Напоминание про inline и static. Синглтон. Екатерина Полищук. 11.02.2011]]
* [[ STL. Последовательные контейнеры|STL. Последовательные контейнеры. Мария Фомкина. 18.02.2011]]
* [[ Ассоциативные контейнеры |STL. Ассоциативные контейнеры. Светлана Марченко. 25.02.2011]]
* [[ Итераторы и алгоритмы | Итераторы и алгоритмы. Всеволод Опарин. 04.03.2011]]
* [[ Функторы, часть вторая. Иван Близнец. когда-то | Функторы. Namespaces. Иван Близнец. 09.03.2011 ]]
* [[ Указатели на функции|Указатели на функции. Курьян Кристина. 18.03.2011]]
* [[ Исключения | Методы обработки ошибок. Исключения. Гарантии исключений. Евгений Баталов. 01.04.2011 ]]
* [[ Приведение типов. RTTI | Приведение типов. RTTI. Алексей Гуревич. 15.04.2011 ]]
* [[ Метапрограммирование на C++ | Метапрограммирование на C++. Александр Карташов. 06.05.2011 ]]

Задания по С++

2011-03-30T07:35:26Z

Alexey.Gurevich: /* Лабораторная работа №4 iterator */

== Лабораторная работа №1 Шаблоны ==
Реализовать собственный контейнер
<source lang="cpp">template<typename T>
class Container {
public:
void push_back(const T& t);
T& back();
size_t size() const;
};</source>
В качестве хранилища значенией в реализации <code>Container</code> используйте <code>std::vector</code>.

Затем создайте новый контейнер с двумя шаблонными параметрами, первый - тип хранимых значений, второй - тип хранилища, используемый в реализации вашего контейнера.

Пример использования такого контейнера
<source lang="cpp">
Container<int, std::list<int> > c;
</source>

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

Пример использования такого контейнера
<source lang="cpp">
Container<int, std::deque> c;
</source>

== Лабораторная работа №2 Синглтон ==

Написать протой логгер
<source lang="cpp">class Logger {
public:
void warn(const std::string& msg);
static Logger& getInstance();
};
</source>
Запретить пользователю его создание, копирование.

Пример использования
<source lang="cpp">
Logger& log = Logger::getInstance();
log.warn("Ooops");
</source>

Представить, что понадобилось ещё несколько синглтонов, вынести общий для всех синглтонов код в отдельный класс <code>Singleton</code>.
Реализовать логгер с использованием класса <code>Singleton</code> так, чтоб код, использующий логгер, не надо было модифицировать.

== Лабораторная работа №3 merge sort ==
Необходимо написать функцию сортировки слиянием. 
Сигнатура функции должны быть такой: 
<source lang="cpp">template<typename Iter>
std::list<typename Iter::value_type> mergeSort(Iter left, Iter right);</source> 
Исходные данные функция модифицировать не должна, в возвращаемом списке должны быть отсортированные элементы.

Затем необходимо добиться, чтоб можно было сортировать по указателям: 
<source lang="cpp">int* array = new int[SIZE];
mergeSort(array, array + SIZE);</source>

''Рекомендации'': для merge можно воспользоваться <code>std::list::merge</code> 
для получения типа, на который указывает указатель, можно воспользоваться <code>std::iterator_traits</code>

== Лабораторная работа №4 iterator ==
Написать шаблонный класс <code>slist</code> односвязный список. 
Реализовать для него <code>forward</code> итератор.

== Лабораторная работа №5 functor ==
Реализовать алгоритм
<source lang="cpp">
template<typename InIter, typename OutIter, typename Pred>
OutIter filter(InIter begin, InIter end, OutIter out, Pred pred);
</source>
который читает элементы и, если <code>pred(val)</code> возвращает <code>true</code>, то записывает элемент в <code>out</code>.

Реализовать собственный функтор, который принимает <code>std::set<char></code> и <code>char</code> и проверят наличие входного символа в сете.
С помощью алгоритма <code>filter</code> и вашего функтора отфильровать строку.

== Лабораторная работа №6 mem_fun ==
Реализовать аналог <code>std::mem_fun</code>, убедиться, что аналог работает на коде:
<source lang="cpp">
std::vector<char> v;
std::set<int> s;
mem_fun(&std::vector<char>::push_back)(v, 'd');
mem_fun(&std::set<int>::count)(s, 3);
</source>

== Лабораторная работа №7 заполнитель мапы ==
Реализовать заполнитель мапы
<source lang="cpp">
std::map<float, int> m(mapper(1.0, 2)(2, 2)(4, 2));
</source>

Динамическое распределение памяти

2011-03-27T19:29:14Z

Alexey.Gurevich: Новая страница: «== Виды памяти == Память, которую использует программа делится на три вида: 1. Статическая п…»

== Виды памяти ==

Память, которую использует программа делится на три вида:

1. Статическая память (static memory)
* хранит глобальные переменные и константы;
* размер определяется при компиляции.
2. Стек (stack)
* хранит локальные переменные, аргументы функций и промежуточные значения вычислений;
* размер определяется при запуске программы (обычно выделяется 4 Мб).
3. Куча (heap)
* динамически распределяемая память;
* ОС выделяет память по частям (по мере необходимости).

Динамически распределяемую память следует использовать в случае если мы заранее (на момент написания программы) не знаем сколько памяти нам понадобится (например, размер массива зависит от того, что введет пользователь во время работы программы) и при работе с большими объемами данных (например, массив из 1 000 000 элементов типа <code>int</code> не поместится на стеке).

== Работа с динамической памятью в С ==

Для работы с динамической памятью в языке С используются следующие функции: <code>malloc, calloc, free, realloc</code>.
Рассмотрим их подробнее.
<source lang="cpp">
void * malloc(size_t size);
</source>
В качестве входного параметра функция принимает размер памяти, которую требуется выделить. Возвращаемым значением является указатель на выделенный в куче участок памяти.
Для выделения памяти под 1 000 000 элементов типа <code>int</code> необходимо выполнить следующий код:
<source lang="cpp">
int * p = malloc(1000000 * sizeof(int));
</source>
В языке С++ потребуется небольшая модификация данной кода (из-за того, что в С++ нет неявного приведения указателей):
<source lang="cpp">
int * p = (int *) malloc(1000000 * sizeof(int));
</source>
Если ОС не смогла выделить память (например, памяти не хватило), то <code>malloc</code> возвращает 0.

После окончания работы с выделенной динамически памятью нужно освободить ее. Для этой цели используется функция <code>free</code>, которая возвращает память под управление ОС.
<source lang="cpp">
void free(void * ptr);
</source>
В качестве входного параметра в <code>free</code> нужно передать указатель, значение которого получено из функции <code>malloc</code>. Вызов <code>free</code> на указателях полученных не из <code>malloc</code> (например, <code>free(p+10)</code>) приведет к неопределенному поведению. Это связанно с тем, что при выделении памяти при помощи <code>malloc</code> в ячейки перед той, на которую указывает возвращаемый функцией указатель операционная система записывает служебную информацию (см. рис.). При вызове <code>free(p+10)</code> информация находящаяся перед ячейкой <code>(p+10)</code> будет трактоваться как служебная.

[[Файл:pointer_in_heap.png|400px]]

<source lang="cpp">
void * calloc(size_t nmemb, size_t size);
</source>
Функция работает аналогично <code>malloc</code>, но отличается синтаксисом (вместо размера выделяемой памяти нужно задать количество элементов и размер одного элемента) и тем, что выделенная память будет обнулена. Например, после выполнения
<source lang="cpp">
int * q = (int *) calloc(1000000, sizeof(int))
</source>
<code>q</code> будет указывать на начало массива из миллиона элементов типа <code>int</code> проинициализированных нулями.
<source lang="cpp">
void * realloc(void * ptr, size_t size);
</source>
Функция изменяет размер выделенной памяти (на которую указывает <code>ptr</code>, полученный из вызова <code>malloc</code>, <code>calloc</code> или <code>realloc</code>). Если размер указанный в параметре <code>size</code> больше, чем тот, который был выделен под указатель <code>ptr</code>, то проверяется, есть ли возможность выделить недостающие ячейки памяти подряд с уже выделенными. Если места недостаточно, то выделяется новый участок памяти размером <code>size</code> и данные по указателю <code>ptr</code> копируются в начало нового участка.

=== Какие бывают ошибки ===
1. Потеря памяти
<source lang="cpp">
int * p = (int *) malloc(100);
p = (int *) malloc(200); // потерян указатель на первые 100 <code>int</code>'ов, которые теперь нельзя отдать обратно ОС
</source>
2. Повторное освобождение выделенной памяти
<source lang="cpp">
free(p);
…
free(p); // неопределенное поведение
</source>

Правильно:
<source lang="cpp">
free(p);
p = 0;
…
free(p); // отработает без ошибок
</source>

== Работа с динамической памятью в С++ ==

В С++ есть свой механизм выделения и освобождения памяти — это функции <code>new</code> и <code>delete</code>.

Пример использования <code>new</code>:
<source lang="cpp">
int * p = new int[1000000]; // выделение памяти под 1000000 int`ов
</source>
Т.е. при использовании функции <code>new</code> не нужно приводить указатель и не нужно использовать <code>sizeof()</code>.
Освобождение выделенной при помощи <code>new</code> памяти осуществляется посредством следующего вызова:
<source lang="cpp">
delete [] p;
</source>
Если требуется выделить память под один элемент, то можно использовать
<source lang="cpp">
int * q = new int;
</source>
или
<source lang="cpp">
int * q = new int(10); // выделенный int проинциализируется значением 10
</source>
в этом случае удаление будет выглядеть следующим образом:
<source lang="cpp">
delete q;
</source>
'''Замечание:'''

Выделять динамически небольшие кусочки памяти (например, под один элемент простого типа данных) не целесообразно по двум причинам:
# При динамическом выделении памяти в ней помимо значения указанного типа будет храниться служебная информация ОС и С/С++. Таким образом потребуется гораздо больше памяти, чем при хранении необходимых данных на стеке.
# Если в памяти хранить большое количество маленьких кусочков, то она будет сильно фрагментирована и большой массив данных может не поместиться.

=== Многомерные массивы ===
<code>new</code> позволяет выделять только одномерные массивы, поэтому для работы с многомерными массивами необходимо воспринимать их как массив указателей на другие массивы.
Для примера рассмотрим задачу выделения динамической памяти под массив чисел размера <code>n</code> на <code>m</code>.

'''1ый способ'''

На первом шаге выделяется указатель на массив указателей, а на втором шаге, в цикле каждому указателю из массива выделяется массив чисел в памяти:
<source lang="cpp">
int ** a = new int*[n];
for (int i = 0; i != n; ++i)
a[i] = new int[m];
</source>
Однако, этот способ плох тем, что в нём требуется n+1 выделение памяти, а это достаточно дорогая по времени операция.

'''2ой способ'''

На первом шаге выделение массива указателей и массива чисел размером n на m. На втором шаге каждому указателю из массива ставится в соответствие строка в массиве чисел.
<source lang="cpp">
int ** a = new int*[n];
a[0] = new int[n*m];
for (int i = 1; i != n; ++i)
a[i] = a[0] + i*m;
</source>
В данном случае требуется всего 2 выделения памяти.
Для освобождения памяти потребуется выполнить:

'''1ый способ:'''
<source lang="cpp">
for (int i = 0; i != n; ++i)
delete [] a[i];
delete [] a;
</source>
'''2ой способ:'''
<source lang="cpp">
delete [] a[0];
delete [] a;
</source>
Таким образом, второй способ опять же требует гораздо меньше вызовов функции <code>delete []</code>, чем первый.

Файл:Pointer in heap.png

2011-03-27T19:05:33Z

Alexey.Gurevich:

Конспекты С++

2011-03-27T18:46:18Z

Alexey.Gurevich:

Конспекты по C++
* [[ Как происходит компиляция|Как происходит компиляция. Алексей Давыдов. 08.09.2010]]
* [[ Динамическое распределение памяти|Динамическое распределение памяти. Алексей Гуревич. 17.09.2010]]
* [[ Перегрузка операторов|Перегрузка операторов. Мария Фомкина. 12.11.2010]]
* [[ STL. Последовательные контейнеры|STL. Последовательные контейнеры. Мария Фомкина. 18.02.2011]]

The Shortest Path Problem

2011-03-16T23:11:54Z

Alexey.Gurevich:

* Студент: [[Участник:Alexey.Gurevich|Алексей Гуревич]]
* Руководитель: Валерий Лесин

Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации.

Положение на начало весеннего семестра:
* разработана графическая оболочка для тестирования алгоритмов,
* реализованы следующие алгоритмы:
'' - алгоритм Дейкстры, ''

'' - a-star.''
* а также их оптимизации на основе:
'' - использования двунаправленного поиска,''

'' - якорных точек (landmark) - ALT,''

'' - подсчета достижимости (reach) - REAL.''

Предполагаемые этапы:
* ускорение алгоритма подсчета достижимости (использование механизма shortcut, распараллеливание вычилений),
* исследование и реализация алгоритмов "contraction hierarchies" (начало апреля),
* исследование и реализация алгоритмов "transit node routing" (начало мая),
* <возможный этап> слияние с [[Shortest_Path_Service|проектом]] [[Участник:Eabatalov89|Евгения Баталова]] (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая)

Ожидаемый результат:
* Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог.

The Shortest Path Problem

2011-03-13T22:56:27Z

Alexey.Gurevich:

* Студент: Алексей Гуревич
* Руководитель: Валерий Лесин

Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации.

Положение на начало весеннего семестра:
* разработана графическая оболочка для тестирования алгоритмов,
* реализованы следующие алгоритмы:
'' - алгоритм Дейкстры, ''

'' - a-star.''
* а также их оптимизации на основе:
'' - использования двунаправленного поиска,''

'' - якорных точек (landmark) - ALT,''

'' - подсчета достижимости (reach) - REAL.''

Предполагаемые этапы:
* ускорение алгоритма подсчета достижимости (использование механизма shortcut, распараллеливание вычилений),
* исследование и реализация алгоритмов "contraction hierarchies" (начало апреля),
* исследование и реализация алгоритмов "transit node routing" (начало мая),
* <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая)

Ожидаемый результат:
* Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог.

The Shortest Path Problem

2011-03-13T22:47:37Z

Alexey.Gurevich: Новая страница: «* Студент: Алексей Гуревич * Руководитель: Валерий Лесин Описание: Целью проекта является …»

* Студент: Алексей Гуревич
* Руководитель: Валерий Лесин

Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации.

Положение на начало весеннего семестра:
* разработана графическая оболочка для тестирования алгоритмов,
* реализованы следующие алгоритмы:
<nowiki> - алгоритм Дейкстры, </nowiki>
<nowiki> - a-star. </nowiki>
* а также их оптимизации на основе:
<nowiki> - использования двунаправленного поиска,</nowiki>
<nowiki> - якорных точек (landmark) - ALT,</nowiki>
<nowiki> - подсчета достижимости (reach) - REAL.</nowiki>

Предполагаемые этапы:
* ускорение алгоритма подсчета достижимости (использование механизма shortcut, распараллеливание вычилений),
* исследование и реализация алгоритмов "contraction hierarchies" (начало апреля),
* исследование и реализация алгоритмов "transit node routing" (начало мая),
* <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая)

Ожидаемый результат:
* Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог.

Темы практик

2011-03-13T22:42:49Z

Alexey.Gurevich:

На этой странице собраны темы индивидуальных и командных проектов.

== Весна 2011 ==

* [[Genome assembler]] (Mariya Fomkina)

* [[Анализ изображений с целью поиска похожих лиц]] (Екатерина Полищук)

* [[The Shortest Path Problem]] (Алексей Гуревич)

== Пул свободных тем ==

* [[GeoToDo list]]

Поисковые системы

2011-03-13T17:03:20Z

Alexey.Gurevich:

Предлагается провести семинар по поисковым системам по базам данных (не про веб-поиск). Формат: много мини-докладов в один день и создание соответствующих страниц в wiki.
В качестве первого этапа предлагается составить список тем, которые можно было бы обсудить. Сейчас можно только предлагать темы, распределять их будем наследующем этапе.

* Механизм, архитектура поисковой системы с 3 потоками управления: обработка пользовательских запросов, исполнение запросов, индексирование новых данных.
* Алгоритм обратных индексов.
* Кластеризация в Data Mining
* напиши название темы здесь

Участник:Alexey.Gurevich

2011-03-12T23:24:45Z

Alexey.Gurevich: Новая страница: «Алексей Гуревич [mailto:alexeigurevich@gmail.com alexeigurevich@gmail.com] 200px»

Алексей Гуревич

[mailto:alexeigurevich@gmail.com alexeigurevich@gmail.com]

[[Файл:Gurevich.JPG|200px]]

Файл:Gurevich.JPG

2011-03-12T23:23:50Z

Alexey.Gurevich: