search

divyang4481 / mipt-hw

Automatically exported from code.google.com/p/mipt-hw
0 stars 0 forks source link

task01 TVector (Mishatkin) #182

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
mishatkin_vladimir/Term2/task01a_TVector/Main.cpp

Original issue reported on code.google.com by sane.vova on 3 Mar 2013 at 9:15

GoogleCodeExporter commented 9 years ago 
0. Ошибки компиляции:
./Main.cpp:87: error: class ‘CIterator<T>’ is implicitly friends with itself
./Main.cpp:258: error: ‘const’ qualifiers cannot be applied to 
‘GVector<T>&’
./Main.cpp:341: error: invalid use of template-name ‘std::iterator’ without 
an argument list
./Main.cpp:346: error: invalid use of template-name ‘std::iterator’ without 
an argument list
./Main.cpp:401: error: ‘iterator’ is not a type
./Main.cpp:401: error: ‘iterator’ is not a type
./Main.cpp:401: error: ‘iterator’ is not a type
./Main.cpp:433: error: invalid use of template-name ‘std::iterator’ without 
an argument list
./Main.cpp:439: error: invalid use of template-name ‘std::iterator’ without 
an argument list
./Main.cpp:464: error: invalid use of template-name ‘std::iterator’ without 
an argument list
./Main.cpp: In constructor ‘GVector<T>::GVector(size_t)’:
./Main.cpp:253: error: missing template arguments before ‘it’
./Main.cpp:253: error: expected `;' before ‘it’
./Main.cpp:253: error: ‘it’ was not declared in this scope
./Main.cpp:253: error: there are no arguments to ‘end’ that depend on a 
template parameter, so a declaration of ‘end’ must be available
./Main.cpp:253: error: (if you use ‘-fpermissive’, G++ will accept your 
code, but allowing the use of an undeclared name is deprecated)
./Main.cpp: In member function ‘virtual void GVector<T>::resize(size_t)’:
./Main.cpp:306: error: missing template arguments before ‘it’
./Main.cpp:306: error: expected `;' before ‘it’
./Main.cpp:306: error: ‘it’ was not declared in this scope
./Main.cpp: In member function ‘virtual T& GVector<T>::front() const’:
./Main.cpp:368: error: there are no arguments to ‘begin’ that depend on a 
template parameter, so a declaration of ‘begin’ must be available
./Main.cpp: In member function ‘virtual void GVector<T>::push_front(const 
T&)’:
./Main.cpp:384: error: there are no arguments to ‘begin’ that depend on a 
template parameter, so a declaration of ‘begin’ must be available
./Main.cpp:384: error: missing template arguments before ‘(’ token
./Main.cpp: In member function ‘virtual void GVector<T>::push_back(const 
T&)’:
./Main.cpp:391: error: there are no arguments to ‘end’ that depend on a 
template parameter, so a declaration of ‘end’ must be available
./Main.cpp:391: error: missing template arguments before ‘)’ token
./Main.cpp: In member function ‘virtual void GVector<T>::insert(int, int, 
int)’:
./Main.cpp:409: error: there are no arguments to ‘begin’ that depend on a 
template parameter, so a declaration of ‘begin’ must be available
./Main.cpp:409: error: there are no arguments to ‘end’ that depend on a 
template parameter, so a declaration of ‘end’ must be available
./Main.cpp:410: error: there are no arguments to ‘begin’ that depend on a 
template parameter, so a declaration of ‘begin’ must be available
./Main.cpp:413: error: there are no arguments to ‘begin’ that depend on a 
template parameter, so a declaration of ‘begin’ must be available
./Main.cpp:419: error: missing template arguments before ‘followingIterator’
./Main.cpp:419: error: expected `;' before ‘followingIterator’
./Main.cpp:419: error: ‘followingIterator’ was not declared in this scope
./Main.cpp:425: error: missing template arguments before ‘item’
./Main.cpp:425: error: expected `;' before ‘item’
./Main.cpp:425: error: ‘item’ was not declared in this scope
./Main.cpp:427: error: missing template arguments before ‘newIterator’
./Main.cpp:427: error: expected `;' before ‘newIterator’
./Main.cpp:428: error: ‘newIterator’ was not declared in this scope
./Main.cpp: In member function ‘void 
GVector<T>::printContentTo(std::ostream*)’:
./Main.cpp:471: error: missing template arguments before ‘it’
./Main.cpp:471: error: expected `;' before ‘it’
./Main.cpp:471: error: ‘it’ was not declared in this scope
./Main.cpp:471: error: there are no arguments to ‘end’ that depend on a 
template parameter, so a declaration of ‘end’ must be available
./Main.cpp:473: error: there are no arguments to ‘begin’ that depend on a 
template parameter, so a declaration of ‘begin’ must be available
./Main.cpp: In function ‘void launchGVectorTests()’:
./Main.cpp:483: error: cannot declare variable ‘items’ to be of abstract 
type ‘GVector<int>’
./Main.cpp:228: note:   because the following virtual functions are pure within 
‘GVector<int>’:
./Main.cpp:191: note:   CIterator<T> IVector<T>::begin() const [with T = int]
./Main.cpp:192: note:   CIterator<T> IVector<T>::end() const [with T = int]
./Main.cpp:199: note:   void IVector<T>::insert(CIterator<T>, CIterator<T>, 
CIterator<T>) [with T = int]
./Main.cpp:200: note:   CIterator<T> IVector<T>::insert(CIterator<T>, 
CIterator<T>) [with T = int]
./Main.cpp:201: note:   CIterator<T> IVector<T>::erase(CIterator<T>, 
CIterator<T>) [with T = int]
./Main.cpp:202: note:   CIterator<T> IVector<T>::erase(CIterator<T>) [with T = 
int]
./Main.cpp:490: error: cannot declare variable ‘secondary’ to be of 
abstract type ‘GVector<int>’
./Main.cpp:228: note:   since type ‘GVector<int>’ has pure virtual functions
./Main.cpp:506: error: no matching function for call to 
‘GVector<int>::insert(int*, int*)’
./Main.cpp:401: note: candidates are: void GVector<T>::insert(int, int, int) 
[with T = int]
./Main.cpp:511: error: cannot allocate an object of abstract type 
‘GVector<int>’
./Main.cpp:228: note:   since type ‘GVector<int>’ has pure virtual functions
./Main.cpp:511: error: cannot declare variable ‘newVector’ to be of 
abstract type ‘GVector<int>’
./Main.cpp:228: note:   since type ‘GVector<int>’ has pure virtual functions
./Main.cpp: In constructor ‘GVector<T>::GVector(size_t) [with T = int]’:
./Main.cpp:483:   instantiated from here
./Main.cpp:253: warning: abstract virtual ‘CIterator<T> IVector<T>::end() 
const [with T = int]’ called from constructor
./Main.cpp: In member function ‘void GVector<T>::swap(GVector<T>&) [with T = 
int]’:
./Main.cpp:497:   instantiated from here
./Main.cpp:292: error: cannot allocate an object of abstract type 
‘GVector<int>’
./Main.cpp:228: note:   since type ‘GVector<int>’ has pure virtual functions
./Main.cpp:292: error: cannot declare variable ‘temporary’ to be of 
abstract type ‘GVector<int>’
./Main.cpp:228: note:   since type ‘GVector<int>’ has pure virtual functions
./Main.cpp: In member function ‘void GVector<T>::resize(size_t) [with T = 
int]’:
./Main.cpp:499:   instantiated from here
./Main.cpp:304: warning: unused variable ‘oldSize’
./Main.cpp: In member function ‘void GVector<T>::insert(int, int, int) [with 
T = int]’:
./Main.cpp:391:   instantiated from ‘void GVector<T>::push_back(const T&) 
[with T = int]’
./Main.cpp:491:   instantiated from here
./Main.cpp:409: error: no match for ‘operator>’ in ‘position > 
((GVector<int>*)this)->GVector<int>::<anonymous>.IVector<T>::end [with T = 
int]()’
./Main.cpp:391:   instantiated from ‘void GVector<T>::push_back(const T&) 
[with T = int]’
./Main.cpp:491:   instantiated from here
./Main.cpp:409: error: no match for ‘operator<’ in ‘position < 
((GVector<int>*)this)->GVector<int>::<anonymous>.IVector<T>::begin [with T = 
int]()’
./Main.cpp:391:   instantiated from ‘void GVector<T>::push_back(const T&) 
[with T = int]’
./Main.cpp:491:   instantiated from here
./Main.cpp:410: error: no match for ‘operator-’ in ‘position - 
((GVector<int>*)this)->GVector<int>::<anonymous>.IVector<T>::begin [with T = 
int]()’
./Main.cpp:391:   instantiated from ‘void GVector<T>::push_back(const T&) 
[with T = int]’
./Main.cpp:491:   instantiated from here
./Main.cpp:413: error: no match for ‘operator-’ in ‘position - 
((GVector<int>*)this)->GVector<int>::<anonymous>.IVector<T>::begin [with T = 
int]()’
./Main.cpp:417: error: invalid conversion from ‘int*’ to ‘int’

1. Почему Вы храние поля в protected, а не в private? 
Кстати, в чем разница между ними и когда что 
нужно использовать?

2. В чем смысл поля source у Ваших классов 
исключений?

3. В чем смысле объявления CIterator другом себя?

4. Почему Вы все функции конкретного класса 
делаете виртуальными? В чем смысл 
виртуальных функций? Когда их следует 
использовать? Почему не следует все 
функции подряд делать виртуальными?

5. В постфиксной версии операторов ++/-- Вы 
возвращаете ссылки на локальные 
переменные. В общем случае это приводит к 
undefined behaviour, т.к. после выхода из функции 
локальные объекты разрушаются.

6. Почему Вы решили реализовать итератор 
вектора как объект класса, а не просто 
указатель?

7. Подсчитывать кол-во созданных векторов 
неинтересно. Мы ведь не тесты хотим 
проверить. Нам нужны тесты, проверяющие, 
нет ли ошибок работы с памятью внутри 
вектора. Для этого считать кол-во 
созданных/удаленных объектов, хранимых в 
векторе.

8. Не вижу константного итератора.

9. С какой целью вообще Вы выделяете 
интерфейс у вектора. Какое возможное 
использование этого интерфейса? Почему в STL 
так не сделано?

10. Ваш метод swap делает абсолютно то же 
самое, что и стандартная функция swap. 
Спрашивается, зачем тогда вообще он нужен?

11. Кидать исключения, созданные с 
использованием new - грубая ошибка. Т.к. в 
таком случае их ловить нужно по указателю и 
заботиться в catch об удалении объектов 
исключений. В противном случае - утечки 
памяти.

Общее замечание к Вашему решению:
Предлагаю Вам не использовать инструменты, 
которыми Вы не владеете и сосредоточиться 
на решении поставленной задачи.
Конкретнее: полиморфизм здесь ни к чему. 
Точнее. Алгоритмы STL используют контейнеры 
STL полиморфно. Но для этого не требуется 
интерфейс, т.к. на шаблонах реализуется 
статический полиморфизм.
Если пользуетесь исключениями, делайте это 
правильно.

Советую Вам почитать эту книгу:
http://www.rsdn.ru/res/book/cpp/cppstandards.xml

Original comment by aivyu...@gmail.com on 8 Mar 2013 at 8:52

GoogleCodeExporter commented 9 years ago 
1. Чтобы был прямой доступ к этим полям в 
сабклассе. Portected нужно использовать, когда 
нужен такой вот доступ.
2. Указатель на объект, который получил 
сообщение(вызов метода), которое вызвало 
исключение.
3. Нет смысла, надо исправить.
4. Это реализации pure virtual функций, 
унаследованных от интерфейса. Смысл 
виртуальных функций - динамическое 
связывание, т.е. реализация функции, 
которая будет выполнена, зависит от 
фактического класса объекта, который 
получает сообщение. Их следует 
использовать, когда нужно динамическое 
связывание. Насколько мне известно, по 
крайней мере в некоторых ОО-языках 
(например Java, Objective-C) именно все подряд 
функции виртуальные, и не могут быть не 
виртуальными. Для каждого класса создается 
dispatch table (или Virtual Mehtod Table), которая хранит 
указатели на виртуальные функции с 
реализацией, поэтому занимают 
numberOfNonPureVirtualFunctions * sizeof(pointerToAFunction) памяти, 
что есть одним из минусов злоупотребления 
виртуальными функциями. При вызове 
виртуальной функции идет поиск указателя 
на реализацию этой функции по dispatch table'ам, 
начиная с фактического класса 
ресивера(объекта, от которого вызывается 
метод) вверх по иерархии наследования, то 
есть в сторону родительского класса. 
Существуют какие-то механизмы хеширования 
результатов таких поисков, для того, чтобы 
быстрее находить нужные указатели при 
повторном вызове. Но, в любом случае, если 
бы функция была не виртуальной, время бы не 
тратилось на этот поиск. Еще один повод не 
делать функцию виртуальной по возможности.
6. Насколько я понял, для вектора можно было 
обойтись без отдельного класса итератора, 
и использовать обычный указатель на 
элемент, поскольку доступ к элементам 
последовательный.
Я увидел в обсуждении такой фрагмент
class TMyMegaIterator {
   ...
};

template<typename T>
class TVector {
public:
   typedef TMyMegaIterator iterator;
};
, и почему-то все-таки решил сделать 
отдельный класс итератора.
5. Но если бы нужно было делать отдельный 
класс, как в этом случае нормально 
реализовать постфиксную версию оператора++ 
?
7. Понятно, буду исправлять.
8. Где стоит использовать константный 
итератор?
9. Interface Segregation Principle, который, как я понял, 
здесь неуместен и не используется 
правильно. В STL так не сделано, потому что 
нет возможных использований этого 
интерфейса в других местах, поскольку в STL 
нет контейнера, настолько похожего на 
вектор, чтобы выделять такой интерфейс.
10. Надо исправить.
11. Действительно, лучше бросать объекты, а 
не указатели, не подумал об этом.

Однажды слышал об этой книге, но не 
прочитал. Спасибо.

Original comment by sane.vova on 8 Mar 2013 at 11:09

GoogleCodeExporter commented 9 years ago 
1. Доступ к данным другим классам (даже 
наследникам) - плохой стиль 
программирования. Лучше данные хранить в 
private. А получать доступ к ним через методы 
аксессоры-мутаторы.

2. Ну хорошо. Поймали Вы исключение. У Вас 
есть НЕТИПИЗИРОВАННЫЙ указатель на объект. 
И что с ним делать? :)

4. охъ... В целом все так. Но:
  3.1. Зачем это здесь? Где конкретно и как полиморфно используется интерфейс контейнера?
  3.2. Почему Вы делаете функции виртуальными и в классе-наследнике тоже?
Если Вы делаете функцию виртуальной, да, 
увеличивается таблица вирт методов класса. 
Но, главное, замедляется ее вызов. Да, в 
языках вроде Java/C# все методы виртуальные. 
Ну так они все страдают по 
производительности. Не случайно, например, 
Apple отказался от использования Java вообще.

6. ок. Я не настаиваю. Просто мне важно, чтобы 
Вы понимали, что можно и так реализовать.

5. Нет речь о том, что Вы возвращаете ссылку 
на локальный объект:
         CIterator &operator ++(int)
         {
                 CIterator retValue = *this; // после выхода из метода этот объект не существует
                 m_pObject++;
                 return retValue;
         }
Правильно так:
         CIterator operator ++(int)
         {
                 CIterator retValue = *this;
                 m_pObject++;
                 return retValue;
         }
Если это работает и не падает - не 
удивительно. Т.к. "скорее всего" объект 
помеченен как удаленный (смещен указатель 
стека), но в памяти еще лежит. Дальнейшее 
создание объектов на стеке приведет к 
изменению этой памяти. Так что, в общем 
случае, ссалка, которую возвращает Ваш 
оператор указывает на мусор.

8. Пример. У Вас есть ссылка на константный 
объект vector:
void PrintElements(const TVector<int> &v) { ... }
Если Вы попытаетесь это сделать с помощью 
обычного итератора, получите ошибку 
компиляции, т.к. неконстантный итератор 
возвращает ссылку на неконстантный 
элемент вектора.
Как это реализовано: неконстантный begin/end 
возвращает iterator; константный begin/end 
возвращает const_iterator.
Соответственно, мы синтаксически 
гарантируем, что невозможно получить iterator 
у константного объекта-контейнера.

9. В STL используется полиморфизм, но он 
статический. Если непонятно о чем речь, 
советую почитать про обобщенное 
программирование (generic programming). Например 
здесь: http://www.ozon.ru/context/detail/id/1590010/

P.S.: Использовать сложные решения не к месту 
- норма для новичков :)
Я не отговариваю применять что-то за гранью 
нашего курса. Но в таком случае хочется, 
чтобы у Вас было понимание как это все 
работает.

Original comment by aivyu...@gmail.com on 9 Mar 2013 at 8:49

GoogleCodeExporter commented 9 years ago 
2. Теперь типизированный указатель.
4. Я понял, что здесь так делать не нужно, 
просто ответил на вопрос о виртуальных 
функциях вообщем.
В Objective-C, которым пользуются Apple, все 
функции виртуальные, что вполне 
соответствует парадигме обмена 
сообщениями, унаследованной от SmallTalk. 
Благодаря каким-то алгоритмам кэширования 
результатов поиска, производительность 
немного повышается при повторных вызовах 
виртуальных функций, если верить доке. 
Возможно, за счет этого Objective-C в 
большинстве случаев работает быстрее Java, 
но не стану утверждать, не проверял. Еще 
Objective-C полностью совместим с С, который 
быстрее Java. Возможно, у Apple были еще какие-то 
весомые причины не использовать Java кроме 
той, что там все методы виртуальные. Но и 
здесь не стану утверждать.

Как удалять объекты в erase(), resize() без явного 
вызова деструктора?

Original comment by sane.vova on 10 Mar 2013 at 10:47

GoogleCodeExporter commented 9 years ago

Original comment by sane.vova on 18 Mar 2013 at 3:53

GoogleCodeExporter commented 9 years ago 
0. Compilation errors and warnings:

Main.cpp: In member function ‘virtual std::string 
Object::_internalDescription()’:
Main.cpp:27: error: cast from ‘Object*’ to ‘unsigned int’ loses 
precision
Main.cpp: In member function ‘std::string 
CIterator<T>::_internalDescription() [with T = int]’:
Main.cpp:672:   instantiated from here
Main.cpp:187: error: cast from ‘int*’ to ‘unsigned int’ loses precision
Main.cpp: In member function ‘std::string GVector<T>::_internalDescription() 
[with T = int]’:
Main.cpp:672:   instantiated from here
Main.cpp:298: error: cast from ‘int*’ to ‘unsigned int’ loses precision
Main.cpp:298: warning: format ‘%d’ expects type ‘int’, but argument 3 
has type ‘size_t’
Main.cpp:298: warning: format ‘%d’ expects type ‘int’, but argument 4 
has type ‘size_t’
Main.cpp:298: warning: format ‘%d’ expects type ‘int’, but argument 3 
has type ‘size_t’
Main.cpp:298: warning: format ‘%d’ expects type ‘int’, but argument 4 
has type ‘size_t’

4. Честно говоря, представления не имею, как 
устроены вирт функции и их вызов в Objective С. 
Но в С++ вызов вирт функции производится 
медленнее, чем невиртуальной. Признаюсь, не 
проверял насколько :)

5. Как удалять объекты в erase(), resize() без 
явного вызова деструктора?
В принципе явный вызов деструктора 
используется крайне редко. Возможные 
вариант управления памятью в С++ (самые 
распространенные):
  (a) Объект создается на стеке. Деструктор вызывается автоматически. Память освобождается автоматически.
  (b) Объект создается с помощью оператора new/new[]. Оператор new/new[] выделяет память и вызывает конструктор. Удаление осуществляется с помощью оператора delete/delete[]. Оператор delete/delete[] скобки вызывает декструктор, затем освобождает выделенную память.
  (c) Объект создается с помощью размещающего оператора new. В этом случае деструктор нужно вызывать явно. Освобождение памяти - в зависимости от того, как выделена. Т.е. это сценарий использования для самописного менеджера памяти.
В наших домашних задачах вариант (с) не 
будет встречаться. Остаются (a) и (b). Так что, 
Вам не придется никогда явно вызывать 
деструктор. Пользуйтесь оператором 
delete/delete[]. На практике и он используется 
крайне редко, т.к. в продакшн коде 
применяются смарт-указатели.

По поводу реализации resize()/erase(). В 
действительности, в STL как правило 
используется как раз размещающий оператор 
new/new[]. И соответственно - явный вызов 
деструктора. Это связано с тем, что STL 
использует свой менеджер памяти. Но я 
предлагаю упростить нашу задачу и для 
управления памятью ограничиться 
new/new[]/delete/delete[].

В таком случае в resize():
  * если запрашиваемый размер меньше просто уменьшаем внутреннюю переменную Size без реального удаления объектов. Они все равно удаляться при вызове delete[] для всего массива
  * если запрашиваемый размер больше. создаем новый массив большего размера, перекладываем в него объекты из исходного массива. Недостающие объекты инициализируем копированием: = T() (в реальном STL - размещающим оператором new). Исходный массив удаляем с помощью delete[].

erase():
Просто перемещаем копированием элементы и 
уменьшаем Size.

Original comment by aivyu...@gmail.com on 6 Apr 2013 at 6:30

GoogleCodeExporter commented 9 years ago 
Кстати, я не против, если Вы используете С++11.

Original comment by aivyu...@gmail.com on 6 Apr 2013 at 6:33