Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > C++ > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 21.05.2013, 17:23   #1
el_gato_de_Ch
Пользователь
 
Регистрация: 21.05.2013
Сообщений: 13
По умолчанию реализация стека через массив

Добрый день форумчане.

Изучаю C++, и в качестве примера объявления класса решил попробовать сам запилить свой класс стека, просто так для ознакомления.

my_stack.hpp
Код:
#ifndef _MY_STACK_HPP_
#define _MY_STACK_HPP_

// 
class my_stack
{
	int last;
	int *data;
	int max_elem;
	
	public :
	
	int top(void);
	void pop(void);
	void push(int);
	int size(void);
	bool empty(void);
	
	my_stack();
	my_stack(int);
	
	~my_stack();
};

#endif
my_stack.cpp
Код:
#include "my_stack.hpp"
#include <cstring>
#include <iostream>

my_stack::my_stack()
{
	max_elem = 1;
	last = 0;
	data = new int[max_elem];
}

my_stack::my_stack(int n)
{
	max_elem = n;
	last = 0;
	data = new int[max_elem];
}

my_stack::~my_stack()
{
	delete[] data;
}

int my_stack::top()
{
	return (last)? data[last - 1] : -1;
}

void my_stack::pop()
{
	if(last)
		--last;	
}

void my_stack::push(int a)
{
	if(last < max_elem)
		data[last++] = a;
	else
	{
		max_elem *= 2;
		int *new_data = new int[max_elem];
		memcpy(new_data, data, max_elem*sizeof(int));
		
		delete[] data; 
		data = new_data;
		data[last++] = a;
	}
	
}

int my_stack::size()
{
	return last;
}

bool my_stack::empty()
{
	return !last;
}
в main'e я просто заполняю этот стек и освобождаю его, вроде всё работает кошерно.

У меня возникает вопрос "стоит ли функции size() и empty() сделать inline, если да, то какие от этого плюсы и выигрыш, если нет, то какие функции стоит помечать inline". Стек я реализовывал на основе массива, так проще, насколько эстетична такая реализация ? ну и соответственно, на ваш опытный взгляд всё ли правильно сделано ? нет ли утечек памяти ?
el_gato_de_Ch вне форума Ответить с цитированием
Старый 21.05.2013, 17:39   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
У меня возникает вопрос "стоит ли функции size() и empty() сделать inline, если да, то какие от этого плюсы и выигрыш, если нет, то какие функции стоит помечать inline".
Плюс понятен - inline-функция может быть встроена компилятором в точку вызова, что позволит сэкономить немного времени. Минус - при этом определение функции придётся вынести в заголовочный файл.
Я бы сказал, что это скорее оптимизация и, как любая оптимизация, должна проводиться только в том случае, если её положительный эффект признан значимым (то есть, в данном случае не стоит).
Цитата:
Стек я реализовывал на основе массива, так проще, насколько эстетична такая реализация ?
Само по себе использование расширяемого массива - вроде нормальный ход, пока стек не слишком крупный (т.к. при большом числе элементов будет требоваться много памяти одним непрерывным куском, а это может быть неприятно).
Цитата:
ну и соответственно, на ваш опытный взгляд всё ли правильно сделано ?
1) Идеологически, насколько удачная идея для top() при пустом стеке возвращать -1? Вынесено ли это поведение в интерфейс класса? Я думаю, что, как минимум, второго делать не стоит - т.е. в описании метода должно стоять "при пустом стеке поведение метода не определено", а не "при пустом стеке top() возвращает -1".
2) Методы top(), size(), empty() следует пометить как константные.
3) Для размеров (и индексов) в C++ принято использовать тип size_t.
4) (а вот это серьёзно) memcpy при копировании выходит за пределы массива-источника. Исправить.
5) (ещё серьёзнее) Не определён и не запрещён конструктор копии, при том, что класс управляет ресурсом (т.е. копирование с помощью memcpy некорректно). Исправить немедленно.
6) Память, занимаемая стеком, не уменьшается. Возможно, стоит добавить проверку в pop для случая, когда last << max_elem.
Abstraction вне форума Ответить с цитированием
Старый 21.05.2013, 21:17   #3
el_gato_de_Ch
Пользователь
 
Регистрация: 21.05.2013
Сообщений: 13
По умолчанию

Спасибо за подробный ответ.

у меня теперь получился вот такой код.

my_stack.hpp

Код:
#ifndef _MY_STACK_HPP_
#define _MY_STACK_HPP_

#include <cstdlib>

// 
class my_stack
{
	std::size_t last;
	int *data;
	std::size_t max_elem;
	
	public :
	
	int top(void) const;
	void pop(void);
	void push(int);
	int size(void) const;
	bool empty(void) const;
	
	my_stack();
	my_stack(int);
	~my_stack();
	
	private:
	my_stack(const my_stack&) = delete;
	//void my_stack(const my_stack&) = delete;

};

#endif
my_stack.cpp

Код:
#include "my_stack.hpp"
#include <cstring>
#include <iostream>

my_stack::my_stack()
{
	max_elem = 1;
	last = 0;
	data = new int[max_elem];
}

my_stack::my_stack(int n)
{
	max_elem = n;
	last = 0;
	data = new int[max_elem];
}

my_stack::~my_stack()
{
	delete[] data;
}

int my_stack::top() const
{
	return (last)? data[last - 1] : -1;
}

void my_stack::pop()
{
	if(last)
		--last;	
}

void my_stack::push(int a)
{
	if(last < max_elem)
		data[last++] = a;
	else
	{
		int *new_data = new int[max_elem*2];
		memcpy(new_data, data, max_elem*sizeof(int));
		max_elem *= 2;
		
		delete[] data; 
		data = new_data;
		data[last++] = a;
	}
	
}

int my_stack::size() const
{
	return last;
}

bool my_stack::empty() const 
{
	return !last;
}
А теперь обо всём по порядку.

Цитата:
1) Идеологически, насколько удачная идея для top() при пустом стеке возвращать -1? Вынесено ли это поведение в интерфейс класса? Я думаю, что, как минимум, второго делать не стоит - т.е. в описании метода должно стоять "при пустом стеке поведение метода не определено", а не "при пустом стеке top() возвращает -1".
я долго думал что делать если стек пустой, а мы пытаемся из него выдёргивать значения, либо удалять их. Подумал что можно это дело обернуть exception'ами и плеваться throw, но я ещё про это не прочитал (там целая глава, а я не хочу пробежаться по ней поверхностно), поэтому решил сделать вот так, а как лучше ?? return random() ?

Цитата:
2) Методы top(), size(), empty() следует пометить как константные.
сделал, единственный вопрос тут "правильно ли я их в хереде объявил?"

Цитата:
3) Для размеров (и индексов) в C++ принято использовать тип size_t.
поправил

Цитата:
4) (а вот это серьёзно) memcpy при копировании выходит за пределы массива-источника. Исправить.
поправил, вроде должно работать.

Цитата:
5) (ещё серьёзнее) Не определён и не запрещён конструктор копии, при том, что класс управляет ресурсом (т.е. копирование с помощью memcpy некорректно). Исправить немедленно.
поправил вот таким образом, предварительно прочитав вот эту статью на хабре. Теперь вопрос

почему у автора в коде

Цитата:
NonCopyable( const NonCopyable& ) = delete;
void NonCopyable( const NonCopyable& ) = delete;
конструктор типа void ? лично у меня на это ругался компилятор. А на предыдущую строчку, он выдал warning следующего содержания:
Цитата:
defaulted and deleted functions only available with -std=c++0x or -std=gnu++0x [enabled by default]
как на это реагировать ?? дизейблить прагмой чтобы не мозолило глаза ? PS компилятор g++ сижу и компилю из-под убунты.
Цитата:
6) Память, занимаемая стеком, не уменьшается. Возможно, стоит добавить проверку в pop для случая, когда last << max_elem.
ну да, выделение памяти х2 от предыдущей + копирование, может нехило ударить по производительности. Только как уменьшить объём занимаемой памяти ?? в функцию pop() загнать проверку, по новой выделять память "чуть поменьше" и по новой копировать как в push(), это же расточительно по времени. У нас и так есть одна потенциально тяжеловесная функция push() зачем вторая такая же ?
el_gato_de_Ch вне форума Ответить с цитированием
Старый 21.05.2013, 22:11   #4
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Подумал что можно это дело обернуть exception'ами и плеваться throw, но я ещё про это не прочитал (там целая глава, а я не хочу пробежаться по ней поверхностно), поэтому решил сделать вот так, а как лучше ?? return random() ?
Не-не-не, это точно хуже. Можно возвращать -1, в принципе - главное, не создать у пользователя впечатления, будто вызов top() для пустого стека - не ошибка.
Цитата:
сделал, единственный вопрос тут "правильно ли я их в хереде объявил?"
Да.
Цитата:
поправил
Не до конца. Аргумент второй формы конструктора по-прежнему принимает int, my_stack::size по-прежнему возвращает int.
Цитата:
поправил, вроде должно работать.
Да.
Цитата:
поправил вот таким образом, предварительно прочитав вот эту статью на хабре. Теперь вопрос...
Это синтаксис C++11 (который =delete). В принципе, если не забывать избегать копирования в коде класса (в конце концов, такое встречается нечасто), достаточно просто объявить конструктор копирования и оператор присваивания в закрытой части. "void NonCopyable( const NonCopyable& ) = delete; " - явная опечатка, operator= там должен быть (см. первый комментарий).
Цитата:
ну да, выделение памяти х2 от предыдущей + копирование, может нехило ударить по производительности. Только как уменьшить объём занимаемой памяти ?? в функцию pop() загнать проверку, по новой выделять память "чуть поменьше" и по новой копировать как в push(), это же расточительно по времени. У нас и так есть одна потенциально тяжеловесная функция push() зачем вторая такая же ?
Я загнал в стек 1000000 элементов, затем вытащил 999000 элементов. Стек занимает 4МБ и будет занимать столько до самой своей смерти. Вообще говоря, нехорошо. Попытка в некоторых случаях уменьшать массив действительно ухудшит временные характеристики, но улучшит использование памяти. Это вопрос скорее архитектурный (т.е. ни один вариант не "однозначно лучше" другого) - но тогда в заголовочном файле желательно по крайней мере указать, что стек при извлечении объектов не освобождает память. Чтобы не было сюрпризов.
Abstraction вне форума Ответить с цитированием
Старый 21.05.2013, 22:40   #5
el_gato_de_Ch
Пользователь
 
Регистрация: 21.05.2013
Сообщений: 13
По умолчанию

я, кстати, так и подумал, что там пропущено operator, но всё же решил поинтересоваться,
когда писал стек, я старался реализовать функционал std::stack а у него нет resize(). в конкретной задаче всё сведётся к тому, что нужно будет чаще делать, и если добавлять\убирать из стека, то эффективней будет добавить функцию reserve() для выделения памяти, но так как я писал стек для себя )) мною был выбран вот такой функционал
el_gato_de_Ch вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
реализация стека через односвязный список snusnu Общие вопросы C/C++ 7 06.04.2014 23:59
Реализация стека через массив Quadrelle Паскаль, Turbo Pascal, PascalABC.NET 1 23.04.2013 07:55
Сортировка стека через массив D00M C++ Builder 6 22.05.2012 20:54
Реализация очереди через массив (Delphi) wertret Помощь студентам 2 24.04.2012 02:25
C++, реализация стека OffyGhost Помощь студентам 2 28.03.2010 07:02