C++11: Կապակցված ցուցակներ (II)

Ժամանակ առ ժամանակ ինձ մոտ ցանկություն է առաջանում ծանոթանալ C++ լեզվի C++11 ստանդարտի հնարավորություններին։ Այս գրառման մեջ ես երկկապակցված ցուցակի (doubly linked list) իրականացման օրինակով փորձում եմ ծանոթանալ լեզվի այնպիսի նորամուծություններին, ինչպիսիք են զրոյական ցուցիչի nullptr արժեքը, տիպի դուրսբերման auto եղանակը, արժեքավորող ցուցակով կոնստրուկտորները, մի կոնստրուկտորում մեկ այլ կոնստրուկտորի օգտագործումը, և այլն։

* * *
Մինչև ցուցակը նկարագրելը ներկայացնեմ նրա մեկ հանգույցը մոդելավորող Item դասը։ Այն շաբլոնային դաս է, data, prev և next դաշտերով, որոնցից առաջինը նախատեսված է հանգույցում պահվող ինֆորմացիայի համար, երկրորդն ու երրորդն էլ համապատասխանաբար նախորդ ու հաջորդ հանգույցներին կապելու համար։

template<typename T>
class Item {
public:
  T data;
  Item* prev;
  Item* next;
    
public:
  Item( const T& val, Item* pr, Item* nx )
    : data(val), prev(pr), next(nx)
  {}
  Item( const T& val )
    : Item(val, nullptr, nullptr)
  {}
  inline void Print() const
  { std::cout << data << (next != nullptr ? ", " : ""); }
};

Առաջին կոնստրուկտորը երեք դաշտերն էլ արժեքավորում է տրված արժեքներով։ Երկրորդ կոնստրուկտորը կառուցում է տրված ինֆորմացիայով հանգույց, որի prev և next ցուցիչները զրոյական են։ Այս կոնստրուկտորում արդեն երևում են C++11 ստանդարտի երկու նորամուծություններ։ 1. Մի կոնստրուկտորում կարելի է օգտագործել մեկ այլ կոնստրուկտոր՝ կիրառելով այն դաշտերի արժեքավորման ցուցակում։ 2. Զրոյական ցուցիչների համար նախատեսված է nullptr հաստատունը (այն ծառայողական բառ է)։

Print մեթոդը ստանդարտ արտածման հոսքի վրա արտածում է հանգույցի data դաշտի պարունակությունը։ Եթե հանգույցի next ցուցիչը հավասար է nullptr-ի, ապա համարվում է, որ այդ հանգույցը ցուցակի վերջին հանգույցն է և այլևս ոչինչ չի արտածվում։ Եթե next ցուցիչը տարբեր է nullptr-ից, ապա արտածվում է նաև ստորակետ՝ ենթադրելով, որ հաջորդելու են այլ հանգույցների արտածումներ։

* * *
Ցուցակը մոդելավորող List շաբլոնային դասն ունի երեք դաշտ. head – ցուցիչ է առաջին հանգույցին, tail – ցուցիչ է վերջին հանգույցին, count – հանգույցների քանակն է։

template<typename T>
class List {
private:
  Item<T>* head;
  Item<T>* tail;
  unsigned int count;

Կոնստրուկտորներից առաջինը ստեղծում է դատարկ ցուցակ՝ առաջին ու վերջին հանգույցների ցրույական ցուցիչներով և տարրերի քանակի զրոյական հաշվիչով։

public:
  List()
    : head(nullptr), tail(nullptr), count(0)
  {}

Երկրորդ կոնստրուկտորը ցուցակը կառուցում է տրված արժեքավորող ցուցակի (initializer list) տարրերից: Օրինակ, եթե պետք է սահմանել մի ցուցակ 1, 2, 3 սկզբնական տարրերով, ապա կարող ենք գրել “List<int> ex0 = {1, 2, 3};“: Ահա այս դեպքում է աշխատում հենց ստորև բերված կոնստրուկտորը։ (initializer_list կոնտեյները հայտարարված է ստանդարտ գրադարանի initializer_list ֆայլում։)

  List( std::initializer_list<T> vals )
    : List()
  {
    for( auto v : vals )
      PushBack( v );
  }

Նորամուծություն է նաև ցիկլի կազմակերպման for կառուցվածքի տեսքը։ Այս տեսքով v փոփոխականն անցնում է vars կոնտեյների տարրերով։ auto ծառայողական բառը ցույց է տալիս, որ կոմպիլյատորը v փոփոխականի տիպը ավտոմատ որոշելու է կոմպիլյացիայի ժամանակ։ Եթե գրեինք C++98 ոճով, ապա այս ցիկլը կունենար մոտավորապես հետևյալ տեսքը.

for( std::initalizer_list<T>::iterator v = vals.begin(); v != vals.end(); ++v )
  PushBack( *v );

Front և Back մեթոդները համապատասխանաբար վերադարձնում են ցուցակի առաջին ու վերջին հանգույցների ցուցիչները։ Count մեթոդը վերադարձնում է տարրերի քանակը։ IsEmpty մեթոդը պարզում է ցուցակի դատարկ լինելը։ (Այս ֆունկցիաների իրականացման մեջ որևէ հետաքրքիր բան չկա։)

  Item<T>* Front() const 
  { return head; }
  
  Item<T>* Back() const 
  { return head; }
  
  unsigned int Count() const
  { return count; }

  bool IsEmpty() const
  { return head == nullptr && tail == nullptr; }

Print մեթոդը ստանդարտ արտածման հոսքին արտածում է ցուցակի տարրերի արժեքները՝ ստորակետերով անջատված։ Ցուցակի ամբողջ պարունակությունն արտածվում է “[” և “]” նիշերի մեջ։ Մեթոդի իրականացումը մի պարզ ցիկլ է, որը, թեևս, բացատրության կարիք չունի։

  void Print() const
  {
    std::cout << "[";
    for( auto p(head); p != nullptr; p = p->next )
      p->Print();
    std::cout << "]";
  } 

* * *
Ցուցակում տարրեր ավելացվում են չորս մեթոդների օգնությամբ։ Դրանք են.

• PushFront(v) – ցուցակի սկզբից ավելացնում է տրված v արժեքով հանգույց,
• InsertBefore(v, n) – ցուցակի n հանգույցից առաջ ավելացնում է v արժեքով հանգույց,
• PushBack(v) – ցուցակի վերջից ավելացնում է տրված v արժեքով հանգույց,
• InsertAfter(v, n) – ցուցակի n հանգույցից հետո ավելացնում է v արժեքով հանգույց։

Եթե ցուցակը դատարկ է, ապա PushFront մեթոդը ստեղծում է նոր հանգույց, head և tail ցուցյիչները կապում է նրան, իսկ հանգույցների հաշվիչին վերագրում է 1։ Եթե ցուցակը դատարկ չէ, ապա նոր հանգույցն ավելացվում է InsertBefore մեթոդով։

  void PushFront( const T& val )
  {
    if( IsEmpty() ) {
      head = new Item<T>(val);
      tail = head;
      count = 1;
    }
    else
      InsertBefore( val, head );
  }

InsertBefore մեթոդը արգումենտում ստանում է val արժեքը և node ցուցիչը։ Ապա ստեղծվում է նոր հանգույց՝ val արժեքով, որի prev ցուցիչին վերագրված է node->prev ցուցիչը, իսկ next ցուցիչին՝ node ցուցիչը։ Հաջորդ քայլում նոր ստեղծված temp հանգույցին հաջորդող և նախորդող հանգույցները կապվում են temp-ի հետ։ Եվ վերջապես, ստուգվում է, որ եթե հոր հանգույցն ավելացվել է head-ից առաջ, ապա head տեղաշարժվում է նոր հանգույցի վրա։

  void InsertBefore( const T& val, Item<T>* node )
  {
    auto temp = new Item<T>(val, node->prev, node); // 1
    temp->next->prev = temp; // 2
    if( temp->prev != nullptr )
      temp->prev->next = temp; // 3
    ++count;
    if( node == head )
      head = temp;
  }

PushBack մեթոդը, որ պետք է արժեք ավելացնի ցուցակի պոչից, օգտագործում է տրված հանգույցից հետո նոր հանգույց խցկող InsertAfter մեթոդը։

  void PushBack( const T& val )
  {
    if( IsEmpty() )
      PushFront( val );
    else
      InsertAfter( val, tail );
  }

Իսկ InsertAfter մեթոդն իր հերթին օգտագործում է InsertBefore մեթոդը՝ նոր հանգույցն ավելացնելով ոչ թե տրված հանգույցից առաջ, այլ նրանից հետո, ապա փոխարինելով data դաշտի արժեքները։

  void InsertAfter( const T& val, Item<T>* node )
  {
    InsertBefore( node->data, node );
    node->data = val;
  }

* * *
Մեթոդների հաջորդ խումբը նախատեսված է ցուցակից հանգույցներ հեռացնելու համար։ Դրանք են.

• Remove(n) – ցուցակից հեռացնում է տրված n հանգույցը,
• PopFront – հեռացնում է ցուցակի առաջին հանգույցը և վերադարձնում է նրա data դաշտի արժեքը,
• PopBack – հեռացնում է ցուցակի վերջին հանգույցը՝ նույնպես վերադարձնելով նրա data դաշտի արժեքը,

Remove մեթոդի սկզբում նախ ստուգվում է, որ տրված հանգույցի ցուցիչը զրոյական չլինի և ցուցակը դատարկ չլինի։ Երկու դեպքերում էլ գեներացվում է սխալ՝ runtime_error՝ համապատասխան հաղորդագրությամբ։ Այս բացառության դասը նունպես ավելացված է C++11 ստանդարտում և, ի թիվս այլ նոր բացառությունների դասերի, սահմանված է ստանդարտ գրադարանի stdexcept ֆայլում։
  Այնուհետև, եթե հեռացվող հանգույցն ունի հաջորդող հանգույց, ապա դրա prev ցուցիչին վերագրվում է հեռացվող հանգույցի prev ցուցիչի արժեքը։ Համապատասխան գործողությունը կատարվում է նաև հեռացվողին նախորդող հանգույցի հետ։
  Եթե հեռացվող հանգույցը ցուցակի առաջին կամ վերջին հանգույցն է, ապա համապատասխան ձևով վերահաշվարկվում են նաև head և tail ցուցիչները։
Իսկ վերջում համակարգին է վերադարձվում հեռացվող հանգույցի զբաղեցրած հիշողությունն ու մեկով նվազեցվում է հանգույցների քանակի հաշվիչի արժեքը։

  void Remove( Item<T>* node )
  {
    if( node == nullptr )
      throw new std::runtime_error("Null node.");
    if( IsEmpty() )
      throw new std::runtime_error("Empty list.");
    
    if( node->next != nullptr )
      node->next->prev = node->prev;

    if( node->prev != nullptr )
      node->prev->next = node->next;

    if( node == head )
      head = head->next;
    if( node == tail )
      tail = tail->prev;

    delete node;
    --count;
  }

PopFront և PopBack մեթոդները պարզապես օգտագործում են Remove մեթոդը՝ նախապես պահելով և վերադարձնելով առաջին կամ վերջին հանգույցի պարունակած արժեքը։

  T PopFront()
  {
    auto res(head->data);
    Remove(head);
    return res;
  }
  
  T PopBack()
  {
    auto res(tail->data);
    Remove(tail);
    return res;
  }

* * *
Ցուցակում որոնում կատարելու համար ես նախատեսել եմ երկու մեթոդներ. FindIf, որը վերադարձնում է տրված պրեդիկատին բավարարող առաջին հանգույցի ցուցիչը, և Find, որը վերադարձնում է տրված արժեքը պարունակող առաջին հանգույցի ցուցիչը։

Պրեդիկատը FindIf մեթոդին փոխանցվում է որպես ստանդարտ գրադարանի function օբյեկտ։ Այս function դասը նույնպես ներմուծված է նոր ստանդարտում և սահմանված է functional ֆայլում։

  Item<T>* FindIf( std::function<bool(T)> pred ) const 
  {
    for( auto p(head); p != nullptr; p = p->next )
      if( pred(p->data) )
        return p;
    return nullptr;
  }

Find մեթոդն օգտագործում է FindIf-ը՝ տրված արժեքով հանգույցը գտնելու համար։ Այս մեթոդում ստեղծվում է մի լյամբդա ֆունկցիա (արտահայտություն), որպես որոնման պրեդիկատ, որը “բռնելով” val փոփոխականը, այն համեմատում է իր արգումենտում տրված արժեքի հետ։

  Item<T>* Find( const T& val ) const
  {
    return FindIf( [&val](T v)->bool { return val == v; } );
  }

Եվ վերջին մեթոդը։ Map մեթոդը արգումենտում ստանում է ցուցակի արժեքը ձևափոխող ֆունկցիա և ներադարձնում է ձևափոխված արժեքներից կառուցած նոր ցուցակի ցուցիչը։

  List<T>* Map( std::function<T(T)> func ) const
  {
    auto result = new List<T>();
    for( auto p(head); p != nullptr; p = p->next )
      result->PushBack( func(p->data) );
    return result;
  }

Օրինակ, այս Map մեթոդով կարելի է ամբողջ թվեր պարունակող ցուցակից կառուցել նույն այդ թվերի քառակուսիները պարունակող ցուցակ։ Ահա այսպես.

  auto ex0 = new List<int>({1, 2, 3, 4});
  List<int>* ex1 = ex0->Map( [](int e)->int { return e * e; } );
  ex1->Print();

* * *
List դասի դեստրուկտորը Remove մեթոդի օգնությամբ հեռացնում է բոլոր հանգույցները։

  ~List()
  {
    while( !IsEmpty() )
      Remove( head );
  }
};

Նշագրեր: C++11, lambda, linked list

Բաժին: C և C++, Ծրագրավորում