Лабораторная работа 22 / lab2_1 / test_sequences / test_sequences

#include <conio.h>
#include <stdio.h>
#include <process.h>
#include <ctime>

#include <string>
#include <iostream>

#include <vector>
#include <list>
#include <deque>

using namespace std;

void clrscr(){
	system("cls");
}

class Test {
	int x[100];
} t;

template<class Cont>
struct InsertBack {
	void operator()(Cont& c, long count) {
		for(long i = 0; i < count; i++)
			c.push_back(t);
	}
	string testName() { 
		return "InsertBack"; 
	}
};

template<class Cont>
struct InsertFront {
	void operator()(Cont& c, long count) {
		long cnt = count * 10;
		for(long i = 0; i < cnt; i++)
			c.push_front(t);
	}  
	string testName() {
		return "InsertFront"; 
	}
};

template<class Cont>
struct InsertMiddle {
	void operator()(Cont& c, long count) {
		Cont::iterator it;
		long cnt = count / 10;
		for(long i = 0; i < cnt; i++) {
			// Must get the iterator every time to keep
			// from causing an access violation with
			// vector. Increment it to put it in the
			// middle of the container:
			it = c.begin();
			it++;
			c.insert(it, t);
		}
	}
	string testName() { 
		return "InsertMiddle"; 
	}
};

template<class Cont>
struct RandomAccess { // Not for list
	void operator()(Cont& c, long count) {
		int sz = c.size();
		long cnt = count * 100;
		for(long i = 0; i < cnt; i++)
			c[rand() % sz];
	}
	string testName() { 
		return "RandomAccess"; 
	}
};

template<class Cont>
struct Traversal {
	void operator()(Cont& c, long count) {
		long cnt = count / 100;
		for(long i = 0; i < cnt; i++) {
			Cont::iterator it = c.begin(),
			end = c.end();
			while(it != end) 
				it++;
		}
	}
	string testName() { 
		return "Traversal"; 
	}
};

template<class Cont>
struct Swap {
	void operator()(Cont& c, long count) {
		int middle = c.size() / 2;
		Cont::iterator it = c.begin(), 
		mid = c.begin();
		it++; // Put it in the middle
		for(int x = 0; x < middle + 1; x++)
			mid++;
		long cnt = count * 10;
		for(long i = 0; i < cnt; i++)
			swap(*it, *mid);
	}
	string testName() { 
		return "Swap"; 
	}
};

template<class Cont>
struct RemoveMiddle {
	void operator()(Cont& c, long count) {
		long cnt = count / 10;
		if(cnt > c.size()) {
			cout << "RemoveMiddle: not enough elements" << endl;
			return;
		}
		for(long i = 0; i < cnt; i++) {
			Cont::iterator it = c.begin();
			it++;
			c.erase(it);
		}
	}
	string testName() { 
		return "RemoveMiddle"; 
	}
};

template<class Cont>
struct RemoveBack {
	void operator()(Cont& c, long count) {
		long cnt = count * 10;
		if(cnt > c.size()) {
			cout << "RemoveBack: not enough elements" << endl;
			return;
		}
		for(long i = 0; i < cnt; i++)
			c.pop_back();
	}
	string testName() { 
		return "RemoveBack";
	}
};

template<class Op, class Container>
void measureTime(Op f, Container& c, long count){
	string id(typeid(f).name());
	bool Deque = id.find("deque") != string::npos;
	bool List = id.find("list") != string::npos;
	bool Vector = id.find("vector") !=string::npos;
	string cont = Deque ? "deque": 
				List ? "list":
				Vector? "vector" : "unknown";

	cout << f.testName() << " for " << cont << ": ";
	clock_t ticks = clock();

	f(c, count); 

	ticks = clock() - ticks;
	cout << ticks << endl;
}

typedef deque<Test> Deque;
typedef list<Test> List;
typedef vector<Test> Vector;

int main(int argc, char* argv[])
{
	clrscr();

	cout << endl;
	cout << "============================================" << endl;
	cout << "Testing STL sequences: vector, list, dequeue" << endl;
	cout << "============================================" << endl;
	getch();

	srand(time(0));
	long count = 5000;
	Deque deque;
	List list;
	Vector vector, vector2;
	vector2.reserve(count); 

	cout << endl;
	measureTime(InsertBack<Vector>(), vector, count);
	cout << "[w/ memory pre allocation] ";
	measureTime(InsertBack<Vector>(), vector2, count);
	measureTime(InsertBack<Deque>(), deque, count);
	measureTime(InsertBack<List>(), list, count);

	cout << endl;
	// Can't push_front() with a vector:
	cout << "InsertFront for vector: unavailable" << endl;
	measureTime(InsertFront<Deque>(), deque, count);
	measureTime(InsertFront<List>(), list, count);

	cout << endl;
	measureTime(InsertMiddle<Vector>(), vector, count);
	measureTime(InsertMiddle<Deque>(), deque, count);
	measureTime(InsertMiddle<List>(), list, count);

	cout << endl;
	measureTime(RandomAccess<Vector>(), vector, count);
	measureTime(RandomAccess<Deque>(), deque, count);
	// Can't operator[] with a list:
	cout << "RandomAccess for list: unavailable" << endl;

	cout << endl;
	measureTime(Traversal<Vector>(), vector, count);
	measureTime(Traversal<Deque>(), deque, count);
	measureTime(Traversal<List>(), list, count);

	cout << endl;
	measureTime(Swap<Vector>(), vector, count);
	measureTime(Swap<Deque>(), deque, count);
	measureTime(Swap<List>(), list, count);

	cout << endl;
	measureTime(RemoveMiddle<Vector>(), vector, count);
	measureTime(RemoveMiddle<Deque>(), deque, count);
	measureTime(RemoveMiddle<List>(), list, count);

	cout << endl;
	vector.resize(vector.size() * 10);
	measureTime(RemoveBack<Vector>(), vector, count);
	measureTime(RemoveBack<Deque>(), deque, count);
	measureTime(RemoveBack<List>(), list, count);

	return 0;
}