Список наиболее долго выполнявшихся функцийЭ

Func Func+Child Hit

Time % Time % Count Function

---------------------------------------------------------

322,606 72,6 322,606 72,6 806 std::basic_streambuf<char,struct std::char_traits<char> >::xsputn(char const *,int) (point.obj)

54,620 12,3 58,505 13,2 456 std::basic_ostream<char,struct std::char_traits<char> >::put(char) (lab1_3.obj)

28,430 6,4 28,442 6,4 831 std::ostreambuf_iterator<char,struct std::char_traits<char> >::operator=(char) (lab1_3.obj)

19,310 4,3 437,939 98,6 1 _main (lab1_3.obj)

6,130 1,4 19,799 4,5 276 std::num_put<char,class std::ostreambuf_iterator<char,struct std::char_traits<char> > >::_Fput(class std::ostreambuf_iterator<char,struct std::char_traits<char> >,class std::ios_base &,char,char const *,unsigned int,unsigned int) (lab1_3.obj)

3,883 0,9 3,883 0,9 1890 std::basic_ostream<char,struct std::char_traits<char> >::opfx(void) (lab1_3.obj)

2,996 0,7 22,795 5,1 276 std::num_put<char,class std::ostreambuf_iterator<char,struct std::char_traits<char> > >::do_put(class std::ostreambuf_iterator<char,struct std::char_traits<char> >,class std::ios_base &,char,double) (lab1_3.obj)

2,768 0,6 2,768 0,6 980 std::ios_base::getloc(void) (lab1_3.obj)

0,770 0,2 14,222 3,2 349 std::num_put<char,class std::ostreambuf_iterator<char,struct std::char_traits<char> > >::do_put(class std::ostreambuf_iterator<char,struct std::char_traits<char> >,class std::ios_base &,char,unsigned long) (lab1_3.obj)

0,446 0,1 0,446 0,1 276 std::num_put<char,class std::ostreambuf_iterator<char,struct std::char_traits<char> > >::_Rep(class std::ostreambuf_iterator<char,struct std::char_traits<char> >,char,unsigned int) (lab1_3.obj)

0,330 0,1 70,972 16,0 23 Point::Point(double,double) (point.obj)

0,260 0,1 0,152 0,0 86 std::basic_stringstream<char,struct std::char_traits<char>,class std::allocator<char> >::str(void) (point.obj)

0,234 0,1 3,516 0,8 6 Text::Text(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >) (text.obj)

0,211 0,0 0,211 0,0 355 std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >::_Copy(unsigned int) (lab1_3.obj)

0,201 0,0 0,000 0,0 58 std::operator+(char const *,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &) (line.obj)

0,170 0,0 0,165 0,0 12 Text::toString(void) (text.obj)

0,145 0,0 104,645 23,6 40 Point::~Point(void) (point.obj)

0,137 0,0 0,135 0,0 560 std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >::assign(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &,unsigned int,unsigned int) (lab1_3.obj)

0,136 0,0 17,416 3,9 2 [thunk]:TextInTriangle::moveBy`vtordisp{-4,0}' (double,double) (textintriangle.obj)

0,104 0,0 25,986 5,8 276 std::basic_ostream<char,struct std::char_traits<char> >::operator<<(double) (line.obj)

0,099 0,0 0,099 0,0 980 std::locale::id::operator unsigned int(void) (lab1_3.obj)

0,060 0,0 10,595 2,4 4 printShapeObjectStats(void) (lab1_3.obj)

0,031 0,0 6,536 1,5 3 [thunk]:Line::print`vtordisp{-4,0}' (class std::basic_ostream<char,struct std::char_traits<char> > &) (line.obj)

0,026 0,0 50,001 11,3 5 Line::Line(class Point *,class Point *) (line.obj)

0,023 0,0 22,042 5,0 2 Triangle::Triangle(void) (triangle.obj)

0,020 0,0 122,027 27,5 37 [thunk]:Point::`vector deleting destructor'`vtordisp{-4,0}' (unsigned int) (point.obj)

0,013 0,0 0,013 0,0 86 std::basic_stringbuf<char,struct std::char_traits<char>,class std::allocator<char> >::overflow(int) (point.obj)

0,012 0,0 21,523 4,8 3 Line::Line(void) (line.obj)

0,009 0,0 63,286 14,2 4 Triangle::Triangle(class Point *,class Point *,class Point *) (triangle.obj)

0,008 0,0 31,059 7,0 3 createRandomShape(void) (lab1_3.obj)

0,008 0,0 0,008 0,0 3 Point::operator=(class Point const &) (point.obj)

0,008 0,0 0,045 0,0 3 std::num_put<char,class std::ostreambuf_iterator<char,struct std::char_traits<char> > >::do_put(class std::ostreambuf_iterator<char,struct std::char_traits<char> >,class std::ios_base &,char,long) (lab1_3.obj)

0,006 0,0 0,000 0,0 1 std::num_put<char,class std::ostreambuf_iterator<char,struct std::char_traits<char> > >::num_put<char,class std::ostreambuf_iterator<char,struct std::char_traits<char> > >(unsigned int) (lab1_3.obj)

0,006 0,0 3,187 0,7 6 Text::~Text(void) (text.obj)

Разработка шаблон контейнера и шаблон итератора.

Контейнер – хэш на базе массива.

Хэш или хэш-таблица – это ассоциативный массив, т.е. контейнер в котором элементы доступны по индексам (ключам), имеющим произвольный тип. Для использования хэш-таблицы, необходимо предоставить функцию, которая должна возвращать положительное целое число (hashcode), по которому определяется позиция элемента в хэш таблице. Для этого предоставляется интерфейсHashable, в котором объявлена чистая виртуальная функцияhashCode(). Ключ хэш-таблицы должен иметь тип, реализующий интерфейсHashable, помимо этого в класса ключа должны быть переопределены операторы сравнения объектовoperator== и присваниванияoperator=.

В качестве элементов массива используются структуры, хранящие пару <ключ – значение> и флаг isNull, говорящий о том, пуст ли данный элемент или нет (в связи с тем, что структура не динамическая и надо знать, какие элементы используются, а какие - нет).

При создании хэш имеет фиксированный заданный размер, но если при добавлении элемента места в хэше не оказалось, то происходит рехеширование – увеличение размера хэша (создает массив в 2 раза большего размера, элементы хэша копируются туда, старый массив удаляется).

При добавлении элемента возвращается пара <итератор элемента, флаг добавления элемента в хэш>, если флаг установлен в false, то добавление не было осуществлено. Если происходит попытка добавить элемент с уже существующим ключем, то объект этот не добавляется.

При удалении возвращается пара <пара<ключ-значение> удаленного элемента и флаг удаления элемента>, если флаг установлен в false, то добавление удаление не было осуществлено. Иначе удаление прошло успешно и первым элементом возвращаемой пары будет пара <ключ-значение> удаленного элемента, таким образом можно освободить ресурсы занимаемые этими объектами.

Поиск позиции объекта с заданным ключем в хэше производится через хэш функцию объекта, вычисляется hashCodeи берется по модулюmaxsize(максимальный “текущий” размер хэша), т.о. определяется индекс в массиве - (object.hashCode()) %maxsize.

Для разрешения коллизий используется метод линейных проб (linearprobing). Идея состоит в том, что сталкиваясь с коллизией при включении записи, мы последовательно (циклически, с переходом через конец на начало) просматриваем массив в поиске первого незанятого элемента.

Если такой элемент обнаруживается, в него и заносится включаемая запись. Если все элементы массива заняты, то это означает, что хэш-таблица переполнена и требуется расширение массива – рехэш. Для этого использунется функция (object.hashCode() + i) %maxsize

Шаблон Хэш (Hash)

Члены-данные

- максимальный размер

int maxSize;

- текущий размер

intsize;

- массив объектов типа HashElem

HashElem<K,V>*t;

Члены-функции

Внутренние:

- вычисление хэш-функции для определения позиции элемента хэша

(вычисляется как object.hashCode()%hashMaxSize)

int h(const K& key);

- функция используется в связке с предыдущей

(вычисляется как (object.hashCode()+1)%hashMaxSize)

int r(const K& key, int i);

- вычисление позиции элемента с ключем Kв хэше

int getPos(const K& key);

- рехэшинг (увеличение размера хэша в 2 раза)

int rehash();

Интерфейсные:

- конструктор (параметр – количество элементов в хэше, значение по умолчанию = 8). Количество элементов увеличивается при необходимости.

Hash(int n = 8);

- деструктор

virtual ~ Hash();

- добавление в хэш (параметр key– ключ, параметрvalue- значение). Возвращает объект типаpair– первый элемент – итератор добавленного элемента или конца хэша, если элемент добавлен не был, второй параметр – булевская переменная, принимающая значениеtrue, если элемент был добавлен в массив.

pair<iterator, bool> put(K key, V value);

- удаление элемента с заданным ключем из хэша (параметр key- ключ). Возвращает пару: первый элемент – пара<ключ-значение> удаленного элемента, второй параметр - булевская переменная, принимающая значениеtrue, если элемент был удален из массива.

pair<pair<K, V>, bool> remove(K key);

- итератор начала хэша

iterator begin()

- итератор конца хэша

iterator end ()

- поиск элемента с заданным ключем в хэше (параметр key- ключ). Возвращает итератор элемента с заданным ключем, если тот был найден, иначе итератор конца хэша.

iterator find(const K& key)

- проверка хэша на пустоту

bool empty()

- получение текущего размера хэша

int getSize()

- получение максимального размера хэша

int getMaxSize()

Шаблон элемента хэша (HashElem)

Члены-данные

- ключ

Kkey;

- значение

Vvalue;

- булевская переменная, принимающая значение true, если элемент хэша “пустой”

bool null;

Члены-функции

Внутренние:

Нет

Интерфейсные:

- дефолтный конструктор. Создает объект и делает его “пустым”

HashElem();

- конструктор (параметры – ключ и значение). Делает объект “непустым”

HashElem(K k, V v):

- конструктор. Создает объект и делает его “непустым”

HashElem(intn= 8);

- деструктор. Разрушает объект и делает его “пустым”

virtual~HashElem();

- селекторы ключа и значения. Возвращают ссылки на объекты

K& getKey()

V& getValue()

- проверка на пустоту

bool isNull()

- установка объекта в состояние “пустой”

voidsetNull()

Шаблон итератора (Hash::iterator)

Члены-данные

- указатель на хэш с которым работает итератор (задается при создании автоматически)

Hash<K,V>*hash;

- текущий индекс в хэше на который указывает итератор

int index;

Члены-функции

Внутренние:

- поиск первого элемента хэша

intfindFirstElemPos()

- поиск следующего элемента хэша после элемента в заданной позиции

int findNextElemPos(int pos)

Интерфейсные:

- конструктор (параметр – указатель на хэш). Индекс устанавливается в позицию первого элемента.

iterator(Hash<K, V>* h)

- конструктор (параметр – указатель на хэш, поз – позиция итератора).

iterator(Hash<K, V>* h, int pos)

- перегруженный оператор *. Возвращает пару <ключ-значение> элемента на который указывает итератор

pair<K,V>operator*()

- перегруженный оператор ++ (префикс). Возвращает пару <ключ-значение> элемента на который указывает итератор

pair<K, V> operator++()

- перегруженный оператор ++ (постфикс). Возвращает пару <ключ-значение> элемента на который указывает итератор, после этого итератор инкрементируется

pair<K, V> operator++(int)

- перегруженный оператор == (для сравнения итераторов)

bool operator==(const iterator& it) const

- перегруженный оператор != (для сравнения итераторов)

bool operator!=(const iterator& it) const

- дружественный перегруженный оператор << (для вывода элемента, на который указывает итератор, в поток)

friend ostream& operator<<(ostream& os, const iterator& it)

Обработка исключений

Класс HashExceptionиспользуется для возбуждения исключения в хэше.

В операторах итератора operator*(), operator++() иoperator++(int) предусмотрена обработка исключений. Если индекс, на который указывает итератор выходит за пределы хэша, то возникает исключение “outofbounds”, это исключение ловится и возвращается последний элемент хэша. При рехэше может возникнуть нехватка памяти, это исключение обрабатывается и элемент не добавляется в массив.