القائمة الأمامية في C++ STL

Forward_list توفر الحاوية تنفيذ قائمة مرتبطة منفردة بنية البيانات. يقوم بتخزين البيانات في ذاكرة غير متجاورة حيث يشير كل عنصر إلى العنصر التالي في التسلسل. وهذا يجعل الإدراج والحذف أسرع بمجرد معرفة موضع العنصر.

بناء الجملة

يتم تعريف القائمة الأمامية على أنها الأمراض المنقولة جنسيا::forward_list قالب الفصل داخل < ward_list > ملف الرأس.

ward_list فلوريدا؛

أين

  • ت: نوع بيانات العناصر في القائمة الأمامية.
  • و: الاسم المخصص للقائمة الأمامية.

الإعلان والتهيئة

يمكن الإعلان عن قائمة Forward_list وتهيئتها بعدة طرق كما هو موضح في المثال أدناه:

C++
   #include          using     namespace     std  ;   void     printFL  (  forward_list   <  int  >&     fl  )     {      for     (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     'n'  ;   }   int     main  ()     {          // Creating an empty forward_list      forward_list   <  int  >     fl1  ;      // Creating a forward_list with      // default value      forward_list   <  int  >     fl2  (  3       4  );          // Creating a forward_list from an      // initializer list      forward_list   <  int  >     fl3     =     {  1       5       3       4  };          printFL  (  fl2  );      printFL  (  fl3  );      return     0  ;   }   

الإخراج
4 4 4 1 5 3 4  

مثال: في البرنامج أعلاه، قمنا بتهيئة القائمة الأمامية البسيطة بثلاث طرق:

  • إفادة ward_list FL1 ينشئ قائمة أمامية فارغة من الأعداد الصحيحة.
  • إفادة ward_list فلوريدا2(34) ينشئ قائمة أمامية بالحجم 3 وكل عنصر يكون 4.
  • إفادة ward_list fl3 = {1 5 3 4} يقوم بإنشاء قائمة للأمام وتهيئتها باستخدام العناصر التي تشكل قائمة المُهيئ.

العمليات الأساسية

فيما يلي العمليات الأساسية التي يمكننا تنفيذها في القائمة الأمامية:

1. الوصول إلى العناصر

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

ومع ذلك، يمكن الوصول بسهولة إلى العنصر الأول من القائمة أمام() طريقة.

مثال:

C++
   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Access the first element      cout      < <     fl  .  front  ()      < <     endl  ;          // Access third element      auto     it     =     next  (  fl  .  begin  ()     2  );      cout      < <     *  it  ;      return     0  ;   }   

الإخراج
1 3 

مثال: في البرنامج أعلاه تتم طباعة العنصر الأول باستخدام أمام() طريقة. للوصول إلى العنصر الثالث التالي() يستخدم لتحريك المكرر موقعين من البداية و *هو - هي يتم استخدامه لإلغاء الإشارة إلى المكرر.

2. إدراج العناصر

يمكن إدراج العناصر في القائمة الأمامية باستخدام إدراج_بعد () وظيفة. يتطلب المكرر الذي سيتم بعده إدراج العنصر. ومع ذلك يتم دعم الإدراج السريع في المقدمة Push_front() طريقة.

مثال:

C++
   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  5       4  };      // Inserting Element at front      fl  .  push_front  (  1  );          // Insert 3 after the second element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  insert_after  (  it       3  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }   

الإخراج
1 5 3 4  

توضيح: في هذا البرنامج، يتم إدراج العنصر الأول من قائمة Forward_list في المقدمة باستخدام الأمر Push_front() وظيفة. ثم يتم إنشاء مكرر وتحريك موضع واحد للأمام باستخدام يتقدم() وظيفة. بعد ذلك العنصر 5 يتم إدراجه بعد العنصر الثاني باستخدام إدراج_بعد () وظيفة.

3. تحديث العناصر

يمكن تغيير قيمة العناصر الموجودة ببساطة عن طريق الوصول إليها واستخدامها عامل المهمة لتعيين القيمة الجديدة.

مثال:

C++
   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Updating first element      fl  .  front  ()     =     111  ;      cout      < <     fl  .  front  ()      < <     endl  ;          // Updating third element      auto     it     =     next  (  fl  .  begin  ()     2  );      *  it     =     333  ;      cout      < <     *  it  ;      return     0  ;   }   

الإخراج
111 333 

4. العثور على العنصر

لا توفر القائمة الأمامية أي وظيفة عضو للبحث عن عنصر ولكن يمكننا استخدام يجد() خوارزمية للعثور على أي قيمة معينة.

مثال :

C++
   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Finding 3      auto     it     =     find  (  fl  .  begin  ()     fl  .  end  ()     3  );          if     (  it     !=     fl  .  end  ())     cout      < <     *  it  ;      else     cout      < <     'Element not Found'  ;      return     0  ;   }   

الإخراج
3 

5. العبور

يمكن اجتياز القائمة الأمامية باستخدام يبدأ() و نهاية() التكرارات ذات حلقة ولكن لا يمكننا التحرك إلا للأمام وليس للخلف.

مثال:

C++
   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };          // Traversing using range-based for loop      for  (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     endl  ;          return     0  ;   }   

الإخراج
1 5 3 4  

6. حذف العناصر

في القائمة الأمامية يمكننا حذف العنصر الموجود في الموضع المحدد باستخدام محو_بعد () طريقة. تأخذ هذه الطريقة المكرِّر إلى موضع واحد قبل العنصر الهدف. الحذف السريع من الأمام ممكن باستخدام pop_front() طريقة.

مثال:

C++
   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Delete first element      fl  .  pop_front  ();          // Delete third element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  erase_after  (  it  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }   

الإخراج
5 3  

7. حجم القائمة الأمامية

لا تحتوي Forward_list على وظيفة size() مضمنة. للعثور على حجمه، نحتاج إلى حساب العناصر يدويًا عن طريق اجتيازها بحلقة أو باستخدام المسافة std::.

C++
   #include          #include         #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  =  {  10    20    30    40  };      //Calculate size by counting elements using std:: distance      int     size  =  distance  (  flist  .  begin  ()  flist  .  end  ());      cout   < <  'Size of forward_list: '   < <  size   < <  endl  ;      return     0  ;   }   

الإخراج
Size of forward_list: 4  

8. فارغة ()

يتم استخدامه للتحقق مما إذا كانت قائمة Forward_list فارغة.
يتم إرجاعه صحيحًا إذا كانت القائمة فارغة وخطأ مما يسمح بالتحقق بسرعة مما إذا كانت الحاوية لا تحتوي على بيانات.

C++
   #include          #include         using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  ;      if     (  flist  .  empty  ())     {      cout      < <     'The forward_list is empty.'      < <     endl  ;      }      flist  .  push_front  (  10  );      if     (  !  flist  .  empty  ())     {      cout      < <     'The forward_list is not empty.'      < <     endl  ;      }      return     0  ;   }   

الإخراج
The forward_list is empty. The forward_list is not empty.  

تعقيد الوقت

يسرد الجدول أدناه التعقيد الزمني للعمليات المذكورة أعلاه في القائمة الأمامية:

عملية تعقيد الوقت
الوصول إلى العنصر الأول يا(1)
الوصول ن ذ عنصر على)
أدخل في الأمام يا(1)
أدخل بعد موضع محدد على)
حذف العنصر الأول يا(1)
حذف بعد موقف محدد على)
اجتياز على)

القائمة الأمامية مقابل القائمة

ميزة

ward_list

قائمة

نوع القائمة المرتبطة

قائمة مرتبطة منفردة

قائمة مرتبطة بشكل مضاعف

اجتياز

لا يمكن إلا أن تعبر إلى الأمام

يمكن اجتياز كل من الأمام والخلف

استخدام الذاكرة

يستخدم ذاكرة أقل (مؤشر واحد فقط لكل عقدة)

يستخدم المزيد من الذاكرة (مؤشران لكل عقدة)

الإدراج/الحذف

الإدراج والحذف السريع ولكن فقط عند أو بعد موضع معين

الإدراج والحذف السريع في أي مكان (قبل الموضع أو بعده)

الوظائف المدعومة

محدود مقارنة بالقائمة (بدون حجم () ولا يوجد مكررات عكسية)

واجهة أكثر اكتمالا بما في ذلك حجم () عكس () التكرارات ثنائية الاتجاه.