Ժամանակ առ ժամանակ ինձ մոտ ցանկություն է առաջանում ծանոթանալ 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 ); } };
Սկզբնաղբյուրը։ http://armenbadal.blogspot.com/2013/01/c11-ii.html
Comments: no replies