Форум программистов, компьютерный форум CyberForum.ru

Union - Объединения - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.67
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
21.09.2012, 17:49     Union - Объединения #1
Объясните доходчиво что такое Объединения и для какой работы они нужны.
Несколько книг листал а про объединения толком ничего не сказано и нет примеров почти. Везде одно и тоже:
пример с переменными разных типов и выводом их значений при объявлении каждой...

Что-нибудь более реальное к жизни что ли хотелось бы увидеть. Ну как минимум это union и структуры, или классы.
И если кто видел книгу в которой доходчиво рассказывается про union дайте пожалуйста название этой книги.
Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.09.2012, 17:49     Union - Объединения
Посмотрите здесь:

C++ Объединения (union)
Union C++
union с методами C++
Union C++
C++ Управляемый value union
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Invader_Zim
Twilight Parasite
 Аватар для Invader_Zim
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
21.09.2012, 17:52     Union - Объединения #2
Elfenlide, K&R! так как юнионы, энумы и структуры это наследие няшного Си!
Infinity3000
 Аватар для Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
21.09.2012, 17:54     Union - Объединения #3
ОБЪЕДИНЕНИЯ
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
21.09.2012, 18:18  [ТС]     Union - Объединения #4
Цитата Сообщение от Invader_Zim Посмотреть сообщение
Elfenlide, K&R! так как юнионы, энумы и структуры это наследие няшного Си!
K&R! - это как понимать?)
Дайте нормальную книгу или может сайт с хорошими примерами.
Ссылка что дали выше ,я там был, и совсем не понимаю зачем что и почему.....как бы понятно, что можно выводить в разных типах одно значение, но неужели юнион используют только для того чтобы
выполнять задачи подобные этой:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    #include <iostream.h>
 
    void main(void)
 
    {
       union distance
 
       {
          int miles;
          long meters;
       } walk;
 
       walk.miles = 5;
       cout << "Пройденное расстояние в милях " << walk.miles << endl;
       walk.meters = 10000;
       cout << "Пройденное расстояние в метрах " << walk.meters << endl;
    }
Расскажу в чём дело, у меня в универе 2 курс есть предмет ППвИС, и дали мне первую лабу реализовать класс Set и основные операции над множествами, не использую STL, я сделал всё кроме одного пункта: Множеств может являться элементом другого множества.
Как это сделать я не представляю себе. Препод сказал используй "Объединения Union", я посмотрел что там к чему, и ничего не понял, препод мне объяснил тоже что и на сайт указанном выше, хотя это мне понятно. Непонятно как юнион в моей ситуации может помочь. он сказал использовать можно юнион и массив структур.. дал небольшой фрагмент который от руки набросал за минуту, сказал пару умных слов и я так и ничего не понял...ну, кроме мелочей которые итак ясны....
это то что он мне написал:
C++
1
2
3
4
5
6
7
8
union element{
char* el;
Set* s;
}
struct Set_Element{
enum ElType{ATOM,SET};
int type;
Element el;
откуда тут Set* s; мне непонятно....ибо set это должно быть либо класс либо структура как я понимаю....ну и что тут к чему...не совсем понятно....зачем тут перечисление тоже не понял....на мои вопросы он ответил видимо слишком умно, для моих знаний\
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
21.09.2012, 18:19     Union - Объединения #5
Invader_Zim, Ага, только вот union в C++11 вышел далеко за рамки данного наследия.
Invader_Zim
Twilight Parasite
 Аватар для Invader_Zim
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
21.09.2012, 18:30     Union - Объединения #6
ForEveR, что не использую, о том не говорю. Времени с новым стандартом разобраться ,к сожалению, нет.
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
21.09.2012, 21:01  [ТС]     Union - Объединения #7
Цитата Сообщение от ForEveR Посмотреть сообщение
Invader_Zim, Ага, только вот union в C++11 вышел далеко за рамки данного наследия.
Это всё замечательно,но может кто-нибудь мне сможет всё-таки объяснить, а-то разговоров об этом много а что это и зачем, непонятно
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
21.09.2012, 21:16     Union - Объединения #8
Окей, суть в чём: юнион позволяет хранить несколько величин (в данном случае величины типов нормальный-элемент-множества и множество-как-элемент-множества) в одном куске памяти. То есть одну и ту же переменную юнион-типа можно трактовать и как один из хранимых типов, и как другой.

Применительно к данному случаю юнион тут как собаке пятая лапа, но раз уж сказано. (Вообще стоит делать внутри несколько контейнеров "для нормальных", "для множеств", "для другой-третий-тип".)

Идею вы поняли правильно (шаблонами не гружу):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct SetElement {
  enum { ATOM, SET } type; // токен типа, содержащий тип текущих хранимых данных
  
  // Собсно данные: или атом, или множество. Фишка в том, что можно хранить или
  // множество, или атом. Если достать что-то другое, то получим мусор и вообще капец.
  // Всё из-за того, что хранятся они в одном и том же месте памяти.
  //
  // Хранить сразу значения или указатели на них, решайте сами, тут однозначно не скажешь.
  union {
    char atom;
    Set set;
  };
 
  SetElement(char value)
  {
    atom = value;
    type = ATOM;
  }
 
  SetElement(const Set &value)
  {
    set = value;
    type = SET;
  }
 
  SetElement& operator=(char value)
  {
    atom = value;
    type = ATOM;
    return *this;
  }
 
  SetElement& operator=(const Set &value)
  {
    set = value;
    type = SET;
    return *this;
  }
 
  bool operator==(const SetElement &other)
  {
    if (this->type != other.type) {
      return false;
    }
    else {
      if (this->type == ATOM) {
        return this->atom == other.atom;
      }
      else {
        return this->set == other.set;
      }
    }
  }
};
В итоге можно делать вот так:
C++
1
2
3
4
5
6
SetElement element1('x'); // элемент-атом
SetElement element2(someSet); // элемент-множество
if (element1.type == SetElement::ATOM) { // можно сделать методы isAtom() и isSet()
  std::cout << element1.atom;
}
element1 = element2; // element1 теперь тоже элемент-множество
К сожалению, придётся руками смотреть на тайп-токен, чтобы понять, какого типа этот элемент, и как его доставать: через .atom или через .set. В принципе, можно добавить сверху методы asAtom() и asSet(), которые будут ругаться, если типы не совпадают, и спрятать все эти поля внутрь, но это уж как хотите.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.09.2012, 21:21     Union - Объединения #9
хотел бы уточнить у знающих:
union разве может не POD типы содержать? множество какое-то например.
старый стандарт?
новый стандарт?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
21.09.2012, 21:45     Union - Объединения #10
Цитата Сообщение от DU Посмотреть сообщение
хотел бы уточнить у знающих:
union разве может не POD типы содержать? множество какое-то например.
старый стандарт?
новый стандарт?
В старом может, но с дикими ограничениями: никаких своих конструкторов и деструкторов, никаких виртуальных функций и не трогать стандартный оператор copy-assign (Type::operator=(const Type&)). Так что тот мой пример выше наверняка не сработает :) По крайней мере, если хранить множество не как указатель.

В новом ограничение снято, но при условии, что все эти функции реализуются руками для юниона, если они нужны. (Ну и список, естессно, расширился move-конструктором/присваиванием.)
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
21.09.2012, 21:54     Union - Объединения #11
Infinity3000,
посмотрел я на твою ссылку и пригорюнился
одна эта фраза
Как вы узнаете, объединения очень похожи на структуры,


Elfenlide,
попытаюсь объяснить своими словами
Объединения используют когда одни и те же данные нужно выразить разным способом
например(куски реальной программы для работы с контроллера с USB)
хост посылает контроллеру данные упакованные вот в такую структуру
C++
1
2
3
4
5
6
7
typedef struct{ 
  byte bmRequestType;//0
  byte bRequest;     //1
  word wValue;       //2-3
  word wIndex;       //4-5
  word wLength;      //6-7
} SETUP_PACKET;
иногда нужно значение первых 2 элементов вместе
их удобно объединить
C++
1
word         wRequest;
но хост посылает последовательно 8 байт и как их вписать в слово word wValue;?
и тут приходит на помощь объединение

C++
1
2
3
4
5
6
typedef union
{
  SETUP_PACKET setup;
  byte         b[8];
  word         wRequest;
} UsbSetupPacket;
т.е одни и те же данные можно представить
массив из 8 байтов
структуру SETUP_PACKET
и слово wRequest(используются два первых байта)

и работаем
C++
1
UsbSetupPacket SetupPacket;
при получении данных нам удобней работать с массивом
C++
1
2
  for (i=0; i<8; i++)
   SetupPacket.b[i]= Usb_read_byte();
при анализе пакета с wRequest;
C++
1
2
3
  switch (SetupPacket.wRequest)  
  {
    case GET_STATUS_DEVICE:
а для обработки со структурой

C++
1
2
3
 if (SetupPacket.setup.wValue ==0x00  )     //  FEATURE_ENDPOINT_HALT
      {
       wIndex = (SetupPacket.setup.wIndex & 0x7F );
так же можешь разложить int на массив char
C++
1
2
3
4
5
union
  {
   ArrChar char[4];
   Value int; 
  }
в зависимости от элемента будешь работать или с массивом байт или с числом
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
22.09.2012, 00:01  [ТС]     Union - Объединения #12
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
В старом может, но с дикими ограничениями: никаких своих конструкторов и деструкторов, никаких виртуальных функций и не трогать стандартный оператор copy-assign (Type::operator=(const Type&)). Так что тот мой пример выше наверняка не сработает :) По крайней мере, если хранить множество не как указатель.

В новом ограничение снято, но при условии, что все эти функции реализуются руками для юниона, если они нужны. (Ну и список, естессно, расширился move-конструктором/присваиванием.)
Спасибо большое, теперь уже более менее понятно, думаю сам уже на практике доработаю.
Ещё один вопрос:
Откуда такие знания?)Дело в том что я смотрел несколько книг разных по С++, и везде один пример на ввод и вывод элементов разного типа, и просто синтаксис объявления, а толкового ничего нету.Какие книги вы посоветуете может из тех в которых можно полноценно черпать информацию?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
22.09.2012, 00:06     Union - Объединения #13
Естессно, я не помню наизусть тонкости. Интересуют тонкости — открываем стандарт (новый) и читаем. Вот оттуда я и вычитал про конкретные ограничения (так-то только смутно помню, что туда засунуть можно только классы, которые не особо круче сишных структур).
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
22.09.2012, 00:11  [ТС]     Union - Объединения #14
Цитата Сообщение от ValeryS Посмотреть сообщение
Infinity3000,
посмотрел я на твою ссылку и пригорюнился
одна эта фраза
Спасибо большое
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
22.09.2012, 00:26     Union - Объединения #15
Цитата Сообщение от Elfenlide Посмотреть сообщение
Откуда такие знания?)Дело в том что я смотрел несколько книг разных по С++, и везде один пример на ввод и вывод элементов разного типа,
если вопрос к ~OhMyGodSoLong~, то он уже ответил
а если ко мне то отвечу словами Гете
"Теория без практики мертва, а вечно зелено лишь древо жизни"
изучай побольше исходников , задавай вопросы, ну и книги тоже читай но отбрасывай ненужное

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

не это
Цитата Сообщение от Elfenlide Посмотреть сообщение
union distance
{
int miles;
long meters;
} walk;
а нормальное например как я привел, понял их силу

а с учебниками особенно с нашими будь осторожней
недавно тема проскакивала
привели методичку 2012 для работы с BC 3.1( лет десять наверно тупо перепечатывали)
смотри переводную литературу, а если знания позволяют читай в оригинале
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
22.09.2012, 00:56  [ТС]     Union - Объединения #16
Цитата Сообщение от ValeryS Посмотреть сообщение
если вопрос к ~OhMyGodSoLong~, то он уже ответил
а если ко мне то отвечу словами Гете
"Теория без практики мертва, а вечно зелено лишь древо жизни"
изучай побольше исходников , задавай вопросы, ну и книги тоже читай но отбрасывай ненужное

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

не это

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

а с учебниками особенно с нашими будь осторожней
недавно тема проскакивала
привели методичку 2012 для работы с BC 3.1( лет десять наверно тупо перепечатывали)
смотри переводную литературу, а если знания позволяют читай в оригинале
Собственно так и делаю, пока Лафоре изучаю шаг за шагом, и думаю ещё пробежаться потом по Харви и Пол Дэйтлы, ну а после страуструпа чтоли.
К сожалению я не мог въехать в объединения как раз-таки по причине того что сколько ни искал, толком не нашёл нормального примера с union или если находил то там небыло комментариев и код слижком сложный для моего уровня.
Ещё раз спасибо огромное всем за помощь!

Добавлено через 21 минуту
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Естессно, я не помню наизусть тонкости. Интересуют тонкости — открываем стандарт (новый) и читаем. Вот оттуда я и вычитал про конкретные ограничения (так-то только смутно помню, что туда засунуть можно только классы, которые не особо круче сишных структур).
А вы не могли бы свой пример который писали доработать так чтобы он компилировался, чтоб уже от рабочего изучать, ато тут ошибок много выбивает, и в union у вас стоит Set set; но ведь структуры или класса Set небыло вообще создано...Если вам не сложно доработайте пожалуйста.И вы писали что union для решения такого типа задачи не нужны,а каким ещё спсобом можно решить такую задачу не используя STL ?
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
22.09.2012, 01:24     Union - Объединения #17
Цитата Сообщение от Elfenlide Посмотреть сообщение
класса Set небыло вообще создано...
в твоем примере как раз все ясно
Цитата Сообщение от Elfenlide Посмотреть сообщение
union element{
char* el;
Set* s;
}
если возьмешь вот так
element.s будет указатель на структуру
если так element.el указатель на байты
вот пришло в голову
это не рабочий пример а мысли вслух
распечатать дамп памяти который занимает структура(или класс)
C++
1
2
3
4
Set st;
element.s=&st
for(int i=0;i<sizeof(st);i++)
   printf("0x%x  ",element.el[i]);
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
22.09.2012, 01:42  [ТС]     Union - Объединения #18
Цитата Сообщение от ValeryS Посмотреть сообщение
в твоем примере как раз все ясно

если возьмешь вот так
element.s будет указатель на структуру
если так element.el указатель на байты
вот пришло в голову
это не рабочий пример а мысли вслух
распечатать дамп памяти который занимает структура(или класс)
C++
1
2
3
4
Set st;
element.s=&st
for(int i=0;i<sizeof(st);i++)
   printf("0x%x  ",element.el[i]);
Препод не под меня код писал,не под мою прогу, а просто мысли в слух)
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
22.09.2012, 02:33     Union - Объединения #19
Цитата Сообщение от Elfenlide Посмотреть сообщение
А вы не могли бы свой пример который писали доработать так чтобы он компилировался, чтоб уже от рабочего изучать, ато тут ошибок много выбивает, и в union у вас стоит Set set; но ведь структуры или класса Set небыло вообще создано...Если вам не сложно доработайте пожалуйста.
Я б делал так. (Осторожно, впереди кирпич.)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
#include <vector>
#include <iostream>
 
template <typename T>
class Set {
public:
  Set();
  Set(const Set<T> &other);
 
  // добавление
  Set<T>& add(const T &element);
  Set<T>& add(const Set<T> &set);
 
  // проверка вхождения
  bool contains(const T &element);
  bool contains(const Set<T> &set);
 
  // проверка вхождения и в хранимых подмножествах
  bool deepContains(const T &element);
  bool deepContains(const Set<T> &set);
 
  bool operator==(const Set<T> &other);
 
  template <class R>
  friend
  std::ostream& operator<<(std::ostream &stream, const Set<R> &set);
 
private:
  struct SetElement {
    enum { ATOM, SET } type;
    union {
      T atom;
      Set<T> *set; // <- хранится как указатель
    };
 
    SetElement(const T &element);
    SetElement(const Set<T> &set);
    SetElement(const Set<T>::SetElement &other);
    ~SetElement();
 
    bool operator==(const Set<T>::SetElement &other);
    bool operator==(const T &element);
    bool operator==(const Set<T> &set);
  };
 
  // Вообще стоит сделать что-то умнее вектора. Обычно тут
  // используется какое-нибудь самобалансирующееся дерево,
  // чтобы время на поиск вхождения было минимальным.
  std::vector<SetElement> data;
 
  static void printout(std::ostream &stream, const Set<T>::SetElement &element);
};
 
template <class T>
Set<T>::SetElement::SetElement(const T &element)
{
  type = ATOM;
  atom = element;
}
 
template <class T>
Set<T>::SetElement::SetElement(const Set<T> &set)
{
  type = SET;
  this->set = new Set<T>(set);
}
 
template <class T>
Set<T>::SetElement::SetElement(const Set<T>::SetElement &other)
{
  this->type = other.type;
  if (type == ATOM) {
    atom = other.atom;
  }
  else {
    // Полностью копируем хранимое внутри множество
    this->set = new Set<T>(*(other.set));
  }
}
 
// Так как элементы-подмножества хранятся как указатели,
// то их необходимо убивать вручную. Блааго, vector вызывает
// деструкторы, так что из самого Set<T> всё удалится
// автоматически.
template <class T>
Set<T>::SetElement::~SetElement()
{
  if (type == SET) {
    delete set;
  }
}
 
template <class T>
bool Set<T>::SetElement::operator==(const Set<T>::SetElement &other)
{
  if (this->type != other.type) {
    return false;
  }
  else {
    if (this->type == ATOM) {
      return this->atom == other.atom;
    }
    else {
      return *(this->set) == *(other.set);
    }
  }
}
 
template <class T>
bool Set<T>::SetElement::operator==(const T &element)
{
  if (type != ATOM) {
    return false;
  }
  else {
    return atom == element;
  }
}
 
template <class T>
bool Set<T>::SetElement::operator==(const Set<T> &set)
{
  if (type != SET) {
    return false;
  }
  else {
    return *(this->set) == set;
  }
}
 
template <class T>
Set<T>::Set()
{}
 
// vector сам повызывает конструкторы копирования и сделает deep-copy
template <class T>
Set<T>::Set(const Set<T> &other)
  : data(other.data)
{}
 
template <class T>
Set<T>& Set<T>::add(const T &element)
{
  if (!contains(element)) {
    data.push_back(SetElement(element));
  }
  return *this;
}
 
template <class T>
Set<T>& Set<T>::add(const Set<T> &set)
{
  if (!contains(set)) {
    data.push_back(SetElement(set));
  }
  return *this;
}
 
template <class T>
bool Set<T>::contains(const T &element)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i] == element) {
      yes = true;
      break;
    }
  }
  return yes;
}
 
template <class T>
bool Set<T>::contains(const Set<T> &set)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i] == set) {
      yes = true;
      break;
    }
  }
  return yes;
}
 
template <class T>
bool Set<T>::deepContains(const T &element)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i].type == Set<T>::SetElement::ATOM) {
      if (data[i] == element) {
        yes = true;
        break;
      }
    }
    else {
      // Если наткнулись на множество, то рекурсивно проверяем,
      // есть ли искомый внутри него.
      if (data[i].set->deepContains(element)) {
        yes = true;
        break;
      }
    }
  }
  return yes;
}
 
template <class T>
bool Set<T>::deepContains(const Set<T> &set)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i].type == Set<T>::SetElement::SET) {
      // На элементы-значения можно вообще не смотреть,
      // а для множеств искомое может быть как равно им,
      // так и быть внутри них.
      if ((data[i] == set) || (data[i].set->deepContains(set))) {
        yes = true;
        break;
      }
    }
  }
  return yes;
}
 
// Офигенно медленная O(n^2) реализация сравнения,
// но сойдет как иллюстрация.
template <class T>
bool Set<T>::operator==(const Set<T> &other)
{
  if (this->data.size() != other.data.size()) {
    return false;
  }
  else {
    bool okay = true;
    for (int i = 0; i < data.size(); ++i) {
      if (other.data[i].type == Set<T>::SetElement::ATOM) {
        if (!contains(other.data[i].atom)) {
          okay = false;
          break;
        }
      }
      else {
        if (!contains(*(other.data[i].set))) {
          okay = false;
          break;
        }
      }
    }
    return okay;
  }
}
 
template <class T>
std::ostream& operator<<(std::ostream &stream, const Set<T> &set)
{
  bool first = true;
  stream << "{";
  for (int i = 0; i < set.data.size(); ++i) {
    if (!first) {
      stream << ", ";
    }
    Set<T>::printout(stream, set.data[i]);
    first = false;
  }
  stream << "}";
  return stream;
}
 
template <class T>
void Set<T>::printout(std::ostream &stream, const typename Set<T>::SetElement &element)
{
  if (element.type == Set<T>::SetElement::ATOM) {
    stream << element.atom;
  }
  else {
    stream << *(element.set);
  }
}
 
int main()
{
  Set<int> set1;
  set1.add(1).add(2).add(3).add(1);
 
  std::cout << "set1 = " << set1 << "\n";
  for (int i = 0; i < 5; ++i) {
    std::cout << "set1 contains(" << i << ") => " << set1.contains(i) << "\n";
  }
  std::cout << "\n";
 
  Set<int> set2;
  set2.add(9).add(set1);
  std::cout << "set2 = " << set2 << "\n";
  std::cout << "set2 contains(1) => " << set2.contains(1) << "\n"
            << "set2 contains(9) => " << set2.contains(9) << "\n"
            << "set2 contains(2) => " << set2.contains(2) << "\n"
            << "set2 deepContains(2) => " << set2.deepContains(2) << "\n"
            << "set2 contains(set1) => " << set2.contains(set1) << "\n"
            << "set2 deepContains(set1) => " << set2.deepContains(set1) << "\n";
  std::cout << "\n";
 
  Set<int> set3;
  set3.add(3).add(2).add(1);
  std::cout << "set3 = " << set3 << "\n";
  std::cout << "set1 == set3 => " << (set1 == set3) << "\n";
  std::cout << "\n";
 
  Set<int> set4;
  set4.add(set3).add(9);
  std::cout << "set4 = " << set4 << "\n";
  std::cout << "set2 == set4 => " << (set2 == set4) << "\n";
  std::cout << "\n";
}
Цитата Сообщение от Elfenlide Посмотреть сообщение
И вы писали что union для решения такого типа задачи не нужны,а каким ещё спсобом можно решить такую задачу не используя STL ?
Ну вот у есть есть внутри множества какой-нибудь std::vector<SetElement> или что там, коллекция элементов, короче. Каждый SetElement может быть как атомом, так и множеством. Беда с этим юнионом, что, во-первых, статически не понять (принципиально), там лежит атом или множество, а во-вторых, туда не всякий класс засунешь, а хотелось бы не жонглировать указателями (но это не так сложно.)

Поэтому можно сделать два вектора: std::vector<AtomicType> и std::vector<Set>. Первый хранит все элементы-атомы, второй — множества. Меньше динамических проверок типов и чуть быстрее поиск, просто потому, что мы уверены, что если нам надо искать число, то мы его ищем среди чисел, а не среди включённых в множество подмножеств. И наоборот, если мы ищем множество, то тоже знаем, где его искать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.09.2012, 08:41     Union - Объединения
Еще ссылки по теме:

Union, struct C++
Union C++
Тип объединения union C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
22.09.2012, 08:41  [ТС]     Union - Объединения #20
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Я б делал так. (Осторожно, впереди кирпич.)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
#include <vector>
#include <iostream>
 
template <typename T>
class Set {
public:
  Set();
  Set(const Set<T> &other);
 
  // добавление
  Set<T>& add(const T &element);
  Set<T>& add(const Set<T> &set);
 
  // проверка вхождения
  bool contains(const T &element);
  bool contains(const Set<T> &set);
 
  // проверка вхождения и в хранимых подмножествах
  bool deepContains(const T &element);
  bool deepContains(const Set<T> &set);
 
  bool operator==(const Set<T> &other);
 
  template <class R>
  friend
  std::ostream& operator<<(std::ostream &stream, const Set<R> &set);
 
private:
  struct SetElement {
    enum { ATOM, SET } type;
    union {
      T atom;
      Set<T> *set; // <- хранится как указатель
    };
 
    SetElement(const T &element);
    SetElement(const Set<T> &set);
    SetElement(const Set<T>::SetElement &other);
    ~SetElement();
 
    bool operator==(const Set<T>::SetElement &other);
    bool operator==(const T &element);
    bool operator==(const Set<T> &set);
  };
 
  // Вообще стоит сделать что-то умнее вектора. Обычно тут
  // используется какое-нибудь самобалансирующееся дерево,
  // чтобы время на поиск вхождения было минимальным.
  std::vector<SetElement> data;
 
  static void printout(std::ostream &stream, const Set<T>::SetElement &element);
};
 
template <class T>
Set<T>::SetElement::SetElement(const T &element)
{
  type = ATOM;
  atom = element;
}
 
template <class T>
Set<T>::SetElement::SetElement(const Set<T> &set)
{
  type = SET;
  this->set = new Set<T>(set);
}
 
template <class T>
Set<T>::SetElement::SetElement(const Set<T>::SetElement &other)
{
  this->type = other.type;
  if (type == ATOM) {
    atom = other.atom;
  }
  else {
    // Полностью копируем хранимое внутри множество
    this->set = new Set<T>(*(other.set));
  }
}
 
// Так как элементы-подмножества хранятся как указатели,
// то их необходимо убивать вручную. Блааго, vector вызывает
// деструкторы, так что из самого Set<T> всё удалится
// автоматически.
template <class T>
Set<T>::SetElement::~SetElement()
{
  if (type == SET) {
    delete set;
  }
}
 
template <class T>
bool Set<T>::SetElement::operator==(const Set<T>::SetElement &other)
{
  if (this->type != other.type) {
    return false;
  }
  else {
    if (this->type == ATOM) {
      return this->atom == other.atom;
    }
    else {
      return *(this->set) == *(other.set);
    }
  }
}
 
template <class T>
bool Set<T>::SetElement::operator==(const T &element)
{
  if (type != ATOM) {
    return false;
  }
  else {
    return atom == element;
  }
}
 
template <class T>
bool Set<T>::SetElement::operator==(const Set<T> &set)
{
  if (type != SET) {
    return false;
  }
  else {
    return *(this->set) == set;
  }
}
 
template <class T>
Set<T>::Set()
{}
 
// vector сам повызывает конструкторы копирования и сделает deep-copy
template <class T>
Set<T>::Set(const Set<T> &other)
  : data(other.data)
{}
 
template <class T>
Set<T>& Set<T>::add(const T &element)
{
  if (!contains(element)) {
    data.push_back(SetElement(element));
  }
  return *this;
}
 
template <class T>
Set<T>& Set<T>::add(const Set<T> &set)
{
  if (!contains(set)) {
    data.push_back(SetElement(set));
  }
  return *this;
}
 
template <class T>
bool Set<T>::contains(const T &element)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i] == element) {
      yes = true;
      break;
    }
  }
  return yes;
}
 
template <class T>
bool Set<T>::contains(const Set<T> &set)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i] == set) {
      yes = true;
      break;
    }
  }
  return yes;
}
 
template <class T>
bool Set<T>::deepContains(const T &element)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i].type == Set<T>::SetElement::ATOM) {
      if (data[i] == element) {
        yes = true;
        break;
      }
    }
    else {
      // Если наткнулись на множество, то рекурсивно проверяем,
      // есть ли искомый внутри него.
      if (data[i].set->deepContains(element)) {
        yes = true;
        break;
      }
    }
  }
  return yes;
}
 
template <class T>
bool Set<T>::deepContains(const Set<T> &set)
{
  bool yes = false;
  for (int i = 0; i < data.size(); ++i) {
    if (data[i].type == Set<T>::SetElement::SET) {
      // На элементы-значения можно вообще не смотреть,
      // а для множеств искомое может быть как равно им,
      // так и быть внутри них.
      if ((data[i] == set) || (data[i].set->deepContains(set))) {
        yes = true;
        break;
      }
    }
  }
  return yes;
}
 
// Офигенно медленная O(n^2) реализация сравнения,
// но сойдет как иллюстрация.
template <class T>
bool Set<T>::operator==(const Set<T> &other)
{
  if (this->data.size() != other.data.size()) {
    return false;
  }
  else {
    bool okay = true;
    for (int i = 0; i < data.size(); ++i) {
      if (other.data[i].type == Set<T>::SetElement::ATOM) {
        if (!contains(other.data[i].atom)) {
          okay = false;
          break;
        }
      }
      else {
        if (!contains(*(other.data[i].set))) {
          okay = false;
          break;
        }
      }
    }
    return okay;
  }
}
 
template <class T>
std::ostream& operator<<(std::ostream &stream, const Set<T> &set)
{
  bool first = true;
  stream << "{";
  for (int i = 0; i < set.data.size(); ++i) {
    if (!first) {
      stream << ", ";
    }
    Set<T>::printout(stream, set.data[i]);
    first = false;
  }
  stream << "}";
  return stream;
}
 
template <class T>
void Set<T>::printout(std::ostream &stream, const typename Set<T>::SetElement &element)
{
  if (element.type == Set<T>::SetElement::ATOM) {
    stream << element.atom;
  }
  else {
    stream << *(element.set);
  }
}
 
int main()
{
  Set<int> set1;
  set1.add(1).add(2).add(3).add(1);
 
  std::cout << "set1 = " << set1 << "\n";
  for (int i = 0; i < 5; ++i) {
    std::cout << "set1 contains(" << i << ") => " << set1.contains(i) << "\n";
  }
  std::cout << "\n";
 
  Set<int> set2;
  set2.add(9).add(set1);
  std::cout << "set2 = " << set2 << "\n";
  std::cout << "set2 contains(1) => " << set2.contains(1) << "\n"
            << "set2 contains(9) => " << set2.contains(9) << "\n"
            << "set2 contains(2) => " << set2.contains(2) << "\n"
            << "set2 deepContains(2) => " << set2.deepContains(2) << "\n"
            << "set2 contains(set1) => " << set2.contains(set1) << "\n"
            << "set2 deepContains(set1) => " << set2.deepContains(set1) << "\n";
  std::cout << "\n";
 
  Set<int> set3;
  set3.add(3).add(2).add(1);
  std::cout << "set3 = " << set3 << "\n";
  std::cout << "set1 == set3 => " << (set1 == set3) << "\n";
  std::cout << "\n";
 
  Set<int> set4;
  set4.add(set3).add(9);
  std::cout << "set4 = " << set4 << "\n";
  std::cout << "set2 == set4 => " << (set2 == set4) << "\n";
  std::cout << "\n";
}


Ну вот у есть есть внутри множества какой-нибудь std::vector<SetElement> или что там, коллекция элементов, короче. Каждый SetElement может быть как атомом, так и множеством. Беда с этим юнионом, что, во-первых, статически не понять (принципиально), там лежит атом или множество, а во-вторых, туда не всякий класс засунешь, а хотелось бы не жонглировать указателями (но это не так сложно.)

Поэтому можно сделать два вектора: std::vector<AtomicType> и std::vector<Set>. Первый хранит все элементы-атомы, второй — множества. Меньше динамических проверок типов и чуть быстрее поиск, просто потому, что мы уверены, что если нам надо искать число, то мы его ищем среди чисел, а не среди включённых в множество подмножеств. И наоборот, если мы ищем множество, то тоже знаем, где его искать.
Спасибо большое, буду разбирать!)

Добавлено через 1 час 30 минут
Цитата Сообщение от Elfenlide Посмотреть сообщение
Спасибо большое, буду разбирать!)
что-то не компилится, несколько ошибок:
1.Синтаксическая ошибка идентификатор "SetElement"
2. Other - не объявленный идентификатор
3.бинарный "оператор ==" слишком мало аргументов
4.Set<T>::SetElement::operator == " не является статическим членом.
5.Set<T>::SetElement - зависимое имя не является типом.
Yandex
Объявления
22.09.2012, 08:41     Union - Объединения
Ответ Создать тему
Опции темы

Текущее время: 12:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru