Определить класс стек

[simples]

Сообщение от still_alive

Во-первых, причем тут Net

А почему не НЕТ? Тоже ЯП. С историей.

Сообщение от still_alive

Я тогда сейчас хаскелл запилю в тред.

Запилите. По мне - это более полезнее чем теоретические рассуждения на 4 листах выше.

Сообщение от still_alive

Во-вторых, тут передается емкость, по умолчанию равная 10 (а почему 10, а не 9? или 8? или 666?) Емкость - это ни разу не максимальный размер стека и тем более не размер стека. Емкость - это сколько элементов может находиться в стеке при текущем объеме выделенной памяти.

Ну захотели МСовцы 10 элементов иметь в пустом новеньком стэке. А может подошли к делу "по науке" и выделили на это дело пару лямов на исследования "какой начальный размер стэка будет хорош?". Не знаю. Взято из оригинала.

Сообщение от still_alive

Емкость - это ни разу не максимальный размер стека и тем более не размер стека. Емкость - это сколько элементов может находиться в стеке при текущем объеме выделенной памяти.

А кто сказал что это размер стэка?
Я например в условии задачи такого не наблюдаю. Я вообще это условие (конструктор для определения стека по его размеру) читаю как "пусть стэк сразу выделит столько места сколько мне надо. Чтобы не было не О(1) операций".

Сообщение от still_alive

В-третьих, добавление элемента в стек, когда массив уже заполнен, требует выделения нового куска памяти и копирования туда всех элементов - длительность этой операции зависит от кол-ва элементов в стеке.

Ну и что? Ну попадете Вы на это место в паре случаев из сотни другой запросов к стэку, и что?
Внутр.массив растет при необходимости. Тупо в два раза от имеющегося (у МС, который Вам не авторитет).
Добавление нового элемента - операция О(1) практически в 99.99% случаев.
А в оставшийся мизерный процент просходит создание нового массива и копирование в него старых элементов. Тут операция не О(1), да.
При обычном использовании стэка - практически все время стэк будет одного размера (я не знаю реальных задач для стэка где ТОЛЬКО запись в него идет).

[still_alive]

Сообщение от simples

А почему не НЕТ? Тоже ЯП. С историей.

Запилите. По мне - это более полезнее чем теоретические рассуждения на 4 листах выше.

Я к тому, что не стоит рассматривать другие языки и их особенности.

Сообщение от simples

Я вообще это условие (конструктор для определения стека по его размеру) читаю как "пусть стэк сразу выделит столько места сколько мне надо. Чтобы не было не О(1) операций".

Скорее "чтобы было как можно меньше не О(1) операций".

Сообщение от simples

Ну и что? Ну попадете Вы на это место в паре случаев из сотни другой запросов к стэку, и что?
Внутр.массив растет при необходимости. Тупо в два раза от имеющегося (у МС, который Вам не авторитет).
Добавление нового элемента - операция О(1) практически в 99.99% случаев.
А в оставшийся мизерный процент просходит создание нового массива и копирование в него старых элементов. Тут операция не О(1), да.
При обычном использовании стэка - практически все время стэк будет одного размера (я не знаю реальных задач для стэка где ТОЛЬКО запись в него идет).

Об этом уже речь в этой теме велась, в том числе и мной.
Стек может постоянно расти в многопоточной среде - когда одни потоки разгребают задачи из стека куда медленнее, чем другие потоки помещают их туда.

[simples]

Сообщение от still_alive

Я к тому, что не стоит рассматривать другие языки и их особенности.

Никаких особенностей НЕТ не обсуждалось и не предлагалось для решения задачи ТС. В С++ - нет чего из описанного мной(класс,массив,копирование массива)?

Сообщение от still_alive

Об этом уже речь в этой теме велась, в том числе и мной.
Стек может постоянно расти в многопоточной среде - когда одни потоки разгребают задачи из стека куда медленнее, чем другие потоки помещают их туда.

Не вижу здесь проблемы стэка. Вижу проблему приложения.

[rrrFer]

still_alive

Но что такое по сути дек? Это набор векторов. Чтобы при перераспределении памяти нужно было копировать не все элементы, а только часть.

поясни как дек тут поможет.
Мне кажется или вы дек с чем-то путаете?
дек - это обычная двусвязная очередь. От стека отличается лишь тем, что я могу элементы не только в начало, но и в конец впихивать. При "перераспределении памяти" эта фича никак не поможет.


simples

Гм... а с каких пор добавление нового элемента в массив - НЕ О(1) операция?

с тех пор, как будет достигнут конец массива

По мне - это более полезнее чем теоретические рассуждения на 4 листах выше.

По мне так вы не осилили рассуждения на 4 листах выше, поэтому начали опять генерировать какой-то бред.

При обычном использовании стэка - практически все время стэк будет одного размера (я не знаю реальных задач для стэка где ТОЛЬКО запись в него идет).

расскажи нам, что значит "обычное использование стека".


still_alive

Стек может постоянно расти в многопоточной среде - когда одни потоки разгребают задачи из стека куда медленнее, чем другие потоки помещают их туда.

стек может расти в любой среде.

[still_alive]

Не вижу здесь проблемы стэка. Вижу проблему приложения.

Проблемы, не проблемы - это отдельный разговор. Я привел реальный пример, когда стек может расти.

стек может расти в любой среде.

А где я говорил, что он растет ТОЛЬКО в многопоточной среде?

поясни как дек тут поможет.
Мне кажется или вы дек с чем-то путаете?
дек - это обычная двусвязная очередь. От стека отличается лишь тем, что я могу элементы не только в начало, но и в конец впихивать. При "перераспределении памяти" эта фича никак не поможет.

Не двусвязная, а двусторонняя. Объясняю, чем поможет. В STL дек реализуется не как один массив, в котором хранятся все элементы, а как набор блоков - массивов меньшего размера. Когда я вставляю новый элемент, а памяти уже не хватает, я просто выделяю память под новый блок. И тогда вообще никакого копирования элементов не происходит.

[simples]

Сообщение от rrrFer

с тех пор, как будет достигнут конец массива

Неужели? Кэп, это Вы? Вы про стэк сейчас пишите или про массив в котором закончилось место? Ничего не попутали?

Сообщение от rrrFer

поэтому начали опять генерировать какой-то бред

Пруф?

Сообщение от rrrFer

расскажи нам, что значит "обычное использование стека".

Это когда стэк на месте и он работает.

[rrrFer]

simples

Неужели? Кэп, это Вы? Вы про стэк сейчас пишите или про массив в котором закончилось место? Ничего не попутали?

Ничего. С возрастом пройдет, может быть.

still_alive

А где я говорил, что он растет ТОЛЬКО в многопоточной среде?

нигде, но зачем вообще было упомянать многопоточную среду если он может расти в любой среде?

Объясняю, чем поможет. В STL дек реализуется не как один массив, в котором хранятся все элементы, а как набор блоков - массивов меньшего размера. Когда я вставляю новый элемент, а памяти уже не хватает, я просто выделяю память под новый блок. И тогда вообще никакого копирования элементов не происходит.

ну причем тут STL? я рад, что он в STL так реализуется, это здорово и интересно, но суть дека не в этом ведь. Суть его в том, что добавление и удаление элементов я могу производить в любой его конец и выполняются эти операции на О(1).

Не двусвязная, а двусторонняя.

как запилить двусторонюю, но не двусвязную очередь так, чтобы в любой конец я мог за О(1) добавить? - я не представляю.

[still_alive]

Сообщение от rrrFer

нигде, но зачем вообще было упомянать многопоточную среду если он может расти в любой среде?

Да просто как пример.

Сообщение от rrrFer

ну причем тут STL? я рад, что он в STL так реализуется, это здорово и интересно, но суть дека не в этом ведь. Суть его в том, что добавление и удаление элементов я могу производить в любой его конец и выполняются эти операции на О(1).

как запилить двусторонюю, но не двусвязную очередь так, чтобы в любой конец я мог за О(1) добавить? - я не представляю.

Я же про STL не просто так сказал. Там как раз можно добавлять и удалять с обеих сторон и за O(1). Обеспечивается это тем, что первый и последний блоки растут в противоположных направлениях, только и всего.

[rrrFer]

Я же про STL не просто так сказал. Там как раз можно добавлять и удалять с обеих сторон и за O(1). Обеспечивается это тем, что первый и последний блоки растут в противоположных направлениях, только и всего.

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

[maka42rus]

Сделала такое задание: Определить класс вектор. В класс включить два конструктора для определения вектора по его размеру и путем копирования другого вектора. При задании вектора по его размеру предусмотреть его заполнение случайными числами. Предусмотреть функции сортировки вектора по возрастанию и нахождения среднего арифметического из элементов вектора. (только здесь вектор - одномерный массив, а мне нужен стек - двумерный. Никак не получается сделать! )

#include<conio.h>
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<iostream>
using namespace std;

class Vector{
public:
	int size;
	int *data;
	Vector(int size) : size(size), data(new int [size]) {}
	~Vector() {delete[] data;}

	void srar(){
		float s=0;
		for(int i=0;i<size;i++){
			s+=data[i];}
	s=s/size;
	cout<<"\n\nSrednee arifmeticheskoe: "<<s;
	}

	void sort(){
		int bank=0;
		for(int j=0; j<50;j++){
			for(int i=1;i<size;i++){
				if(data[i]<data[i-1]){
					bank=data[i]; data[i]=data[i-1]; data[i-1]=bank;}}}
		cout<<"\n\nSortirovka po vozrastaniy:\n ";
		for(int i=0;i<size;i++)
			cout<<data[i]<<" ";
	}
};
int main() {
	int i, d;
	srand (time(NULL));
	cout<<"Vvedi razmer:"; cin>>d;
	Vector v1(d);
	for(i=0;i<v1.size;i++){
		v1.data[i]=rand()%100-50; cout<<v1.data[i]<<" ";}

	cout<<"\nCopy vector:\n";
	Vector copy=v1;
	for(i=0;i<copy.size;i++){
		cout<<copy.data[i]<<" ";}

	v1.sort();
	v1.srar();

	getch();
	return 0;
}