[C++] динамический массив в классе

[Rustam]

надо написать класс, который создаёт динамический двумерный массив (желательно чтобы элементы массива не надо было вбивать в ручную ), размерность массива определяет пользователь!
дайте идею в написании (а то читал про классы ничего не понял!)

спасибо!

[Finch]

Пока отбросим классы. Как создается динамический массив?

[Rustam]

как создать динамический массив я знаю
процедуру я написал, он мне выдаёт ошибку:

Type '<имя класса>' may not be defined here

[Sla]

Rustam, код в студию...

[Rustam]

Код:

#include <iostream.h>
#include <assert.h>
#include <conio.h>
#include <alloc.h>
#include <stdio.h>
class graf
{
	int **mas();
 public:
	int n;
	//**mas(void);
	**izmas(int **x, int **z);
	prov();
}
 graf::**mas(void)
{
 int i,j;
 int **z;
 clrscr();
 z=(int**)malloc(n*sizeof(int*));
 for(i=0;j<n;i++)
 {
  z[i]=(int*)malloc(n*sizeof(int*));
  for(j=0;i<n;i++)
  {z[i][j]=0;}
 }
 for (i=0;i<n;i++)
 for (j=0;j<n;i++)
 {
  printf("\nVvedite element matrici A(%d,%d)",i+1,j+1);
  scanf("%d",&z[i][j]);}
 return z;}

void graf::prov()
{
 int i,j,k,kol,nachuz,nachuz2;
 for (i=0,nuchuz=0,kol=0,i<n,i++)
 {
  for (j=0,k=0,j<n,j++)
  if (z[i][j]=1) k+=1;
  if (k%2=1) {kol+=1; if (nachuz=0) nuchuz=i else nachuz2=i;}}
  if (kol=2) {printf("\nLiniya UNIKURSALNA");
	      printf("\nNachat s uzla %d ili %d",nachuz,nachuz2);}
  else printf("LINIYA NE YVLYAETSA UNIKUrSALNOI");
}

void main()
{
 int **a,**b;
 printf("Vvedite kolichestvo uzlov=");
 scanf(&n);
 a=mas(void);
 prov(a);
 free(a);
 getch();
}

[Алексей++]

точно одна ошибка уже есть - не поставлена ";" после class graf{...}

затем,

int** graf::mas(void)
{
}

[Вад]

Rustam, говоришь, умеешь создавать. Но память так выделяется обычно в С, а в C++ есть другой способ - оператор new[]. И потом: а кто будет освобождать всю выделенную память? У тебя освобождается только первый кусок, с указателями на указатели, а блоки, выделяемые под данные, не освобождаются нигде.

Теперь собственно к задаче: класс в данном случае не имеет смысла, если просто умеет создавать массивы (выделять память) - так можно было просто набор функций написать. Смысл задачи, полагаю, в том, чтобы объект класса и был массивом. То есть, содержал бы вот этот указатель в качестве поля - так же, как он у тебя содержит поле размера (n).

Для конструирования (инициализации) экземпляра класса должен быть конструктор. У тебя массив имеет две размерности (в случае массива n*n они равны) - конструктор должен иметь соответствующие параметры и выделять память нужного размера (то, чем у тебя занимается mas).

Где конструктор - там и деструктор. Особенно когда мы говорим о работе с динамической памятью. Деструктор должен освобождать все ресурсы, выделенные под объект (в данном случае - память).

Для доступа к массиву должны быть соответствующие функции (в самом простом варианте - get(x, y) и set(x,y, value) ) - потому что коль скоро это ты решил завести класс, то данные (указатель) принято прятать от окружающего мира. Таким образом, внешний код может совершать над массивом только определённые операции, криминал типа "вручную заменить что-то там" исключается: управление данными осуществляется методами класса, и никак больше.

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

[Rustam]

Спасибо!
Буду думать

[lazy_troll]

Спасибо!
Буду думать

А зачем тебе двухмерный массив?

В плане управления памятью и быстродействия - имхо, будет удобнее представить реализацию класса одномерным массивом с публичными методами set(x,y) и get(x,y)

[Finch]

lazy_troll,   Что лучше, объясни преподавателю. Раз есть задание сделать так, значит нужно.

[Джон]

lazy_troll, стесняюсь спросить, а в чём конкретно преимущество одномерного массива С++ перед двумерным в плане быстродействия и управления памятью? Желательно с примером (для наглядности).

[lazy_troll]

Джон, быстродействие: 2х мерному массиву потребуется считать из массива первого уровня адрес массива второго уровня, а потом уже получить из него данные

В плане управления памятью: очень много возни с выделением и удалением массивов 2 уровня, и Вад уже нашел ошибку в коде

[Finch]

lazy_troll, А что считать? Чтоб посчитать смешение в массиве указателей, достаточно умножить на 4  Замечу, что умножить на 4 довольно быстрое действо. Это всего лиш сдвиг влево на 2 позиции. Выташить указатель на вторую размерность, и считать уже смешение для второй размерности только.
Чтобы работать в одномерном массиве, как в двухмерном. Нужно будет делать два раза умножение. Так что на счет скорости работы, не совсем точное утверждение. Да при этом на иницилизацию и удаление затрачивается чуть больше времени и памяти.

[Вад]

Finch, ещё, если выделять единым куском, возможно, будет профит при кэшировании.

[Finch]

Вад, В принципе, если выделяется память сразу, то есть большой процент вероятности, что все выделенные участки лягут рядом с друг другом. С другой сторону, если имеется массив больше чем кеш процессора, и произвольно гулять по массиву. Там уже без разници, как будет строиться массив.

[Антон (LogRus)]

Finch, я полагаю, господин lazy_troll имел ввиду конструкцию вида

Код:

int ** a;
a = new *int[N];
for(int i =0; i != N; ++i)
  a[i] = new int[M];

[Вад]

Я тут уже как-то предлагал в одной подобной теме в порядке обще-развивающего упражнения:

Код:

int ** a = new int*[N];
a[0] = new int[M*N];
for (int i = 1; i < N; ++i)
    a[i] = a[0] + M*i;

delete[] a[0];
delete[] a;

Но это так, хохмы ради.

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

Finch, если память уже существенно фрагментирована, то не факт. Маленькие куски могут оказаться далеко друг от друга.
В случае произвольного доступа на большом массиве монолитность, конечно, не спасёт, но какой-то эффект тем не менее может дать (особенно если одна строка массива всё-таки меньше линии кэша)

[Rustam]

А зачем тебе двухмерный массив?
В плане управления памятью и быстродействия - имхо, будет удобнее представить реализацию класса одномерным массивом с публичными методами set(x,y) и get(x,y)

У меня по заданию нужно определить является ли линия уникурсальной (что то типа графа Эйлера), по моему там без двумерного массива сложно будет обойтись
а вобще преподу не важна реализация, лишь бы классы были правильны

[lazy_troll]

Rustam, лови тогда реализацию 2д массива + немного кода показывающего его использование:

Код:

#include <iostream>
using namespace std;

class array_2d {
	const int sz;
	int *pdata;
public:
	explicit array_2d(int size): sz(size),
			pdata(new int[size*size]) {};
	~array_2d() {
		delete[] pdata;
	}
	void set(int x,int y,int data) { pdata[x+sz*y]=data ; }
	int get(int x,int y) { return pdata[x+sz*y] ; }
};

int main() {
	array_2d a(10); // создает массив 10*10
	int aa;
	cin>>aa;
	a.set(4,4,aa); //записывает в 4,4
	cout << a.get(4,4) << endl; // prints !!!Hello World!!!
	return 0;
}

[Rustam]

lazy_troll, спасибо большое, выручил!!!

[Алексей++]

explicit array_2d(int size): sz(size),
         pdata(new int[size*size])

жесткодром )
А инициализация - это уже совсем не модно

[Алексей++]

если извращаться, то уж по-научному

Код:

#include <vector>

class array_2d
{
	std::vector<BYTE> m_A;
public:
	array_2d(int size):
	{
		m_A.resize(size*size,0);
	}
	
	BYTE& AT(DWORD x,DWORD y)
	{
		DWORD dwd=x*y;
		if(m_A.size()<dwd)throw 0;
		return m_A[dwd];
	}
};

[Вад]

Код:

array_2d(int size):
{
	m_A.resize(size*size,0);
}

- а почему тогда уж не

Код:

array_2d(int size)
: m_A(size*size, 0)
    {}

?

и, в довесок:

Код:

	BYTE& AT(DWORD x,DWORD y)
	{
		return m_A.at(x*y);
	}

[Алексей++]

двоеточие у меня - очепятка, не компилировал )

А разницу между at и [] не вижу. А есть, кстати ?

[Вад]

А разницу между at и [] не вижу. А есть, кстати ?

[] не выполняет проверку границ (только ассерты есть в отладочных реализациях), а at генерирует исключение out_of_range. То есть, делает то, что ты для [] написал руками

ЗЫ. В первом примере я акцентировал внимание на том, что вектор можно конструировать не по умолчанию, а специальным конструктором, с указанием размера и значения.

[Алексей++]

понятно ))

[Антон (LogRus)]

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

[Алексей++]

LogRus, ты "бы" переделал, а мы взяли и переделали  

[Антон (LogRus)]

Алексей1153++, я бы переделал, на шаблон, не потому, что меня не устраивает динамический массив, а потому, что небольшие массивы эффективней создавать на стеке и шаблоны тут очень кстати.
я вообще вектор не люблю он мне тупо не нравится

[Алексей++]

а мне понравился тем, что удобно в качестве мемберов класса делать, когда динамические массивы нужны

[Вад]

Алексей1153++, Вад, не понял чего вам не понравилось

А мне не не понравилось Это раз уж Лёша начал по-научному извращаться, то я свои пять копеек вставил.

[RXL]

Таки что порекомендуете использовать вместо std::vector, когда нужен динамический массив?

[Алексей++]

так можно и динамический массив. Но это возня с выделением и удалением в конструкторе/деструкторе и в других местах класса. А вектор объявил и почти забыл

[Антон (LogRus)]

RXL, я предпочитаю дек для хранения крупных объектов, а вектор в основном, как промежуточное хранилище для передачи по сети сложных объектов
вообще каждый случай индивидуален, поэтому ....
вектор я не люблю использовать из повышенных требований к наличию непрерывного блока памяти, когда у тебя данных сотни мегабайт, это может быть важно
push_back приводит к реалокациям, а реалокация на фоне new в соседнем потоке фрагментирует память
вообще, я его недолюбливаю из-за особенностей моей работы, а не от того что он весь такой плохой
просто мне он неподходит

[Алексей++]

push_back приводит к реалокациям,

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

[Антон (LogRus)]

можно, но не всегда удобно, особенно, если ты не знаешь сколько данных будет загружено и они могут загружаться после начальной загрузки в неограниченном объёме

[Алексей++]

LogRus, ну это как раз уже то, что "другая задача"

[RXL]

Код:

selectedWorkers.erase(std::find(selectedWorkers.begin(), selectedWorkers.end(), key));

Здесь selectedWorkers представляет собой std::CONTAINER<int>. Задача - удалить элемент со значением key из списка.

Попробовал заменить CONTAINER c vector на deque и получил ошибку компиляции:

template argument _InputIter passed to 'find' is a output iterator: input iterator required

Не пойму, что я тут не так сделал... Вроде как deque имеет тот же интерфейс, что и vector, но немного расширенный для работы с началом списка.

UPD: отбой - это предупреждения, а не ошибки. Видимо в BCB6 кривая реализация STL.

[Алексей++]

Код:

#include <deque>
#include <algorithm>

std::deque<int> selectedWorkers;

selectedWorkers.erase(std::find(selectedWorkers.begin(), selectedWorkers.end(), 7));

а у меня скомпилировалось

[Rustam]

не отходите далеко от темы ребята =)

[Антон (LogRus)]

RXL, что за компилятор и STL?

если тебе нужно добавлять и удалять числа, то может просто использовать set?

[Антон (LogRus)]

Rustam, ну проблему решили можно и поболтать

[RXL]

LogRus, не, мне нужен упорядоченный список. Выше я написал - это оказалось некритичным предупреждением. Сейчас попробую, как работает.

Замена vector на deque у меня работает.

[Антон (LogRus)]

LogRus, не, мне нужен упорядоченный список. Выше я написал - это оказалось некритичным предупреждением. Сейчас попробую, как работает.

Замена vector на deque у меня работает.

ну у меня предупреждений
а кто сказал, что set нельзя как упорядоченный список использовать?

[RXL]

LogRus, пока не вижу в описании std::set, что это упорядоченный список...

[Антон (LogRus)]

Код:

std::set<int> s;
for(std::set<int>::iterator it=s.begin(); it != s.end(); ++it)
{
   ................
}

так вот: итератор возвращает элементы в порядке возрастания
чем не список?

пример: http://cplusplus.com/reference/stl/set/begin/

[RXL]

Наверно я не так выразился: под упорядоченным я имел в виду не сортированный, а в порядке помещения элементов в контейнер. Ассоциативные контейнеры не могут обеспечить тот же порядок без дополнительной поддержки.

[Антон (LogRus)]

стоп, если он не отсортированный, то код не рабочий

Код:

selectedWorkers.erase(std::find(selectedWorkers.begin(), selectedWorkers.end(), 7));

[RXL]

С чего бы он вдруг стал нерабочий?

1. std::find(selectedWorkers.begin(), selectedWorkers.end(), 7)
Возвращает итератор, указывающий на элемент со значением 7.

2. selectedWorkers.erase(.....)
Удаляет элемент по итератору.

Все согласно спецификации STL для последовательных контейнеров.
Кстати, работает.

[Антон (LogRus)]

потому, что find работает, только с отсортированными диапазонами

[Антон (LogRus)]

а нет гоню, find работает любых массивах т.к. он использует простой перебор элементов, что ИМХО ацтой, хотя задачи бывают разные

[Алексей++]

LogRus, хм, вот только хотел написать, что с вполне неупорядоченным вектором find работает ))

[Антон (LogRus)]

давно не пользовался, всё больше индексы и ассоциативные контейнеры, уже и забыл про простой перебор

[RXL]

Пока я тут читал доки, вы уже разобрались...
Но, все же, чтобы добру не пропадать привожу тест.

Код:

#include <stdio.h>
#include <vector>
#include <algorithm>

typedef std::vector<int> list_int_t;

void print_list(list_int_t &list)
{
    list_int_t::iterator it;

    for (it = list.begin(); it != list.end(); it++)
        printf("%d ", *it);

    puts("");
}

int main()
{
    list_int_t list;

    // Заполняем список.
    list.push_back(5);
    list.push_back(4);
    list.push_back(3);
    list.push_back(7);
    list.push_back(2);
    list.push_back(8);
    list.push_back(1);
    list.push_back(7);

    // Выводим начальное состояние списка.
    puts("Вывод содержимого списка (1)");
    print_list(list);

    // Удаляем элемент со значением 7.
    list.erase(find(list.begin(), list.end(), 7));

    // Выводим конечное состояние списка.
    puts("Вывод содержимого списка (2)");
    print_list(list);

    return 0;
}

Код:

$ g++ -Wall -o t2 t2.cpp
$ ./t2

Код:

Вывод содержимого списка (1)
5 4 3 7 2 8 1 7
Вывод содержимого списка (2)
5 4 3 2 8 1 7

У меня под рукой книженция "STL. Карманный справочник." (ISBN 5-469-00389-2):

Некоторое количество алгоритмов требует отсортированных интервалов или иначе использует функции сравнения для проверки отношений «меньше». ...

Не знаю, может это имеет отношение к нашему вопросу...

[RXL]

Я тоже предпочитаю map, но если нет уникального ключа или нужен определенный порядок хранения, то использую vector (теперь уже deque).

[Вад]

Я тоже предпочитаю map, но если нет уникального ключа или нужен определенный порядок хранения, то использую vector (теперь уже deque).

Для таких случаев есть multiset и multimap, не требующие уникального ключа.

[RXL]

Но с ними не так удобно работать, как с map и vector. Затрудняюсь найти им применение в своей практике.

[Алексей++]

я multimap применял, когда в качестве ключа использовалось время. Могло повторяться )