Создание сложных динамических структур данных

os << "[" << *obj. item << "]" << std::endl;

return os;

}

template <class T> void * TStackItem<T>::operator new (size_t size) {

return stackitem_allocator. allocate();

}

template <class T> void TStackItem<T>::operator delete(void *p) {

stackitem_allocator. deallocate(p);

}

#include "Triangle. h"

template class TStackItem<Triangle>;

template std::ostream& operator<<(std::ostream& os, const TStackItem<Triangle>& obj);

Листинг файла Triangle. h

#ifndef TRIANGLE_H

#define TRIANGLE_H

#include <cstdlib>

#include <iostream>

class Triangle {

public:

Triangle();

Triangle(size_t i, size_t j, size_t k);

Triangle(const Triangle& orig);

friend std::ostream& operator<<(std::ostream& os, const Triangle& obj);

Triangle& operator=(const Triangle& right);

virtual ~Triangle();

private:

size_t side_a;

size_t side_b;

size_t side_c;

};

#endif /* TRIANGLE_H */

Листинг файла Triangle. cpp

#include "Triangle. h"

#include <iostream>

Triangle::Triangle() : Triangle(0, 0, 0) {

std::cout << "Triangle created: default" << std::endl;

}

Triangle::Triangle(size_t i, size_t j, size_t k) : side_a(i), side_b(j), side_c(k) {

std::cout << "Triangle created: " << side_a << ", " << side_b << ", " << side_c << std::endl;

}

Triangle::Triangle(const Triangle& orig) {

std::cout << "Triangle copy created" << std::endl;

side_a = orig. side_a;

side_b = orig. side_b;

side_c = orig. side_c;

}

Triangle& Triangle::operator=(const Triangle& right) {

if (this == &right) return *this;

std::cout << "Triangle copied" << std::endl;

side_a = right. side_a;

side_b = right. side_b;

side_c = right. side_c;

return *this;

}

Triangle::~Triangle() {

std::cout << "Triangle deleted" << std::endl;

}

std::ostream& operator<<(std::ostream& os, const Triangle& obj) {

os << "a=" << obj. side_a << ", b=" << obj. side_b << ", c=" << obj. side_c;

return os;

}

Листинг файла main. cpp

#include <cstdlib>

#include <iostream>

#include <memory>

#include "Triangle. h"

#include "TStackItem. h"

#include "TStack. h"

#include "TAllocationBlock. h"

void TestStack()

{

TStack<Triangle> stack;

stack. push(std::shared_ptr<Triangle>(new Triangle(1,1,1)));

stack. push(std::shared_ptr<Triangle>(new Triangle(2,2,2)));

stack. push(std::shared_ptr<Triangle>(new Triangle(3,3,3)));

stack. push(std::shared_ptr<Triangle>(new Triangle(3,3,3)));

for(auto i : stack) std::cout << *i << std::endl;

std::shared_ptr<Triangle> t;

while(!stack. empty()) std::cout << *stack. pop() << std::endl;

}

void TestAllocationBlock()

{

TAllocationBlock allocator(sizeof(int),10);

int *a1=nullptr;

int *a2=nullptr;

int *a3=nullptr;

int *a4=nullptr;

int *a5=nullptr;

a1 = (int*)allocator. allocate();*a1 =1; std::cout << "a1 pointer value:" << *a1 << std::endl;

a2 = (int*)allocator. allocate();*a2 =2; std::cout << "a2 pointer value:" << *a2 << std::endl;

a3 = (int*)allocator. allocate();*a3 =3; std::cout << "a3 pointer value:" << *a3 << std::endl;

allocator. deallocate(a1);

allocator. deallocate(a3);

a4 = (int*)allocator. allocate();*a4 =4; std::cout << "a4 pointer value:" << *a4 << std::endl;

a5 = (int*)allocator. allocate();*a5 =5; std::cout << "a5 pointer value:" << *a5 << std::endl;

std::cout << "a1 pointer value:" << *a1 << std::endl;

std::cout << "a2 pointer value:" << *a2 << std::endl;

std::cout << "a3 pointer value:" << *a3 << std::endl;

allocator. deallocate(a2);

allocator. deallocate(a4);

allocator. deallocate(a5);

}

// templates stack on shared pointer with iterator and allocator on array

int main(int argc, char** argv) {

TestAllocationBlock();

TestStack();

return 0;

}

Лабораторная работа №7

Цель работы

Целью лабораторной работы является:

·  Создание сложных динамических структур данных.

·  Закрепление принципа OCP.

Задание

Необходимо реализовать динамическую структуру данных – «Хранилище объектов» и алгоритм работы с ней. «Хранилище объектов» представляет собой контейнер, одного из следующих видов (Контейнер 1-го уровня):

1. Массив

2. Связанный список

3. Бинарное — Дерево.

4. N-Дерево (с ограничением не больше 4 элементов на одном уровне).

5. Очередь

6. Стек

Каждым элементом контейнера, в свою, является динамической структурой данных одного из следующих видов (Контейнер 2-го уровня):

1. Массив

2. Связанный список

3. Бинарное — Дерево

4. N-Дерево (с ограничением не больше 4 элементов на одном уровне).

5. Очередь

6. Стек

Таким образом у нас получается контейнер в контейнере. Т. е. для варианта (1,2) это будет массив, каждый из элементов которого – связанный список. А для варианта (5,3) – это очередь из бинарных деревьев.

Элементом второго контейнера является объект-фигура, определенная вариантом задания.

При этом должно выполняться правило, что количество объектов в контейнере второго уровня не больше 5. Т. е. если нужно хранить больше 5 объектов, то создается еще один контейнер второго уровня. Например, для варианта (1,2) добавление объектов будет выглядеть следующим образом:

1. Вначале массив пустой.

2. Добавляем Объект1: В массиве по индексу 0 создается элемент с типом список, в список

добавляется Объект 1.

3. Добавляем Объект2: Объект добавляется в список, находящийся в массиве по индекс 0.

4. Добавляем Объект3: Объект добавляется в список, находящийся в массиве по индекс 0.

5. Добавляем Объект4: Объект добавляется в список, находящийся в массиве по индекс 0.

6. Добавляем Объект5: Объект добавляется в список, находящийся в массиве по индекс 0.

7. Добавляем Объект6: В массиве по индексу 1 создается элемент с типом список, в список добавляется Объект 6.

Объекты в контейнерах второго уровня должны быть отсортированы по возрастанию Имя объекта (в том числе и для деревьев).

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

Нельзя использовать:

·  Стандартные контейнеры std.

Программа должна позволять:

·  Вводить произвольное количество фигур и добавлять их в контейнер.

·  Распечатывать содержимое контейнера (1-го и 2-го уровня).

·  Удалять фигуры из контейнера по критериям:

o  По типу (например, все квадраты).

o  По площади (например, все объекты с площадью меньше чем заданная).

Полезный пример

Данный пример демонстрирует основные возможности языка C++, которые понадобится применить в данной лабораторной работе. Пример не является решением варианта лабораторной работы.

Листинг файла IRemoveCriteria. h

#ifndef IREMOVECRITERIA_H

#define IREMOVECRITERIA_H

template <class T> class IRemoveCriteria {

public:

virtual bool isIt(T* value) = 0;

private:

};

Листинг файла IRemoveCriteriaAll. h

#ifndef IREMOVECRITERIAALL_H

#define IREMOVECRITERIAALL_H

#include "IRemoveCriteria. h"

template <class T> class IRemoveCriteriaAll : public IRemoveCriteria<T>{

public:

IRemoveCriteriaAll() {};

bool isIt(T* value) override{

return true;

}

private:

};

#endif

Листинг файла IRemoveCriteriaByValue. h

#ifndef IREMOVECRITERIABYVALUE_H

#define IREMOVECRITERIABYVALUE_H

#include "IRemoveCriteria. h"

template <class T> class IRemoveCriteriaByValue : public IRemoveCriteria<T>{

public:

IRemoveCriteriaByValue(T&& value) : _value(value) {};

bool isIt(T* value) override{

return _value==*value;

}

private:

T _value;

};

#endif

Листинг файла TAllocationBlock. h

#ifndef TALLOCATIONBLOCK_H

#define TALLOCATIONBLOCK_H

#include <cstdlib>

class TAllocationBlock {

public:

TAllocationBlock(size_t size, size_t count);

void *allocate();

void deallocate(void *pointer);

bool has_free_blocks();

virtual ~TAllocationBlock();

private:

size_t _size;

size_t _count;

char *_used_blocks;

void **_free_blocks;

size_t _free_count;

};

#endif

Листинг файла TIterator. h

#ifndef TITERATOR_H

#define TITERATOR_H

#include <memory>

#include <iostream>

template <class node, class T>

class TIterator

{

public:

TIterator(std::shared_ptr<node> n) {

node_ptr = n;

}

std::shared_ptr<T> operator * (){

return node_ptr->GetValue();

}

std::shared_ptr<T> operator -> (){

return node_ptr->GetValue();

}

void operator ++ (){

node_ptr = node_ptr->GetNext();

}

TIterator operator ++ (int){

TIterator iter(*this);

++(*this);

return iter;

}

bool operator == (TIterator const& i){

return node_ptr == i. node_ptr;

}

bool operator!= (TIterator const& i){

return!(*this == i);

}

private:

std::shared_ptr<node> node_ptr;

};

#endif

Листинг файла TList. h

#ifndef TLIST_H

#define TLIST_H

#include <memory>

#include "TListItem. h"

#include "TIterator. h"

#include "IRemoveCriteria. h"

template <class T, class TT> class TList {

public:

TList();

void InsertSubitem(TT* value);

void RemoveSubitem(IRemoveCriteria<TT> * criteria);

void PushBack(T* value);

bool Remove(T* value);

size_t Size();

TIterator<TListItem<T>, T> begin() const;

TIterator<TListItem<T>, T> end() const;

template <class A, class AA> friend std::ostream& operator<<(std::ostream& os, const TList<A, AA>& list);

virtual ~TList();

private:

std::shared_ptr<TListItem<T>> head;

};

#endif

Листинг файла TListItem. h

#ifndef TLISTITEM_H

#define TLISTITEM_H

#include <memory>

template <class T> class TListItem {

public:

TListItem(T* value);

std::shared_ptr<T> GetValue();

std::shared_ptr<TListItem<T>> GetNext();

void SetNext(std::shared_ptr<TListItem<T>> next);

void PushBack(std::shared_ptr<TListItem<T>> next);

virtual ~TListItem();

private:

std::shared_ptr<T> _value;

std::shared_ptr<TListItem> _next;

};

#endif

Листинг файла TStack. h

#ifndef TSTACK_H

#define TSTACK_H

#include "TIterator. h"

#include "TStackItem. h"

#include <memory>

template <class T> class TStack {

public:

TStack();

void push(T* item);

bool empty();

size_t size();

TIterator<TStackItem<T>,T> begin();

TIterator<TStackItem<T>,T> end();

std::shared_ptr<T> pop();

template <class A> friend std::ostream& operator<<(std::ostream& os, const TStack<A>& stack);

virtual ~TStack();

private:

std::shared_ptr<TStackItem<T>> head;

};

#endif

Листинг файла TStackItem. h

#ifndef TSTACKITEM_H

#define TSTACKITEM_H

#include <memory>

#include "TAllocationBlock. h"

template<class T> class TStackItem {

public:

TStackItem(T *item);

template<class A> friend std::ostream& operator<<(std::ostream& os, const TStackItem<A>& obj);

std::shared_ptr<TStackItem<T>> SetNext(std::shared_ptr<TStackItem> &next);

std::shared_ptr<TStackItem<T>> GetNext();

std::shared_ptr<T> GetValue() const;

void * operator new (size_t size);

void operator delete(void *p);

virtual ~TStackItem();

private:

std::shared_ptr<T> item;

std::shared_ptr<TStackItem<T>> next;

static TAllocationBlock stackitem_allocator;

};

#endif

Листинг файла Triangle. h

#ifndef TRIANGLE_H

#define TRIANGLE_H

#include <cstdlib>

#include <iostream>

class Triangle {

public:

Triangle();

Triangle(size_t i, size_t j, size_t k);

Triangle(const Triangle& orig);

friend std::ostream& operator<<(std::ostream& os, const Triangle& obj);

bool operator==(const Triangle& other);

Triangle& operator=(const Triangle& right);

virtual ~Triangle();

private:

size_t side_a;

size_t side_b;

size_t side_c;

};

#endif

Листинг TAllocationBlock. cpp

#include "TAllocationBlock. h"

#include <iostream>

TAllocationBlock::TAllocationBlock(size_t size, size_t count): _size(size),_count(count) {

_used_blocks = (char*)malloc(_size*_count);

_free_blocks = (void**)malloc(sizeof(void*)*_count);

for(size_t i=0;i<_count;i++) _free_blocks[i] = _used_blocks+i*_size;

_free_count = _count;

std::cout << "TAllocationBlock: Memory init" << std::endl;

}

void *TAllocationBlock::allocate() {

void *result = nullptr;

if(_free_count>0)

{

result = _free_blocks[_free_count-1];

_free_count—;

std::cout << "TAllocationBlock: Allocate " << (_count-_free_count) << " of " << _count << std::endl;

} else

{

std::cout << "TAllocationBlock: No memory exception :-)" << std::endl;

}

return result;

}

void TAllocationBlock::deallocate(void *pointer) {

std::cout << "TAllocationBlock: Deallocate block "<< std::endl;

_free_blocks[_free_count] = pointer;

_free_count ++;

}

bool TAllocationBlock::has_free_blocks() {

return _free_count>0;

}

TAllocationBlock::~TAllocationBlock() {

if(_free_count<_count) std::cout << "TAllocationBlock: Memory leak?" << std::endl;

else std::cout << "TAllocationBlock: Memory freed" << std::endl;

delete _free_blocks;

delete _used_blocks;

}

Листинг TList. cpp

#include "TList. h"

template <class T, class TT> TList<T, TT>::TList() {

head = nullptr;

}

template <class T, class TT> void TList<T, TT>::RemoveSubitem(IRemoveCriteria<TT> * criteria) {

std::cout << "———————->" << std::endl;

for (auto i : * this) {

T copy;

while (!i->empty()) {

std::shared_ptr<TT> value = i->pop();

if (criteria->isIt(&*value))

std::cout << "List: Delete element " << *value << std::endl;

else {

copy. push(new TT(*value));

}

}

while (!copy. empty()) i->push(new TT(*copy. pop()));

}

std::cout << "!!!!!!!!!!!!!!!!!!!!!!!" << std::endl;

}

template <class T, class TT> void TList<T, TT>::InsertSubitem(TT* value) {

bool inserted = false;

if (head!= nullptr) {

for (auto i : * this) {

if (i->size() < 5) {

i->push(value);

std::cout << "List: Add Element in list:" << i->size() << std::endl;

inserted = true;

}

}

}

if (!inserted) {

std::cout << "List: New list element created" << std::endl;

T* t_value = new T();

t_value->push(value);

PushBack(t_value);

}

}

template <class T, class TT> void TList<T, TT>::PushBack(T* value) {

std::shared_ptr<TListItem < T >> value_item(new TListItem<T>(value));

std::cout << "List: Added to list" << std::endl;

if (head!= nullptr) {

head->PushBack(value_item);

} else {

head = value_item;

}

}

template <class T, class TT> bool TList<T, TT>::Remove(T* value) {

std::shared_ptr<TListItem < T>> item = head;

std::shared_ptr<TListItem < T>> prev_item = nullptr;

bool result = false;

while ((item!= nullptr)&&(!result)) {

if (item->GetValue().get() == value) {

if (prev_item!= nullptr) prev_item->SetNext(item->GetNext());

else head = item->GetNext();

result = true;

} else {

prev_item = item;

item = item->GetNext();

}

}

return result;

}

template <class T, class TT> size_t TList<T, TT>::Size() {

size_t result = 0;

for (auto a : * this) result++;

return result;

}

template <class T, class TT> TIterator<TListItem<T>, T> TList<T, TT>::begin() const{

return TIterator<TListItem<T>, T>(head);

}

template <class T, class TT> TIterator<TListItem<T>, T> TList<T, TT>::end() const{

return TIterator<TListItem<T>, T>(nullptr);

}

template <class T, class TT> TList<T, TT>::~TList() {

std::cout << "List: deleted" << std::endl;

}

template <class A, class AA> std::ostream& operator<<(std::ostream& os, const TList<A, AA>& list) {

std::cout << "List:" << std::endl;

for(auto i:list) std::cout << *i << std::endl;

return os;

}

#include "TStack. h"

#include "Triangle. h"

template class TList<TStack<Triangle>, Triangle>;

template std::ostream& operator<<(std::ostream &os, const TList<TStack<Triangle>,Triangle> &list);

Листинг TListItem. cpp

#include "TListItem. h"

template <class T> TListItem<T>::TListItem(T* value) {

_value = std::shared_ptr<T> (value);

_next = nullptr;

}

template <class T> std::shared_ptr<T> TListItem<T>::GetValue() {

return _value;

}

template <class T> std::shared_ptr<TListItem<T>> TListItem<T>::GetNext() {

return _next;

}

template <class T> void TListItem<T>::SetNext(std::shared_ptr<TListItem> next) {

_next = next;

}

template <class T> void TListItem<T>::PushBack(std::shared_ptr<TListItem> next) {

if (_next!= nullptr) {

_next->PushBack(next);

} else {

_next = next;

}

}

template <class T> TListItem<T>::~TListItem() {

}

#include "TStack. h"

#include "Triangle. h"

template class TListItem<TStack<Triangle>>;

template class TListItem<Triangle>;

Листинг TStack. cpp

#include "TStack. h"

template <class T> TStack<T>::TStack() : head(nullptr) {

std::cout << "Stack created" << std::endl;

}

template <class T> std::ostream& operator<<(std::ostream& os, const TStack<T>& stack) {

std::shared_ptr<TStackItem<T>> item = stack. head;

while(item!=nullptr)

{

os << *item;

item = item->GetNext();

}

return os;

}

template <class T> void TStack<T>::push(T *item) {

std::shared_ptr<TStackItem<T>> other(new TStackItem<T>(item));

other->SetNext(head);

head = other;

}

template <class T> bool TStack<T>::empty() {

return head == nullptr;

}

template <class T> std::shared_ptr<T> TStack<T>::pop() {

std::shared_ptr<T> result;

if (head!= nullptr) {

result = head->GetValue();

head = head->GetNext();

}

return result;

}

template <class T> size_t TStack<T>::size(){

int result = 0;

for(auto i : *this) result++;

return result;

}

template <class T> TIterator<TStackItem<T>,T> TStack<T>::begin()

{

return TIterator<TStackItem<T>,T>(head);

}

template <class T> TIterator<TStackItem<T>,T> TStack<T>::end()

{

return TIterator<TStackItem<T>,T>(nullptr);

}

template <class T> TStack<T>::~TStack() {

std::cout << "Stack deleted" << std::endl;

}

#include "Triangle. h"

template class TStack<Triangle>;

template std::ostream& operator<<(std::ostream& os, const TStack<Triangle>& stack);

Листинг TStackItem. cpp

#include "TStackItem. h"

#include <iostream>

template <class T> TStackItem<T>::TStackItem(T* item) {

this->item = std::shared_ptr<T>(item);

this->next = nullptr;

std::cout << "Stack item: created" << std::endl;

}

template <class T> TAllocationBlock TStackItem<T>::stackitem_allocator(sizeof(TStackItem<T>),100);

template <class T> std::shared_ptr<TStackItem<T>> TStackItem<T>::SetNext(std::shared_ptr<TStackItem<T>> &next) {

std::shared_ptr<TStackItem < T>> old = this->next;

this->next = next;

return old;

}

template <class T> std::shared_ptr<T> TStackItem<T>::GetValue() const {

return this->item;

}

template <class T> std::shared_ptr<TStackItem<T>> TStackItem<T>::GetNext() {

return this->next;

}

template <class T> TStackItem<T>::~TStackItem() {

std::cout << "Stack item: deleted" << std::endl;

}

template <class A> std::ostream& operator<<(std::ostream& os, const TStackItem<A>& obj) {

os << "[" << *obj. item << "]" << std::endl;

return os;

}

template <class T> void * TStackItem<T>::operator new (size_t size) {

return stackitem_allocator. allocate();

}

template <class T> void TStackItem<T>::operator delete(void *p) {

stackitem_allocator. deallocate(p);

}

#include "Triangle. h"

template class TStackItem<Triangle>;

template std::ostream& operator<<(std::ostream& os, const TStackItem<Triangle>& obj);

Листинг Triangle. cpp

#include "Triangle. h"

#include <iostream>

Triangle::Triangle() : Triangle(0, 0, 0) {

std::cout << "Triangle created: default" << std::endl;

}

Triangle::Triangle(size_t i, size_t j, size_t k) : side_a(i), side_b(j), side_c(k) {

std::cout << "Triangle created: " << side_a << ", " << side_b << ", " << side_c << std::endl;

}

Triangle::Triangle(const Triangle& orig) {

std::cout << "Triangle copy created" << std::endl;

side_a = orig. side_a;

side_b = orig. side_b;

side_c = orig. side_c;

}

bool Triangle::operator==(const Triangle& other){

return (side_a==other. side_a)&&(side_b==other. side_b)&&(side_c==other. side_c);

}

Triangle& Triangle::operator=(const Triangle& right) {

if (this == &right) return *this;

std::cout << "Triangle copied" << std::endl;

side_a = right. side_a;

side_b = right. side_b;

side_c = right. side_c;

return *this;

}

Triangle::~Triangle() {

std::cout << "Triangle deleted" << std::endl;

}

std::ostream& operator<<(std::ostream& os, const Triangle& obj) {

os << "a=" << obj. side_a << ", b=" << obj. side_b << ", c=" << obj. side_c;

return os;

}

Листинг main. cpp

#include <cstdlib>

#include <iostream>

#include <memory>

#include "Triangle. h"

#include "TStack. h"

#include "TList. h"

#include "IRemoveCriteriaByValue. h"

#include "IRemoveCriteriaAll. h"

int main(int argc, char** argv) {

TList<TStack<Triangle>,Triangle> list;

list. InsertSubitem(new Triangle(1,1,1));

list. InsertSubitem(new Triangle(2,1,1));

list. InsertSubitem(new Triangle(3,1,1));

list. InsertSubitem(new Triangle(4,1,1));

list. InsertSubitem(new Triangle(5,1,1));

list. InsertSubitem(new Triangle(6,1,1));

list. InsertSubitem(new Triangle(7,1,1));

std::cout << list << std::endl;

IRemoveCriteriaByValue<Triangle> criteria(Triangle(4,1,1));

IRemoveCriteriaAll<Triangle> criteriaAll;

list. RemoveSubitem(&criteria);

std::cout << list << std::endl;

return 0;

}

Лабораторная работа №8

Цель работы

Целью лабораторной работы является:

·  Знакомство с параллельным программированием в C++.

Задание

Используя структуры данных, разработанные для лабораторной работы №6 (контейнер первого уровня и классы-фигуры) разработать алгоритм быстрой сортировки для класса-контейнера.

Необходимо разработать два вида алгоритма:

·  Обычный, без параллельных вызовов.

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

Для создания потоков использовать механизмы:

·  future

·  packaged_task/async

Для обеспечения потоко-безопасности структур данных использовать:

·  mutex

·  lock_guard

Нельзя использовать:

·  Стандартные контейнеры std.

Программа должна позволять:

·  Вводить произвольное количество фигур и добавлять их в контейнер.

·  Распечатывать содержимое контейнера.

·  Удалять фигуры из контейнера.

·  Проводить сортировку контейнера

Полезный пример

Данный пример демонстрирует основные возможности языка C++, которые понадобится применить в данной лабораторной работе. Пример не является решением варианта лабораторной работы.

Листинг файла TIterator. h

#ifndef TITERATOR_H

#define TITERATOR_H

#include <memory>

#include <iostream>

template <class node, class T>

class TIterator

{

public:

TIterator(std::shared_ptr<node> n) {

node_ptr = n;

}

std::shared_ptr<T> operator * (){

return node_ptr->GetValue();

}

std::shared_ptr<T> operator -> (){

return node_ptr->GetValue();

}

void operator ++ (){

node_ptr = node_ptr->GetNext();

}

TIterator operator ++ (int){

TIterator iter(*this);

++(*this);

return iter;

}

bool operator == (TIterator const& i){

return node_ptr == i. node_ptr;

}

bool operator!= (TIterator const& i){

return!(*this == i);

}

private:

std::shared_ptr<node> node_ptr;

};

#endif /* TITERATOR_H */

Листинг файла TStack. h

#ifndef TSTACK_H

#define TSTACK_H

#include "TIterator. h"

#include "TStackItem. h"

#include <memory>

#include <future>

#include <mutex>

template <class T> class TStack {

public:

TStack();

void push(T* item);

void push(std::shared_ptr<T> item);

bool empty();

size_t size();

TIterator<TStackItem<T>,T> begin();

TIterator<TStackItem<T>,T> end();

std::shared_ptr<T> operator[] (size_t i);

void sort();

void sort_parallel();

std::shared_ptr<T> pop();

std::shared_ptr<T> pop_last();

template <class A> friend std::ostream& operator<<(std::ostream& os, const TStack<A>& stack);

virtual ~TStack();

private:

std::future<void> sort_in_background();

std::shared_ptr<TStackItem<T>> head;

};

#endif

Листинг файла TStackItem. h

#ifndef TSTACKITEM_H

#define TSTACKITEM_H

#include <memory>

template<class T> class TStackItem {

public:

TStackItem(T *item);

TStackItem(std::shared_ptr<T> item);

template<class A> friend std::ostream& operator<<(std::ostream& os, const TStackItem<A>& obj);

std::shared_ptr<TStackItem<T>> SetNext(std::shared_ptr<TStackItem> next);

std::shared_ptr<TStackItem<T>> GetNext();

std::shared_ptr<T> GetValue() const;

virtual ~TStackItem();

private:

std::shared_ptr<T> item;

std::shared_ptr<TStackItem<T>> next;

};

#endif

Листинг файла Triangle. h

#ifndef TRIANGLE_H

#define TRIANGLE_H

#include <cstdlib>

#include <iostream>

class Triangle {

public:

Triangle();

Triangle(size_t i, size_t j, size_t k);

Triangle(const Triangle& orig);

friend std::ostream& operator<<(std::ostream& os, const Triangle& obj);

bool operator==(const Triangle& other);

bool operator<(const Triangle& other);

bool operator>(const Triangle& other);

bool operator<=(const Triangle& other);

bool operator>=(const Triangle& other);

operator double () const;

Triangle& operator=(const Triangle& right);

virtual ~Triangle();

private:

size_t side_a;

size_t side_b;

size_t side_c;

};

#endif

Листинг файла TStack. cpp

#include "TStack. h"

#include <exception>

template <class T> TStack<T>::TStack() : head(nullptr) {

}

template <class T> std::shared_ptr<T> TStack<T>::operator[](size_t i) {

if (i > size() — 1) throw std::invalid_argument("index greater then stack size");

size_t j = 0;

for (std::shared_ptr<T> a : * this) {

if (j == i) return a;

j++;

}

return std::shared_ptr<T>(nullptr);

}

template <class T> void TStack<T>::sort() {

if (size() > 1) {

std::shared_ptr<T> middle = pop();

TStack<T> left, right;

while (!empty()) {

std::shared_ptr<T> item = pop();

if (*item < *middle) {

left. push(item);

} else {

right. push(item);

}

}

left. sort();

right. sort();

while (!left. empty()) push(left. pop_last());

push(middle);

while (!right. empty()) push(right. pop_last());

}

}

template<class T > std::future<void> TStack<T>::sort_in_background() {

std::packaged_task<void(void) > task(std::bind(std::mem_fn(&TStack<T>::sort_parallel), this));

std::future<void> res(task. get_future());

std::thread th(std::move(task));

th. detach();

return res;

}

template <class T> void TStack<T>::sort_parallel() {

if (size() > 1) {

std::shared_ptr<T> middle = pop_last();

TStack<T> left, right;

while (!empty()) {

std::shared_ptr<T> item = pop_last();

if (*item < *middle) {

left. push(item);

} else {

right. push(item);

}

}

std::future<void> left_res = left. sort_in_background();

std::future<void> right_res = right. sort_in_background();

left_res. get();

while (!left. empty()) push(left. pop_last());

push(middle);

right_res. get();

while (!right. empty()) push(right. pop_last());

}

}

template <class T> std::ostream& operator<<(std::ostream& os, const TStack<T>& stack) {

std::shared_ptr<TStackItem < T>> item = stack. head;

while (item!= nullptr) {

os << *item;

item = item->GetNext();

}

return os;

}

template <class T> void TStack<T>::push(T *item) {

std::shared_ptr<TStackItem < T >> other(new TStackItem<T>(item));

other->SetNext(head);

head = other;

}

template <class T> void TStack<T>::push(std::shared_ptr<T> item) {

std::shared_ptr<TStackItem < T >> other(new TStackItem<T>(item));

other->SetNext(head);

head = other;

}

template <class T> bool TStack<T>::empty() {

return head == nullptr;

}

template <class T> std::shared_ptr<T> TStack<T>::pop() {

std::shared_ptr<T> result;

if (head!= nullptr) {

result = head->GetValue();

head = head->GetNext();

}

return result;

}

template <class T> std::shared_ptr<T> TStack<T>::pop_last() {

std::shared_ptr<T> result;

if (head!= nullptr) {

std::shared_ptr<TStackItem < T>> element = head;

std::shared_ptr<TStackItem < T>> prev = nullptr;

while (element->GetNext() != nullptr) {

prev = element;

element = element->GetNext();

}

if (prev!= nullptr) {

prev->SetNext(nullptr);

result = element->GetValue();

} else {

result = element->GetValue();

head = nullptr;

}

}

return result;

}

template <class T> size_t TStack<T>::size() {

int result = 0;

for (auto i : * this) result++;

return result;

}

template <class T> TIterator<TStackItem<T>, T> TStack<T>::begin() {

return TIterator<TStackItem<T>, T>(head);

}

template <class T> TIterator<TStackItem<T>, T> TStack<T>::end() {

return TIterator<TStackItem<T>, T>(nullptr);

}

template <class T> TStack<T>::~TStack() {

//std::cout << "Stack deleted" << std::endl;

}

#include "Triangle. h"

template class TStack<Triangle>;

template std::ostream& operator<<(std::ostream& os, const TStack<Triangle>& stack);

Листинг файла TStackItem. cpp

#include "TStackItem. h"

#include <iostream>

template <class T> TStackItem<T>::TStackItem(T* item) {

this->item = std::shared_ptr<T>(item);

this->next = nullptr;

//std::cout << "Stack item: created" << std::endl;

}

template <class T> TStackItem<T>::TStackItem(std::shared_ptr<T> item) {

this->item = item;

this->next = nullptr;

//std::cout << "Stack item: created" << std::endl;

}

template <class T> std::shared_ptr<TStackItem<T>> TStackItem<T>::SetNext(std::shared_ptr<TStackItem<T>> next) {

std::shared_ptr<TStackItem < T>> old = this->next;

this->next = next;

return old;

}

template <class T> std::shared_ptr<T> TStackItem<T>::GetValue() const {

return this->item;

}

template <class T> std::shared_ptr<TStackItem<T>> TStackItem<T>::GetNext() {

return this->next;

}

template <class T> TStackItem<T>::~TStackItem() {

//std::cout << "Stack item: deleted" << std::endl;

}

template <class A> std::ostream& operator<<(std::ostream& os, const TStackItem<A>& obj) {

os << "[" << *obj. item << "]" << std::endl;

return os;

}

#include "Triangle. h"

template class TStackItem<Triangle>;

template std::ostream& operator<<(std::ostream& os, const TStackItem<Triangle>& obj);

Листинг файла Triangle. cpp

#include "Triangle. h"

#include <iostream>

#include <cmath>

Triangle::Triangle() : Triangle(0, 0, 0) {

//std::cout << "Triangle created: default" << std::endl;

}

Triangle::Triangle(size_t i, size_t j, size_t k) : side_a(i), side_b(j), side_c(k) {

//std::cout << "Triangle created: " << side_a << ", " << side_b << ", " << side_c << std::endl;

}

Triangle::Triangle(const Triangle& orig) {

//std::cout << "Triangle copy created" << std::endl;

side_a = orig. side_a;

side_b = orig. side_b;

side_c = orig. side_c;

}

bool Triangle::operator==(const Triangle& other) {

return (side_a == other. side_a)&&(side_b == other. side_b)&&(side_c == other. side_c);

}

Triangle& Triangle::operator=(const Triangle& right) {

if (this == &right) return *this;

std::cout << "Triangle copied" << std::endl;

side_a = right. side_a;

side_b = right. side_b;

side_c = right. side_c;

return *this;

}

bool Triangle::operator<(const Triangle& other) {

return (double) (*this)<(double) (other);

}

bool Triangle::operator>(const Triangle& other) {

return double(*this)>double(other);

}

bool Triangle::operator<=(const Triangle& other) {

return double(*this) <= double(other);

}

bool Triangle::operator>=(const Triangle& other) {

return double(*this) >= double(other);

}

Triangle::operator double () const {

double p = double(side_a + side_b + side_c) / 2.0;

return sqrt(p * (p — double(side_a))*(p — double(side_b))*(p — double(side_c)));

}

Triangle::~Triangle() {

//std::cout << "Triangle deleted" << std::endl;

}

std::ostream& operator<<(std::ostream& os, const Triangle& obj) {

os << "a=" << obj. side_a << ", b=" << obj. side_b << ", c=" << obj. side_c << " Square=" << double(obj);

return os;

}

Листинг файла main. cpp

#include <cstdlib>

#include <iostream>

using namespace std;

#include "Triangle. h"

#include "TStack. h"

#include <random>

int main(int argc, char** argv) {

TStack<Triangle> stack;

std::default_random_engine generator;

std::uniform_int_distribution<int> distribution(1, 10000);

for (int i = 0; i < 10000; i++) {

int side = distribution(generator);

stack. push(new Triangle(side, side, side));

}

std::cout << "Sort ————-" << std::endl;

//stack. sort();

stack. sort_parallel();

std::cout << "Done ————-" << std::endl;

return 0;

}

Лабораторная работа №9

Цель работы

Целью лабораторной работы является:

·  Знакомство с лямбда-выражениями

Задание

Используя структуры данных, разработанные для лабораторной работы №6 (контейнер первого уровня и классы-фигуры) необходимо разработать:

·  Контейнер второго уровня с использованием шаблонов.

·  Реализовать с помощью лямбда-выражений набор команд, совершающих операции над контенйром 1-го уровня:

o  Генерация фигур со случайным значением параметров;

o  Печать контейнера на экран;

o  Удаление элементов со значением площади меньше определенного числа;

·  В контенер второго уровня поместить цепочку команд.

·  Реализовать цикл, который проходит по всем командам в контенере второго уровня и выполняет их, применяя к контейнеру первого уровня.

Для создания потоков использовать механизмы:

·  future

·  packaged_task/async

Для обеспечения потоко-безопасности структур данных использовать:

·  mutex

·  lock_guard

Нельзя использовать:

·  Стандартные контейнеры std.

Полезный пример

Данный пример демонстрирует основные возможности языка C++, которые понадобится применить в данной лабораторной работе. Пример не является решением варианта лабораторной работы.

Листинг файла TIterator. h

#ifndef TITERATOR_H

#define TITERATOR_H

#include <memory>

#include <iostream>

template <class node, class T>

class TIterator

{

public:

TIterator(std::shared_ptr<node> n) {

node_ptr = n;

}

std::shared_ptr<T> operator * (){

return node_ptr->GetValue();

}

std::shared_ptr<T> operator -> (){

return node_ptr->GetValue();

}

void operator ++ (){

node_ptr = node_ptr->GetNext();

}

TIterator operator ++ (int){

TIterator iter(*this);

++(*this);

return iter;

}

bool operator == (TIterator const& i){

return node_ptr == i. node_ptr;

}

bool operator!= (TIterator const& i){

return!(*this == i);

}

private:

std::shared_ptr<node> node_ptr;

};

#endif

Листинг файла TStack. h

#ifndef TSTACK_H

#define TSTACK_H

#include "TIterator. h"

#include "TStackItem. h"

#include <memory>

#include <future>

#include <mutex>

#include <thread>

template <class T> class TStack {

public:

TStack();

void push(T* item);

void push(std::shared_ptr<T> item);

bool empty();

size_t size();

TIterator<TStackItem<T>,T> begin() const;

TIterator<TStackItem<T>,T> end() const;

std::shared_ptr<T> operator[] (size_t i);

std::shared_ptr<T> pop();

std::shared_ptr<T> pop_last();

template <class A> friend std::ostream& operator<<(std::ostream& os, const TStack<A>& stack);

virtual ~TStack();

private:

std::recursive_mutex stack_mutex;

std::shared_ptr<TStackItem<T>> head;

};

#endif /* TSTACK_H */

Листинг файла TStackITem. h

#ifndef TSTACKITEM_H

#define TSTACKITEM_H

#include <memory>

#include <thread>

#include <mutex>

template<class T> class TStackItem {

public:

TStackItem(T *item, std::recursive_mutex *parent);

TStackItem(std::shared_ptr<T> item, std::recursive_mutex *parent);

template<class A> friend std::ostream& operator<<(std::ostream& os, const TStackItem<A>& obj);

std::shared_ptr<TStackItem<T>> SetNext(std::shared_ptr<TStackItem> next);

std::shared_ptr<TStackItem<T>> GetNext();

std::shared_ptr<T> GetValue() const;

virtual ~TStackItem();

private:

std::shared_ptr<T> item;

std::shared_ptr<TStackItem<T>> next;

std::recursive_mutex *stack_mutex;

};

Листинг файла TRiangle. h

#ifndef TRIANGLE_H

#define TRIANGLE_H

#include <cstdlib>

#include <iostream>

class Triangle {

public:

Triangle();

Triangle(size_t i, size_t j, size_t k);

Triangle(const Triangle& orig);

friend std::ostream& operator<<(std::ostream& os, const Triangle& obj);

bool operator==(const Triangle& other);

bool operator<(const Triangle& other);

bool operator>(const Triangle& other);

bool operator<=(const Triangle& other);

bool operator>=(const Triangle& other);

operator double () const;

Triangle& operator=(const Triangle& right);

virtual ~Triangle();

private:

size_t side_a;

size_t side_b;

size_t side_c;

};

#endif /* TRIANGLE_H */

Листинг файла TStack. cpp

#include "TStack. h"

#include <exception>

template <class T> TStack<T>::TStack() : head(nullptr) {

//std::cout << "Stack created" << std::endl;

}

template <class T> std::shared_ptr<T> TStack<T>::operator[](size_t i) {

std::lock_guard<std::recursive_mutex> lock(stack_mutex);

if (i > size() — 1) throw std::invalid_argument("index greater then stack size");

size_t j = 0;

for (std::shared_ptr<T> a : * this) {

if (j == i) return a;

j++;

}

return std::shared_ptr<T>(nullptr);

}

template <class T> std::ostream& operator<<(std::ostream& os, const TStack<T>& stack) {

for(auto i:stack) os << *i << std::endl;

return os;

}

template <class T> void TStack<T>::push(T *item) {

std::lock_guard<std::recursive_mutex> lock(stack_mutex);

std::shared_ptr<TStackItem < T >> other(new TStackItem<T>(item,&stack_mutex));

other->SetNext(head);

head = other;

}

template <class T> void TStack<T>::push(std::shared_ptr<T> item) {

std::lock_guard<std::recursive_mutex> lock(stack_mutex);

std::shared_ptr<TStackItem < T >> other(new TStackItem<T>(item,&stack_mutex));

other->SetNext(head);

head = other;

}

template <class T> bool TStack<T>::empty() {

std::lock_guard<std::recursive_mutex> lock(stack_mutex);

return head == nullptr;

}

template <class T> std::shared_ptr<T> TStack<T>::pop() {

std::lock_guard<std::recursive_mutex> lock(stack_mutex);

std::shared_ptr<T> result;

if (head!= nullptr) {

result = head->GetValue();

head = head->GetNext();

}

return result;

}

template <class T> std::shared_ptr<T> TStack<T>::pop_last() {

std::lock_guard<std::recursive_mutex> lock(stack_mutex);

std::shared_ptr<T> result;

if (head!= nullptr) {

std::shared_ptr<TStackItem < T>> element = head;

std::shared_ptr<TStackItem < T>> prev = nullptr;

while (element->GetNext() != nullptr) {

prev = element;

element = element->GetNext();

}

if (prev!= nullptr) {

prev->SetNext(nullptr);

result = element->GetValue();

} else {

result = element->GetValue();

head = nullptr;

}

}

return result;

}

template <class T> size_t TStack<T>::size() {

std::lock_guard<std::recursive_mutex> lock(stack_mutex);

int result = 0;

for (auto i : * this) result++;

return result;

}

template <class T> TIterator<TStackItem<T>, T> TStack<T>::begin() const{

return TIterator<TStackItem<T>, T>(head);

}

template <class T> TIterator<TStackItem<T>, T> TStack<T>::end() const{

return TIterator<TStackItem<T>, T>(nullptr);

}

template <class T> TStack<T>::~TStack() {

//std::cout << "Stack deleted" << std::endl;

}

#include "Triangle. h"

#include <functional>

template class TStack<Triangle>;

template class TStack<std::function<void(void)>>;

template std::ostream& operator<<(std::ostream& os, const TStack<Triangle>& stack);

Листинг файла TStackItem. cpp

#include "TStackItem. h"

#include <iostream>

template <class T> TStackItem<T>::TStackItem(T* item, std::recursive_mutex *parent) {

this->stack_mutex = parent;

this->item = std::shared_ptr<T>(item);

this->next = nullptr;

//std::cout << "Stack item: created" << std::endl;

}

template <class T> TStackItem<T>::TStackItem(std::shared_ptr<T> item, std::recursive_mutex *parent) {

this->stack_mutex = parent;

this->item = item;

this->next = nullptr;

//std::cout << "Stack item: created" << std::endl;

}

template <class T> std::shared_ptr<TStackItem<T>> TStackItem<T>::SetNext(std::shared_ptr<TStackItem<T>> next) {

std::unique_lock<std::recursive_mutex> lock(*stack_mutex);

std::shared_ptr<TStackItem < T>> old = this->next;

this->next = next;

return old;

}

template <class T> std::shared_ptr<T> TStackItem<T>::GetValue() const {

std::unique_lock<std::recursive_mutex> lock(*stack_mutex);

return this->item;

}

template <class T> std::shared_ptr<TStackItem<T>> TStackItem<T>::GetNext() {

std::lock_guard<std::recursive_mutex> lock(*stack_mutex);

return this->next;

}

template <class T> TStackItem<T>::~TStackItem() {

//std::cout << "Stack item: deleted" << std::endl;

}

template <class A> std::ostream& operator<<(std::ostream& os, const TStackItem<A>& obj) {

std::lock_guard<std::recursive_mutex> lock(*obj. stack_mutex);

os << "[" << *obj. item << "]" << std::endl;

return os;

}

#include "Triangle. h"

#include <functional>

template class TStackItem<Triangle>;

template class TStackItem<std::function<void(void)>>;

template std::ostream& operator<<(std::ostream& os, const TStackItem<Triangle>& obj);

Листинг файла Triangle. cpp

#include "Triangle. h"

#include <iostream>

#include <cmath>

Triangle::Triangle() : Triangle(0, 0, 0) {

//std::cout << "Triangle created: default" << std::endl;

}

Triangle::Triangle(size_t i, size_t j, size_t k) : side_a(i), side_b(j), side_c(k) {

//std::cout << "Triangle created: " << side_a << ", " << side_b << ", " << side_c << std::endl;

}

Triangle::Triangle(const Triangle& orig) {

//std::cout << "Triangle copy created" << std::endl;

side_a = orig. side_a;

side_b = orig. side_b;

side_c = orig. side_c;

}

bool Triangle::operator==(const Triangle& other) {

return (side_a == other. side_a)&&(side_b == other. side_b)&&(side_c == other. side_c);

}

Triangle& Triangle::operator=(const Triangle& right) {

if (this == &right) return *this;

std::cout << "Triangle copied" << std::endl;

side_a = right. side_a;

side_b = right. side_b;

side_c = right. side_c;

return *this;

}

bool Triangle::operator<(const Triangle& other) {

return (double) (*this)<(double) (other);

}

bool Triangle::operator>(const Triangle& other) {

return double(*this)>double(other);

}

bool Triangle::operator<=(const Triangle& other) {

return double(*this) <= double(other);

}

bool Triangle::operator>=(const Triangle& other) {

return double(*this) >= double(other);

}

Triangle::operator double () const {

double p = double(side_a + side_b + side_c) / 2.0;

return sqrt(p * (p — double(side_a))*(p — double(side_b))*(p — double(side_c)));

}

Triangle::~Triangle() {

//std::cout << "Triangle deleted" << std::endl;

}

std::ostream& operator<<(std::ostream& os, const Triangle& obj) {

os << "a=" << obj. side_a << ", b=" << obj. side_b << ", c=" << obj. side_c << " Square=" << double(obj);

return os;

}

Листинг файла main. cpp

#include <cstdlib>

using namespace std;

#include "Triangle. h"

#include "TStack. h"

#include <future>

#include <functional>

#include <random>

#include <thread>

int main(int argc, char** argv) {

TStack<Triangle> stack_triangle;

typedef std::function<void (void) > command;

TStack < command> stack_cmd;

command cmd_insert = [&]() {

std::cout << "Command: Create triangles" << std::endl;

std::default_random_engine generator;

std::uniform_int_distribution<int> distribution(1, 1000);

for (int i = 0; i < 10; i++) {

int side = distribution(generator);

stack_triangle. push(new Triangle(side, side, side));

}

};

command cmd_print = [&]() {

std::cout << "Command: Print stack" << std::endl;

std::cout << stack_triangle;

};

command cmd_reverse = [&]() {

std::cout << "Command: Reverse stack" << std::endl;

TStack<Triangle> stack_tmp;

while(!stack_triangle. empty()) stack_tmp. push(stack_triangle. pop_last());

while(!stack_tmp. empty()) stack_triangle. push(stack_tmp. pop());

};

stack_cmd. push(std::shared_ptr<command> (&cmd_print, [](command*) {

})); // using custom deleter

stack_cmd. push(std::shared_ptr<command> (&cmd_reverse, [](command*) {

})); // using custom deleter

stack_cmd. push(std::shared_ptr<command> (&cmd_print, [](command*) {

})); // using custom deleter

stack_cmd. push(std::shared_ptr<command> (&cmd_insert, [](command*) {

})); // using custom deleter

while (!stack_cmd. empty()) {

std::shared_ptr<command> cmd = stack_cmd. pop();

std::future<void> ft = std::async(*cmd);

ft. get();

//std::thread(*cmd).detach();

}

return 0;

}

Пояснения к листингам

В файле main. cpp используются лямбда-выражения со списком захвата «по-ссылке»:

·  command cmd_insert = [&]() { …} это связанно с необходимостью использовать общую переменную TStack<Triangle> stack_triangle; объявленную в теле функции int main(int argc, char** argv). Так как все переменные из main передаются в лямбда выражения по ссылке, то можно менять значения переменных. Это используется при создании и модификации стека.

·  Поскольку в качестве элемента стека используется std::shared_ptr<..> то мы сталкиваемся с ситуацией, когда элементы стека будут принудительно удаляться (т. е. вызываться деструктор). Однако, в качестве элементов стека у нас так же присутствует и тип command (т. е. std::function<void (void) >) который представляет собой указатель на функцию. А указатели на функцию удалять нельзя. Поэтому при конструировании std::shared_ptr<command> мы вынуждены использовать вариант умного-указателя с переопределенным деструктором. Деструктор мы то же описываем в виде лямбда-выражения: std::shared_ptr<command> (&cmd_insert, [](command*) {})

·