سلسلة ++c للمحترفين المكرارات (Iterators) في Cpp

المكررات (Iterators) وسيلة لتنفيذ عمليات على سلسلة عناصر على التوالي، رغم أنها ليست عناصر في نفسها، وإنما هي في الأساس عبارة عن مواضع (Positions)، كذلك فإنها امتداد لمفهوم المؤشرات، انظر المثال التالي:

A B C

يحتوي التسلسل السابق على ثلاثة عناصر، وأربعة مواضع كما يوضح التمثيل التالي:

+---+---+---+---+
| A  |  B | C |    |
+---+---+---+---+

العناصر هي أشياء تؤلف تسلسلًا معيّنًا، أما المواضع فهي الأماكن التي يمكن أن تحدث فيها عمليات ما على ذلك التسلسل، فعند إدراج عنصر جديد فإننا ندرجه في موضع ما قبل أو بعد العنصر A مثلًا، وليس داخل العنصر A نفسه، بل حتى حذف العنصر يتم بإيجاد موضعه أولًا ثم حذفه (erase(A.

من المكرِّرات إلى القيم

للانتقال من موضع إلى قيمة، يجب أن يُحصّل (dereferenced) المُكرِّر:

auto my_iterator = my_vector.begin(); // موضع
auto my_value = *my_iterator; // قيمة

يمكن النظر إلى المُكرِّر كمُحصِّلٍ للقيمة التي يشير إليها في التسلسل، لهذا يجب ألا تحاول أبدًا تحصيل الموضع end()‎ في التسلسل:

+---+---+---+---+
| A  |  B | C |    |
+---+---+---+---+
↑               ↑
|               +-- مكرّر لا يشير إلى أي قيمة، لا تحاول تحصيله
+---------------   A تحصيل هذا المكرّر سيعيد القيمة

سيعيد التعبير begin() مكرِّرًا يشير إلى الموضع الأول، وذلك في جميع التسلسلات والحاويات (Containers) الموجودة في مكتبة C++ القياسية، بينما سيعيد end() مكرِّرًا يشير إلى موضع يلي الموضع الأخير (وليس الموضع الأخير نفسه)، لهذا تسمى تلك المكررات أحيانًا first و last. انظر المثال التالي:

+---+---+---+---+
|  A | B | C |     |
+---+---+---+---+
↑               ↑
|                |
+- first       +- last

من الممكن الحصول على مُكرِّر لأي تسلسل، ذلك أن جميع التسلسلات -حتى الفارغة منها- تحتوي على موضع واحد على الأقل:

+---+
|      |
+---+

في التسلسل الفارغ، يمثّل كل من begin()‎ و end()‎ نفس الموضع، ولا يمكن تحصيل أيّ منهما، انظر المثال التالي:

+---+
|      |
+-----+
    ↑
    |
   +- empty_sequence.begin()
   | 
  +- empty_sequence.end()

كذلك يمكن تصوّر المكرِّرات على أنها إشارات تحدد المواضع بين العناصر:

+---+---+---+
| A | B | C |
+---+---+---+
↑    ^    ^    ↑
|                 |
+- first       +- last

ووفقًا لهذا التصوّر فإنّ تحصيل المُكرِّر سيعيد مرجعًا إلى العنصر الذي يأتي بعد المُكرِّر، وهذا مفيد في العمليات التالية:

• عمليات insert ستدرج عنصرًا في الموضع الذي يشير إليه المكرر.
• عمليات erase ستعيد مكررًا يتوافق مع نفس الموضع الذي تم المرور عليه.
• يتواجد المُكرّر، ومُكرّره المعكوس (Reverse Iterator) في نفس الموضع بين العناصر.

المكرِّرات غير الصالحة (Invalid Iterators)

يصير المكرر غيرَ صالحٍ إن لم يعد موضعُه جزءًا من التسلسل (مثال: أثناء عملية ما)، ولا يمكن تحصيل المكرر غير الصالح إلا بعد إسناده (Assign) إلى موضع آخر صالح. انظر المثال التالي الذي يكون فيه first صالحًا، ثم يخرج foo عن النطاق ويحذف، فيصير first بعد ذلك غير صالح.

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin();
}

الخوارزميات ودوال توابع التسلسلات (sequence member functions) التي في مكتبة C++‎ القياسية لديها قواعد تضبط التعامل مع المكررات حين يتم إبطالها (invalidated)، ولكل خوارزمية طريقة مختلفة في التعامل مع المكررات وإبطالها.

التنقل باستخدام المكررات

تُستخدم المكررات للتنقل بين عناصر التسلسل إذ ينقل المكرر موضعه خلال التسلسل، ويستطيع أن يتحرك في كلا الاتجاهين، للأمام أو للخلف.

auto first = my_vector.begin();

// تقديم المكرر بمَوضع واحد
++first;                        

// تقديم المكرَر بموضع واحد
std::advance(first, 1);         

// إعادة المكرَر إلى العنصر التالي
first = std::next(first);         

// تأخير المكرَر بموضع واحد
std::advance(first, -1);        

// إعادة المكرَر 20 موضعا إلى الأمام
first = std::next(first, 20);     

// إعادة المكرر 5 مواضع إلى الخلف
first = std::prev(first, 5);    

// إعادة المسافة بين مكرّرين
auto dist = std::distance(my_vector.begin(), first);

يجب أن يكون الوصول من الوسيط الأول إلى الوسيط الثاني لـ std::distance ممكنًا، بمعنى أن يكون first أصغر من أو يساوي second. ورغم أنك تستطيع إجراء عمليات حسابية على المكررات إلا أن هذا لا يعني أن جميع العمليات قابلة للتطبيق على المكررات كلها، فقد تصلح العملية a = b + 3;‎ لمكررات الوصول العشوائي (Random Access Iterators)، لكنها لن تصلح مع المكررات الأمامية (Forward Iterators) أو ثنائية الاتجاه (Bidirectional) التي يمكن نقلها ثلاثة مواضع للأمام عبر التعليمة b = a; ++b; ++b; ++b;‎، لذلك يوصى باستخدام دوال خاصة إن لم تكن تعرف نوع المكرِّر، كما في حالة قوالب الدوال التي تقبل المكررات.

مفاهيم المُكرِّرات (Iterator Concepts)

يصف معيار C++‎ العديد من مفاهيم المكررات، وقد جُمعت معًا وفقًا لسلوكها في التسلسلات التي تشير إليها، فإن عرفت السلوك العام للمكرِّر، عرفتَ سلوكه في أي تسلسل يشير إليه. وتوصف مفاهيم المكررات تلك مرتبة من أكثرهًا تقييدًا إلى أقلها:

• مكررات الدخل (Input Iterators): يمكن تحصيلها مرة واحدة فقط لكل موضع، ويمكن نقلها للأمام موضعًا واحدًا فقط في كل مرة، إذ لا تنتقل للوراء.
• مكررات التقدم (Forward Iterators): يمكن تحصيل هذه المكرّرات أيّ عدد من المرات.
• المكرّرات ثنائية الاتجاه (Bidirectional Iterators): هي مكررات تقدم تستطيع التحرك للخلف كذلك موضعًا واحدًا في كل مرة.
• المكرّرات العشوائية (Random Access Iterators): هي مكرّرات ثنائية الاتجاه تتحرك بحرية للأمام أو الخلف أي عدد من المواضع في كل مرة.
• المكرّرات المتجاورة (Contiguous Iterators) (منذ C++17): هي مكرّرات عشوائية تضمن أنّ البيانات التي تشير إليها متجاورة في الذاكرة. قد تختلف الخوارزميات وفقًا لمفاهيم المكرِّرات، فرغم إمكانية تقديم random_shuffle مثلًا للمكرِّرات الأماميّة إلا أن هناك بديلًا يتطلب مكرِّرات عشوائية يمكن توفيره، وسيكون أفضل.

سمات المُكرِّرات (Iterator traits)

توفّر سمات المكرّرات واجهة موحّدة لخصائص المكرِّرات. إذ تسمح لك بجلب نوع القيمة value_type ونوع الفرق difference_type وكذلك المؤشر pointer والمرجع reference، إضافة إلى فئة المكرر iterator_category، انظر المثال التالي:

template <class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)
{
   while (first != last)
   {
       if (*first == val)
           return first;
       ++first;
   }
   return last;
}

يمكن استخدام فئة المُكرِّر iterator_category لتخصيص الخوارزميات:

template <class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)
{
    std::cout << "Bidirectional iterator is used" << std::endl;
}

template <class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)
{
    std::cout << "Forward iterator is used" << std::endl;
}

template <class Iter>
void test(Iter a)
{
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

فئات المكرِّرات هي في الأساس مفاهيم مُكرّرات، باستثناء أنّ المكرّرات المتجاورة (Contiguous Iterators) ليس لها وسم (tag) خاص بها، إذ أنها مُخصّصة لإيقاف الشيفرة (break code).

المُكرِّر المُتّجِهي (Vector Iterator)

تعيد begin مكرّرًا iterator يشير إلى العنصر الأول في حاوية التسلسل (sequence container)، بينما تعيد end مكرّرًا يشير إلى العنصر الأول بعد النهاية.

إذا كان الكائن المتّجهي (vector object) ثابتًا const فإنّ كلًّا من begin و end ستعيدان مُكّررًا ثابتًا const_iterator، وإن أردت أن يُعاد مكرّر ثابت حتى لو لم تكن المتجهة ثابتة، فاستخدم cbegin و cend. انظر المثال التالي حيث نهيئ متجهًا باستخدام initializer_list:

#include <vector>
#include <iostream>
int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5};
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        std::cout << *it << " ";
    }
    return 0;
}

سيكون الخرج:

1 2 3 4 5 

مكرّرات القواميس map_iterator

مكرّرات القواميس هي مكرّرات تشير إلى العنصر الأول في الحاوية. ستعيد الدالة مكررًا ثابتًا const_iterator إذا كان كائن الحاوية مؤهلًا ثبوتيًا (const_qualified)، أما إن كان خلاف ذلك فستعيد مكرّرًا عاديًا. انظر المثال التالي حيث ننشئ قاموسًا وندرج فيه بعض العناصر، ثم نكرره على جميع الأزواج:

std::map<char, int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;
for (std::map<char, int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

سيكون الخرج:

a => 200
b => 100
c => 300 

المكرِّرات العكسيّة (Reverse Iterators)

تُستخدم المكررات العكسية reverse_iterator عندما نريد أن نحرِّك المكرِّر للخلف خلال قائمة أو متجه، ونحصل على تلك المكررات من مكرر ثنائي الاتجاه أو مكرر عشوائي، وهما يحتفظان بذلك المكرر كعضو يمكن الوصول إليه من خلال التابع base()‎. ولكي يتحرّك المُكرِّر للخلف، عليك استخدام rbegin()‎ و rend()‎ كمكرّرين يشيران إلى نهاية وبداية المجموعة على الترتيب. انظر المثال التالي الذي نكرر فيه إلى الخلف لنطبع (54321):

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
}

كذلك يمكن تحويل مكرّر عكسي إلى مكرّر أمامي من خلال التابع base()‎، ويشير المكرّر العكسي إلى العنصر الذي يلي المكرّر base()‎، انظر المثال التالي حيث تكون assert(&*r == &*(i-1));‎ صحيحة إن كان r و (i-1) يقبلان التحصيل (Dereferencing) ولم يكونا مكرريْن وكيلين (Proxy Iterators).

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); 
+----+---+---+---+---+---+---+
|      |  1 |  2 |  3 |  4 |  5 |    |
+----+---+---+---+---+---+---+
  ↑      ↑                     ↑    ↑
  |       |                      |     |
rend()  |              rbegin()     end()
          |                                  rbegin().base()
        begin()
       rend().base()

ستكون العلاقة أبسط إن عدنا إلى التصور السابق حيث تحدِّد المكرراتُ المواضع بين العناصر، انظر:

+---+---+---+---+---+
|  1 |  2 |  3 |  4 |  5 |
+---+---+---+---+---+
↑                           ↑
|                            |
|                        end()
|                       rbegin()
begin()              rbegin().base()
rend()
rend().base()

مُكرِّر التدفق istream_iterator

مُكرِّرات التدفق مفيدة عندما نحتاج إلى قراءة تسلسل أو طباعة بيانات منسّقة (formatted) من الحاوية، لنضرب مثلًا ببرنامج يطبع أرقامًا صحيحة تفصل بين كل منها فاصلتين متتاليتين --، ولنفصله جزءًا جزءًا للتوضيح، فأول جزء يوضح تدفقًا للبيانات، يكون أي عدد من محارف المسافات البيضاء فيه مقبولًا.

std::istringstream istr("1\t 2     3 4");
std::vector < int > v;

نبني الآن مكررات تدفق وننسخ البيانات من التدفق إلى متجه:

std::copy( 

ونستخدم مكررًا يقرأ بيانات التدفق كأعداد صحيحة:

std::istream_iterator < int > (istr),

ينتج الباني الافتراضي مكررًا يشير إلى نهاية التدفق:

std::istream_iterator < int > (),
std::back_inserter(v));

نطبع الآن محتوى المتجه الذي سيكون في مجرى الدخل القياسي كأعداد صحيحة مفصولة بفاصلتين متتاليتين (--):

std::copy(v.begin(), v.end(),
std::ostream_iterator < int > (std::cout, " -- "));

انظر الآن الشيفرة كاملة دون التعليقات التوضيحية:

std::istringstream istr("1\t 2     3 4");
std::vector<int> v;
std::copy(
    std::istream_iterator<int>(istr),
    std::istream_iterator<int>(),   
    std::back_inserter(v));
std::copy(v.begin(), v.end(),
    std::ostream_iterator<int>(std::cout, " -- "));

ويكون الناتج المطبوع للبرنامج أعلاه هو التالي:

1 -- 2 -- 3 -- 4 --

مكرِّرات C (المؤشرات)

انظر المثال التالي لشيفرة ستُنتج الأرقام من 1 إلى 5 بحيث تطبع كل رقم على سطر منفصل:

const int array[] = {1, 2, 3, 4, 5};
#ifdef BEFORE_CPP11

const int *first = array;
const int *afterLast = first + sizeof(array) / sizeof(array[0]);

for (const int *i = first; i < afterLast; ++i)
{
   std::cout << *i << std::endl;
}
#else

for (auto i = std::begin(array); i != std::end(array); ++i)
{
   std::cout << *i << std::endl;
}
#endif

الناتج:

1
2
3
4
5

تحليل الشيفرة

const int array[] = { 1, 2, 3, 4, 5 };

ينشئ السطر السابق مصفوفة أعداد صحيحة (integer) فيها خمس قيَم، تذكر أن مصفوفات لغة C هي مجرد مؤشرات إلى مواضع في الذاكرة حيث تُخزَّن قيم المصفوفة بشكل متجاور.

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

هذان السّطران ينشئان مؤشّريْن اثنين، وقد أعطينا للمؤشر الأول قيمة مؤشّر المصفوفة array الذي يمثّل عنوان العنصر الأول فيها. ويعيد العامل sizeof حجم المصفوفة بالبايت عند استخدامه على مصفوفة في لغة C، وعندما نقسمه على حجم عنصر من المصفوفة سنحصل على عدد العناصر في المصفوفة، ومن ثم نستخدم ذلك لإيجاد عنوان الكتلة التالية للمصفوفة في الذاكرة.

for (const int* i = first; i < afterLast; ++i) { 

في السّطر السابق أنشأنا مؤشرًا لاستخدامه كمكرّر، وقد هيّأناه عند عنوان العنصر الأول الذي نريد أن نبدأ التكرار منه، وسنستمر في التكرار ما دام i أصغر من afterLast، أي طالما يشير i إلى عنوانٍ داخل المصفوفة array.

std::cout << *i << std::endl; 

أخيرًا، يمكننا الوصول إلى القيمة التي يشير إليها المُكرِّر i من خلال تحصيله، وذلك داخل الحلقة التكرارية. وهنا يعيد عاملُ التحصيل‏‏ * القيمةَ المخزّنة في العنوان i.

اكتب مُكرِّرك الخاص

يسود في لغات البرمجة الأخرى غير C++ أن توجد دالة تنتج تدفقًا (stream) من الكائنات مع استخدام حلقات تكرارية للمرور على عناصر ذلك التدفق، ويمكن تنفيذ ذلك في C++ أيضًا، انظر المثال التالي حيث نفصل عملية كتابة مكرر خاص بنا:

template < class T >
    struct generator_iterator {
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T * ;
        using reference = T;
        using iterator_category = std::input_iterator_tag;
        std::optional < T > state;
        std:: function < std::optional < T > () > operation;

والآن سنخزن العنصر الحالي -إن كان موجودًا- في state:

        T operator * () const {
            return *state;
        }

نكمل الآن بأن نستدعي العملية، ونكون قد وصلنا للنهاية إن أعادت nullopt:

        generator_iterator & operator++() {
            state = operation();
            return *this;
        }
        generator_iterator operator++(int) {
            auto r = * this;
            ++( * this);
            return r;
        }

لا يتساوى مكرران مدعومان بالمولِّدات (Generator Iterators) إلا إن كانا في حالة end.

        friend bool operator == (generator_iterator
            const & lhs, generator_iterator
            const & rhs) {
            if (!lhs.state && !rhs.state) return true;
            return false;
        }
        friend bool operator != (generator_iterator
            const & lhs, generator_iterator
            const & rhs) {
            return !(lhs == rhs);
        }

سننشئ دالة بشكل مباشر من std::function مع إعطائها البصمة المناسبة.

generator_iterator( std::function< std::optional() > f ):operation(std::move(f)) 
{ 
if (operation)
                state = operation();
} 

نهيئ كل دوال التوابع الخاصة إلى القيمة default.

 generator_iterator( generator_iterator && ) =default;
 generator_iterator( generator_iterator const& ) =default;
 generator_iterator& operator=( generator_iterator && ) =default;
 generator_iterator& operator=( generator_iterator const& ) =default;
 generator_iterator() =default;
};

يمكنك مشاهدة هذا المثال الحيّ. كذلك فإننا سنخزّن العنصر المُنشأ مبكرًا لمعرفة إن كنا وصلنا للنهاية أم لا، ونظرًا لعدم استخدام الدالة الخاصّة بمكرر المولِّد النهائي (end generator iterator)، فنستطيع إنشاء مجموعة من مكررات المولدات عن طريق نسخ std::function مرة واحدة فقط، ويكون مكرر المولد المنشأ افتراضيًا مساويًا لنفسه ولجميع مكررات المولدات النهائية.

هذا الدرس جزء من سلسلة مقالات عن C++‎.

ترجمة -بتصرّف- للفصل Chapter 9: Iterators من كتاب C++ Notes for Professionals