<< Пред.           стр. 22 (из 121)           След. >>

Список литературы по разделу

 ( 3 )( 4 2 0 )
 
 Последние две операции, которые мы хотим реализовать, – конкатенация двух списков (добавление одного списка в конец другого) и инверсия (изменение порядка элементов на противоположный). Первый вариант concat() содержит ошибку. Сможете ли вы ее найти?
 void ilist::concat( const ilist &i1 ) {
  if ( ! _at_end )
  _at_front = i1._at_front;
  else _at_end->next( i1._at_front );
  _at_end = i1._at_end;
 }
 Проблема состоит в том, что теперь два объекта ilist содержат последовательность одних и тех же элементов. Изменение одного из списков, например вызов операций insert() и remove(), отражается на другом, приводя его в рассогласованное состояние. Простейший способ обойти эту проблему – скопировать каждый элемент второго списка. Сделаем это при помощи функции insert_end():
 void ilist::
 concat( const ilist &i1 )
 {
  i1ist_item *ptr = i1._at_front;
  while ( ptr ) {
  insert_end( ptr->value() );
  ptr = ptr->next();
  }
 }
 Вот реализация функции reverse():
 void
 ilist::
 reverse()
 {
  ilist_item *ptr = _at_front;
  ilist_item *prev = 0;
 
  _at_front = _at_end;
  _at_end = ptr;
 
  while ( ptr != _at_front )
  {
  ilist_item *tmp = ptr->next();
  ptr->next( prev );
  prev = ptr;
  ptr = tmp;
  }
  _at_front->next( prev );
 }
 Тестовая программа для проверки этих операций выглядит так:
 #include
 #include "ilist.h"
 
 int main()
 {
  ilist mylist;
 
  for ( int ix = 0; ix < 10; ++ix )
  { mylist.insert_front( ix ); }
 
  mylist.display();
 
  cout << "\n" << "инвертирование списка\n";
  mylist.reverse(); mylist.display();
 
  ilist mylist_too;
  mylist_too.insert_end(0); mylist_too.insert_end(1);
  mylist_too.insert_end(1); mylist_too.insert_end(2);
  mylist_too.insert_end(3); mylist_too.insert_end(5);
 
  cout << "\n" << "mylist_too:\n";
  mylist_too.display();
 
  mylist.concat( mylist_too );
  cout << "\n"
  << "mylist после concat с mylist_too:\n";
  mylist.disp1ay();
 }
 Результат работы программы:
 
 ( 10 ) ( 9 8 7 6 5 4 3 2 1 0 )
 
 инвертирование списка
 
 ( 10 ) ( 0 1 2 3 4 5 6 7 8 9 )
 
 mylist_too:
  ( 6 )( 0 1 1 2 3 5 )
 
 mylist после concat с mylist_too:
 
 ( 16 ) ( 0 1 2 3 4 5 6 7 8 9 0 1 1 2 3 5 )
 
 С одной стороны, задачу можно считать выполненной: мы не только реализовали все запланированные функции, но и проверили их работоспособность. С другой стороны, мы не обеспечили всех операций, которые необходимы для практического использования списка.
 Одним из главных недостатков является то, что у пользователя нет способа перебирать элементы списка и он не может обойти это ограничение, поскольку реализация от него скрыта. Другим недостатком является отсутствие поддержки операций инициализации одного списка другим и присваивания одного списка другому. Мы сознательно не стали их реализовывать в первой версии, но теперь начнем улучшать наш класс.
 Для реализации первой операции инициализации необходимо определить копирующий конструктор. Поведение такого конструктора, построенного компилятором по умолчанию, совершенно неправильно для нашего класса (как, собственно, и для любого класса, содержащего указатель в качестве члена), именно поэтому мы с самого начала запретили его использование. Лучше уж полностью лишить пользователя какой-либо операции, чем допустить возможные ошибки. (В разделе 14.5 объясняется, почему действия копирующего конструктора по умолчанию в подобных случаях неверны.) Вот реализация конструктора, использующая функцию insert_end():
 ilist::ilist( const ilist &rhs )
 {
  ilist_item *pt = rhs._at_front;
  while ( pt ) {
  insert_end( pt->value() );
  pt = pt->next();
  }
 }
 Оператор присваивания должен сначала вызвать remove_all(), а затем с помощью insert_end() вставить все элементы второго списка. Поскольку эта операция повторяется в обеих функциях, вынесем ее в отдельную функцию insert_all():
 void ilist::insert_all ( const ilist &rhs )
 {
  ilist_item *pt = rhs._at_front;
  while ( pt ) {
  insert_end( pt->value() );
  pt = pt->next();
  }
 }
 после чего копирующий конструктор и оператор присваивания можно реализовать так:
 inline ilist::ilist( const ilist &rhs )
  : _at_front( 0 ), _at_end( 0 )
  { insert_all ( rhs ); }
 
 inline ilist&
 ilist::operator=( const ilist &rhs ) {
  remove_all();
  insert_all( rhs );
  return *this;
 }
 Теперь осталось обеспечить пользователя возможностью путешествовать по списку, например с помощью доступа к члену _at_front:
 ilist_item *ilist::front() { return _at_front(); }
 После этого можно применить ilist_item::next(), как мы делали в функциях-членах:
 ilist_item *pt = mylist.front();
 while ( pt ) {
  do_something( pt->value() );
  pt = pt->next();
 }
 Хотя это решает проблему, лучше поступить иначе: реализовать общую концепцию прохода по элементам контейнера. В данном разделе мы расскажем об использовании цикла такого вида:
 for ( ilist_item *iter = mylist.init_iter();
  iter;
  iter = mylist.next_iter() )
  do_something( iter->value() );
 (В разделе 2.8 мы уже касались понятия итератора. В главах 6 и 12 будут рассмотрены итераторы для имеющихся в стандартной библиотеке контейнерных типов и обобщенных алгоритмов.)
 Наш итератор представляет собой несколько больше, чем просто указатель. Он должен уметь запоминать текущий элемент, возвращать следующий и определять, когда все элементы кончились. По умолчанию итератор инициализируется значением _at_front, однако пользователь может задать в качестве начального любой элемент списка. next_iter() возвращает следующий элемент или 0, если элементов больше нет. Для реализации пришлось ввести дополнительный член класса:
 class ilist {
 public:
  // ...
  init_iter( ilist_item *it = 0 );
 private:
  //...
  ilist_item *_current;
 };
 init_iter() выглядит так:
 inline ilist_item*
 ilist::init_iter( i1ist_item *it )
 {
  return _current = it ? it : _at_front;
 }
 next_iter() перемещает указатель _current на следующий элемент и возвращает его адрес, если элементы не кончились. В противном случае он возвращает 0 и устанавливает _current в 0. Его реализацию можно представить следующим образом:
 inline ilist_item*
 ilist::
 next_iter()
 {
  ilist_item *next = _current
  ? _current = _current->next()
  : _current;
  return next;
 }
 Если элемент, на который указывает _current, удален, могут возникнуть проблемы. Их преодолевают модификацией кода функций remove() и remove_front(): они должны проверять значение _current. Если он указывает на удаляемый элемент, функции изменят его так, чтобы он адресовал следующий элемент либо был равен 0, когда удаляемый элемент – последний в списке или список стал пустым. Модифицированная remove_front() выглядит так:
 inline void
 ilist::remove_front()
 {
  if ( _at_front ) {
  ilist_item *ptr = _at_front;
  _at_front = _at_front->next();
 
  // _current не должен указывать на удаленный элемент
  if ( _current == ptr )
  _current = _at_front;
 
  bump_down_size();
  delete ptr;
  }
 }
 Вот модифицированный фрагмент кода remove():
 while ( plist ) {
  if ( plist->value() == value )
  {
  prev->next( plist->next() );
  if ( _current == plist )
  _current = prev->next();
 Что произойдет, если элемент будет вставлен перед тем, на который указывает _current? Значение _current не изменяется. Пользователь должен начать проход по списку с помощью вызова init_iter(), чтобы новый элемент попал в число перебираемых. При инициализации списка другим и при присваивании значение _current не копируется, а сбрасывается в 0.
 Тестовая программа для проверки работы копирующего конструктора и оператора присваивания выглядит так::
 #include
 #include "ilist.h"
 
 int main()
 {
  ilist mylist;
 
  for ( int ix = 0; ix < 10; ++ix ) {
  mylist.insert_front( ix );
  mylist.insert_end( ix );
  }
 
  cout << "\n" << "Применение init_iter() и next_iter() "
  << "для обхода всех элементов списка:\n";
 
  ilist_item *iter;
  for ( iter = mylist.init_iter();
  iter; iter = mylist.next_iter() )
  cout << iter->value() << " ";
 
  cout << "\n" << "Применение копирующего конструктора\n";
 
  ilist mylist2( mylist );
  mylist.remove_all();
 
  for ( iter = mylist2.init_iter();
  iter; iter = mylist2.next_iter() )
  cout << iter->value() << " ";
 
  cout << "\n" << "Применение копирующего оператора присваивания\n";
  mylist = mylist2;
 
  for ( iter = mylist.init_iter();
  iter; iter = mylist.next_iter() )
  cout << iter->value() << " ";
 
  cout << "\n";
 }
 Результат работы программы:
 
 Применение init_iter() и next_iter() для обхода всех элементов списка:
 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
 Применение копирующего конструктора
 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
 Применение копирующего оператора присваивания
 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
 
 5.11.1. Обобщенный список
 Наш класс ilist имеет серьезный недостаток: он может хранить элементы только целого типа. Если бы он мог содержать элементы любого типа – как встроенного, так и определенного пользователем, – то его область применения была бы гораздо шире. Модифицировать ilist для поддержки произвольных типов данных позволяет механизм шаблонов (см. главу 16).
 При использовании шаблона вместо параметра подставляется реальный тип данных. Например:
 list< string > slist;
 создает экземпляр списка, способного содержать объекты типа string, а
 list< int > ilist;
 создает список, в точности повторяющий наш ilist. С помощью шаблона класса можно обеспечить поддержку произвольных типов данных одним экземпляром кода. Рассмотрим последовательность действий, уделив особое внимание классу list_item.
 Определение шаблона класса начинается ключевым словом template, затем следует список параметров в угловых скобках. Параметр представляет собой идентификатор, перед которым стоит ключевое слово class или typename. Например:
 template
 class list_item;
 Эта инструкция объявляет list_item шаблоном класса с единственным параметром-типом. Следующее объявление эквивалентно предыдущему:
 template
 class list_item;
 Ключевые слова class и typename имеют одинаковое значение, можно использовать любое из них. Более удобное для запоминания typename появилось в стандарте С++ сравнительно недавно и поддерживается еще не всеми компиляторами. Поскольку наши тексты были написаны до появления этого ключевого слова, в них употребляется class. Шаблон класса list_item выглядит так:
 template
 class list_item {
 public:
  list_item( elemType value, list_item *item = 0 )
  : _value( value ) {
  if ( !item )
  _next = 0;
  else {
  _next = item->_next;
  item->_next = this;
  }
  }
 
  elemType value() { return _value; }
  list_item* next() { return _next; }
 
  void next( list_item *link ) { _next = link; }
  void value( elemType new_value ) { _value = new_value; }
 
 private:
  elemType _value;
  list_item *_next;
 };
 Все упоминания типа int в определении класса ilist_item заменены на параметр elemType. Когда мы пишем:
 list_item *ptr = new list_item( 3.14 );
 компилятор подставляет double вместо elemType и создает экземпляр list_item, поддерживающий данный тип.
 Аналогичным образом модифицируем класс ilist в шаблон класса list:
 template
 class list {
 public:
 list()
  : _at_front( 0 ), _at_end( 0 ), _current( 0 ),
  _size( 0 ) {}
  1ist( const list& );
  list& operator=( const list& );
  ~list() { remove_all(); }
 
  void insert ( list_item *ptr, elemType value );
  void insert_end( elemType value );
  void insert_front( elemType value );
  void insert_all( const list &rhs );
 
  int remove( elemType value );
  void remove_front();
  void remove_all();
 
  list_item *find( elemType value );
  list_item *next_iter();
  list_item* init_iter( list_item *it );
 
  void disp1ay( ostream &os = cout );
 
  void concat( const list& );
  void reverse ();
  int size() { return _size; }
 
 private:
  void bump_up_size() { ++_size; }
  void bump_down_size() { --_size; }
 
  list_item *_at_front;

<< Пред.           стр. 22 (из 121)           След. >>

Список литературы по разделу