Создание сложных динамических структур данных
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*) {})
·