insert_front( value );
Второй изъян в нашей версии можно назвать философским. Мы реализовали size() и _size как пробный вариант, который может впоследствии измениться. Если мы преобразуем функции size() таким образом, что она будет просто пересчитывать элементы списка, член _size перестанет быть нужным. Написав:
++_size;
мы тесно связали реализацию insert() с текущей конструкцией алгоритма пересчета элементов списка. Если мы изменим алгоритм, нам придется переписывать эту функцию, как и insert_front(), insert_end() и все операции удаления из списка. Вместо того чтобы распространять детали текущей реализации на разные функции класса, лучше инкапсулировать их в паре:
inline void ilist::bump_up_size() { ++_size; }
inline void ilist::bump_down_size() { --_size; }
Поскольку мы объявили эти функции встроенными, эффективность не пострадала. Вот окончательный вариант insert():
inline void
ilist::
insert( ilist_item *ptr, int value )
if ( !ptr )
insert_front( value );
else {
bump_up_size();
new ilist_item( value, ptr );
}
}
Реализация функций insert_front() и insert_end() достаточно очевидна. В каждой из них мы должны предусмотреть случай, когда список пуст.
inline void
ilist::
insert_front( int value )
{
ilist_item *ptr = new ilist_item( value );
if ( !_at_front )
_at_front = _at_end = ptr;
else {
ptr-next( _at_front );
_at_front = ptr;
}
bump_up_size();
}
inl-ine void
ilist::
insert_end( int value )
{
if ( !_at_end )
_at_end = _at_front = new ilist_item( value );
else _at_end = new ilist_item( value, _at_end );
bump_up_s-ize();
}
find() ищет значение в списке. Если элемент с указанным значением найден, возвращается его адрес, иначе find() возвращает 0. Реализация find()выглядит так:
ilist_item*
ilist::
find( int value )
{
ilist_item *ptr = _at_front;
while ( ptr )
{
if ( ptr-value() == value )
break;
ptr = ptr-next();
}
return ptr;
}
Функцию find() можно использовать следующим образом:
ilist_item *ptr = mylist.find( 8 );
mylist.insert( ptr, some_value );
или в более компактной записи:
mylist.insert( mylist.find( 8 ), some_value );
Перед тем как тестировать операции вставки элементов, нам нужно написать функцию display(), которая поможет нам при отладке. Алгоритм display() достаточно прост: печатаем все элементы, с первого до последнего. Можете ли вы сказать, где в данной реализации ошибка?
// не работает правильно!
for ( ilist_item *iter = _at_front; // начнем с первого
iter != _at_end; // пока не последний
++iter ) // возьмем следующий
cout iter-value() ' ';
// теперь напечатаем последний
cout iter-value();
Список – это не массив, его элементы не занимают непрерывную область памяти. Инкремент итератора
++iter;
вовсе не сдвигает его на следующий элемент списка. Вместо этого он указывает на место в памяти, непосредственно следующее за данным элементом, а там может быть все что угодно. Для изменения значения итератора нужно воспользоваться членом _next объекта ilist_item:
iter = iter-_next;
Мы инкапсулировали доступ к членам ilist_item набором встраиваемых функций. Определение класса ilist_item теперь выглядит так:
class ilist_item {
public:
ilist_item( int value, ilist_item *item_to_link_to = 0 );
int value() { return _value; }
iilst_item* next() { return _next; }
void next( ilist_item *link ) { _next = link; }
void value( int new_value ) { _value = new_value; }
private:
int _value;
ilist_item *_next;
};
Вот определение функции display(), использующее последнюю реализацию класса ilist_item:
#include iostream
class ilist {
public:
void display( ostream os = cout );
// ...
};
void ilist::
display( ostream os )
{
os "\n( " _size " )( ";
ilist_item *ptr = _at_front;
while ( ptr ) {
os ptr-value() " ";
ptr = ptr-next();
}
os ")\n";
}
Тестовую программу для нашего класса ilist в его текущей реализации можно представить таким образом:
#include iostream
#include "ilist.h"
int main()
{
ilist mylist;
for ( int ix = 0; ix 10; ++ix ) {
mylist.insert_front( ix );
mylist.insert_end( ix );
}
cout
"Ok: после insert_front() и insert_end()\n";
mylist.display();
ilist_item *it = mylist.find( 8 );
cout "\n"
"Ищем значение 8: нашли?"