Предыдущий пост -
Следующий пост -

Список с индексацией.

Рубрика: C++, Дата: 24 June, 2013, Автор:

Реализуйте список, похожий на стандартный list, но дополнительно поддерживающий индексацию. Сравните стоимость индексации списков и стоимость индексации для стандартного вектора (то есть типа vector).

Добавил я индексацию к list вот файл list.h:

//ob69vlenie list
#ifndef LIST_H
#define LIST_H

#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;

template<class T>
class list
{	
public:
	typedef T type_data;
	typedef size_t size_type;
	typedef T* iterator;
	//конструктор по умолчанию
	list():size_t(0){}
	//добавить элемент в конец списка
	void push_back(type_data n);
	//доступ к последнему элементу
	type_data& back();
	//доступ к первому элементу
	type_data& front();
	//добавление в начало списка
	void push_front(type_data n);
	//вывод размера
	size_type size(){return size_t;}
	//возврат указателя на первый элемент
	iterator begin(){return &mass[0];}
	//возврат указателя на элемент за последним
	iterator end(){return &mass[size_t];}
	//индексация
	type_data& operator[](int i);

private:
	type_data* mass;
	size_type size_t;
};

//добавить элемент в конец списка
template<class T>
void list<T>::push_back(type_data n)
{
	type_data* temp=mass;
	mass=new type_data[size_t+1];
	for(int i=0;i<size_t;i++)
		mass[i]=temp[i];
	mass[size_t++]=n;
}
//доступ к последнему элементу
template<class T>
typename list<T>::type_data& list<T>::back()
{
	return mass[size_t-1];
}
//доступ к первому элементу
template<class T>
typename list<T>::type_data& list<T>::front()
{
	return mass[0];
}
//добавление в начало списка
template<class T>
void list<T>::push_front(type_data n)
{
	type_data* temp=mass;
	mass=new type_data[size_t+1];
	mass[0]=n;
	for(int i=0,j=1;i<size_t;i++,j++)
		mass[j]=temp[i];
	size_t++;
}
//индексация
template<class T>
typename list<T>::type_data& list<T>::operator[](int i)
{
	if(i>=size_t) exit(1);
	return mass[i];
}

#endif

Файл main.cpp:

#include <iostream>
using std::cout;
using std::endl;

#include "list.h"

int main()
{
	cout <<"hellow gacpada"<<endl;
	list<int> l;
	l.push_back(4);
	l.push_back(3);
	cout <<l.back()<<endl;
	cout <<l.front()<<endl;
	l.push_front(10);
	cout <<l.front()<<endl;
	cout <<l.back()<<endl;
	cout <<"l.size()= "<<l.size()<<endl;

	list<int>::iterator it;
	for(it=l.begin();it!=l.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	cout <<l[0]<<' '<<l[1]<<' '<<l[2]<<endl;

	return 0;
}

Ну что ж рассматривать и сравнивать индексацию с vector мы не будем, нам это и нафиг не нужно, в общем так. Хотя можно на словах рассмотреть, индексация для вектора я думаю одинаковая будет по скорости как и для списка, потому что поиска нету да и внутреннее представление токое же самое как и у вектора массив. Ну да ладно в общем пропустим эту фигню.

[youtube]http://www.youtube.com/watch?v=EDzdfnSl020[/youtube]

Комментарии:


Оставить комментарий

Your email address will not be published. Required fields are marked *