Professional Data Structure Libraries In Cpp

هذه أشهر الـ Data Structure الموجودة في المكتبة القياسية لـ ++C و Boost. مع ذكر نبذة مختصرة جداً حول كل منها حتى نتعرف على أسمائها لا أكثر. و بعد ذلك نتكلم حول استخدام بعضها و كيفية الاستفادة القصوى منها.

vector : أشهر من نار على علم :P المصفوفة الديناميكية في ++C بشكل قياسي. يمكنك بناء مصفوفة غير معرفة الحجم وقت كتابة البرنامج, و من ثم إضافة و إزالة العناصر منها بكل سهولة, حيث يقوم vector بالقيام بالمهمة على أكمل وجه.

list : مطابقة لـ vector في عملها, و لكن خصائص الاستعمال تختلف, أي أنها تفضل في أحيان و يفضل vector في أحيان أخرى بناءً على مواصفات البرنامج. سنتكلم في الفروق لاحقاً.

DQ أو deque : من أهم الـ Data Structures التي تستخدم بناء Data Structures أخرى. تشبه vector في عملها, و لكنها تتميز بميزة إضافية, و هي أنه يمكن للمبرمج أن يضيف إليها من الطرفين, بينما في vector أي إضافة تتم بعد آخر عنصر. و كذك الأمر مع عملية الحذف, يمكنك الحذف من الطرفين. سنلقي نظرة عن قرب عنها رغم أننا لن نستخدمها كثيراً في برامجنا مباشرة.

stack : أعتقد أن طلاب البرمجة لابد أن يعرفو ماهو الـ stack :)

queue : في حين أن آخر عنصر يوضع على الـ stack يخرج أولاً, في queue أول عنصر يدخل هو أول من يخرج (على شكل طابور).

priority queue : يقوم هذا الـ data structure بترتيب العناصر التي يحتويها, و عند طلب العنصر التالي, يقوم بإخراج العنصر الأول بعد عملية الترتيب. يشبه queue بشكل كبير, و الفرق, أن عملية إخراج العناصر لا تتم بالطريقة نفسها, و لكن كلاهما يسمح بإخراج عنصر واحد في كل مرة. و في كلاهما نقوم بإدخال العناصر من طرف و إخراج عناصر أخرى من الطرف الآخر.

set : تحاكي الزمر في الرياضيات, و لكن بفرق واحد لا أكثر, و هو أن عناصرها مرتبة دائماً. الفرق بينها و بين الـ priority queue أنك لو قمت بإدخال عنصر و كان هذا العنصر موجوداً من الأساس فيها, فإنه لن تتم إضافة نسخة إضافية و يتم الاكتفاء بالنسخة الأولى.

mutliset : نفس set و لكنها تسمح بإضافة نسخ من العناصر! بالطبع إن كنت متابعاً فستعتقد أني بدأت أخرف, هذا يعني أنها بالضبط تعمل عمل الـ priority queue!!! لاحقاً عندما نتحدث عن الفرق بين الـ Containers و الـ Adapters و نغوص في الموضوع بشكل أعمق سنعرف الفرق, و هل هذا حقاً تكرار وظائف.

map : تسمى associative array. هذا النوع يأتي غالباً ضمن اللغات العالية المستوى جداً , و لغات الـ scripting شهيرة بهذا النوع, و لكنه في ++C ضمن المكتبة القياسية. يعمل هذا الشيء المسمى map بطريقة بسيطة, كل عنصر في map عبارة زوج من العناصر, بمعنى أن map كل قيمة فيها لها قيمة مقابلة, ربما أسماء طلاب الفصل, و تكرار كل اسم منهم على سبيل المثال في ذلك الفصل, أو كل مدينة و عدد سكانها, و هكذا. فلو قررت أن تكون القيمة الأساسية أسماء الطلاب, و يكون عددهم هو القيمة المقابلة, فيمكن مع إضافة كل اسم موجود أصلاً أن نزيد عداد الطلاب المشابهين في أسمائهم للاسم المدخل.

mutlimap : نفس map و لكنها تسمح بتكرار العناصر. الفائدة منها عندما نريد الحفاظ على قيم النسخ المتشابهة في طرف معين, و لكنها مختلفة في أطراف أخرى. سيتضح الحديث عنها لاحقاً.

بقي في المكتبة القياسية bitset و valarray يمكنك الاطلاع عليهما إن كان يهمك الأمر, و لأنها متخصصتان بشكل أكبر من كونهما أداتان عامتان للقيام بالأعمال البرمجية. أنا أستخدمهما و إن كان هناك وقت سنتسعرض فائدتها بإذن الله. bitset عبارة عن مصفوفة قيم منطقية boolean values و هي تضغط كل قيمة في bit واحد. بينما valarray هي مصفوفة للاستعمال الرقمي. فمثلاً إن كنت تريد تريد بناء مصفوفات رياضية و غير ذلك, فهي توفر دوال كثيرة للمساعدة, إضافة إلى خصائص قوية جداً للاستعمال العلمي, و لكنها ليست مكتبة رياضيات, و لكن data structure للبرامج العملية.

إذا استطعنا المرور على هذا كله, فلابد من إلقاء نظرة على "المدمرة" الشهيرة Boost و ما فيها من نفائس مبنية على طريقة الملكة STL :) هذه قائمة بالـ Data Structures الموجودة في Boost, و التي لا يتوفر في اللغات الأخرى مثلها غالباً, حتى في C و لا أعتقد أن هناك مكتبة تجمع هذا الكم الكبير من الـ Data Structures المتقدمة للبرامج الحقيقية بسهولة الاستخدام المتناهية و التصميم المثالي و السرعة الفائقة. هذا ليس كلام على الماشي, لذلك خذ وقتك و اطلع على Boost و ما فيها, لأني لا أعتقد أننا سنصل إلى هذه المكتبة الرائعة إلا بعد وقت طويل:

كل ما تراه في الأعلى هو أدوات عامة في Boost! و إذا كنت تريد أدوات لبناء Data Structure فوقها فموجود أدوات كثيرة للمحترفين! من اهمها MPL و Fusion و غيرهما الكثير!

نفتح المجال لهذه السلسلة, لكي تكون بإذن الله موضوعاً جيداً.

تحياتي ...

متابع معك ياخالد و زادك الله علم ونفع بعلمك.

اقتباس

متابع معك ياخالد و زادك الله علم ونفع بعلمك.

بارك الله فيك أخي فهد :)

اقتباس

ارجو شرح هذا الشباتر اخي لانها مهمه انا عن نفسي درستها ولكن لم افهماااااااااااااا

للأسف أنا سأفترض أن القارئ يعرف ماهية الـ Data Structure الأساسية, و إلا لن نستطيع تغطية الموضوع إلا بعدة كتب, و هو ما لا أقدر عليه بأي شكل :)

و لكن إن شاء الله تجد الفائدة في الموضوع, لأننا سنتكلم عن الجانب العملي أكثر.

قبل أن يولد أي برنامج إلى الوجود, لابد أن يخرج من عقل آدمي. ما أن تختمر الفكرة, و ينتقل المبرمج من الفكرة إلى التطبيق, فإنه يبدأ ما يسمى بعملية تصميم البرنامج. عند هذه المرحلة بالضبط, يظهر الفرق بين المبرمجين الكبار و المبرمجين المبتدئين (أمثالي :P). ماهو الشيء الذي نقوم به بالضبط في هذه المرحلة, هل هو حلها ؟! بالتأكيد لا! و لكن نقوم بتحديد المشكلة نفسها, و هذه المرحلة تعني فهم المسألة, سواء كانت المسألة إنتاج الأعداد الأولية الأصغر من 1000 أو كانت بناء نظام كامل كـ NET. أو بناء ناطحة سحاب, أو تصميم سيارة. هذه المرحلة ليست مقتصرة على عالم الحاسوب وحده. كل الأعمال لابد أن تمر على مرحلة تصمم فيها. و فهم المشكلة هو نصف الحل بكل بساطة, ما إن تستوعب المشكلة, حتى تضع الحل الأفضل. لابد أن تعلم أن كل مشكلة, و لها حلول, بعضها جيد و بعضها سيء! تماماً كما يصمم مهندسو الفضاء سفنهم, فربما تكون المادة التي اخترتها لجدار السفينة الفضائية, ملائمة جداً للظروف التي تحيط بالسفينة, و لكنها أقرب إلى الجنون عند وضعها على سيارة, فالسيارة لا تحتاج إلى الحماية الزائدة عن الحد التي تحتاجها السفن الفضائية, لاختلاف الظروف, في كل ظرف نقوم بدارسة المحيط, و اختيار المواد الأنسب للظروف المواجهة.

عندما تنتقل من التصميم إلى مرحلة الـ Implementation, فأنت كنت قد اخترت كيف سيقوم برنامجك بحل المشكلة. تلك الطريقة التي حللت بها السؤال, قد تكون سهلة, و قد تكون معقدة جداً, و إذا كانت معقدة فليس عليك إلا أن تأخذ نظرة على ما في STL أو Boost و ترى هل هناك شيء أحتاجه؟ ما إن تجد شيئاً قريباً و لو من مسافة بعيدة, فخذه و لا تنتظر! و ركز على فكرة برنامجك الأساسية, و دع تفاصيل الحل على المكتبات دون إضاعة الوقت.

STL و هو اسم المكتبة التي صممها Alexander Stepanov, أحد علماء HP سابقاً, و حالياً أحد علماء Adobe الكبار. قام هذا الرجل بتصميم مكتبة فريدة من نوعها. سماها Standard Template Library, و ذلك لاستخدامها في شركة HP ككل. و لكن بعد إطلاقها تبنتها العديد من الشركات الكبيرة, و ذاع صيتها و تم دمج معظمها في ++C بناءً على طلب Alex نفسه, و رغبة الشركات الكبرى في أن تصبح مكتبة موحدة. ما يميز مكتبتنا, أن هناك وثيقة رسمية لها, و لكن هناك الكثير من الشركات التي قامت ببناء نسخ خاصة من المكتبة, تلك النسخ تتبع الوثيقة الرسمية, بمعنى أنك يمكن أن تغير المكتبة من جذورها في مترجمك و تنزل المكتبة الجديدة, دون أدنى عناء, رغم أن هذا غير وارد الحصول كثيراً, إلا أنه أحد الفوائدة بجانب الفائدة الرئيسية و هي القوة اللامتناهية في جعبة الأدوات التي صممها Alex :)

STL مكتبة صعبة المنال, بمعنى أن تعلمها ليس سهلاً! لأنها تضم الكثير من الأفكار الغريبة! فهي تمزج ما بين أساليب الـ Data Abstraction و الـ Procedural و الـ Functional. و روعي في تصميمها أن تكون بأقصى كفاءة Efficiency و أكبر مرونة Flexibility ممكنة. ستجد أن كل جزء في هذه المكتبة عبارة أن أداة قائمة بذاتها, و تتعامل مع الأدوات الأخرى بكل سلاسة. فاي أداة يمكن أن تستبدلها, بغيرها ممن يقوم بوظيفتها دون أدنى مشكلة, و في الحقيقة بعد تعرفنا على STL ستجد أننا لن نغير سطراً واحداً من الكود حتى عند رغبتنا في تغيير أجزاء كبيرة من الحل!

إن STL لتنفيذ أهدافها, تم بناؤها بـ الـ Templates في ++C. و ذلك لأن الـ Templates توفر ما تطلبه هذه المكتبة, و للعلم فقط, فإن STL في الأساس كانت مشروعاً للغة ADA العريقة, و لكن Alex رأى في ++C لغة أقوى للمستقبل, و حرية أكبر في تصميم المكتبة.

أعتقد أن أكثرت من الكلام في المقدمة, و لكن ذلك ضروري, حتى نتعرف على ما نحن مقبلون عليه, فهذا الموضوع ليس مرجعاً حول STL :)

لو أردنا تلخيص الفكرة الأساسية حول STL فيمكن القول بأنها عبارة عن أداة لكتابة الخوارزميات! لا أقصد كتابة الخوارزميات بلغة ++C, و لكن أقصد كتابة الخوارزمية مباشرة كما هي على الورق, و ترك الباقي للمكتبة لكي تصل الحلول ببعضها البعض!

المكتبة تقدم لك أدوات لتصميم حلولك بها, و هذا هو موضوعنا الأول..............................

STL من على ارتفاع 33000 قدم :

في هذه المكتبة ركنان, الركن الأول, هو الـ Containers, كـ vector و map و unordered_set و غيرهم. في الزاوية الأخرى, هناك ما يمسى بالخوارزميات algorithms, بكل بساطة هي خوارزميات, و لكنها عامة, أي أنها ليست مرتبطة بـ vector أو set أو stack أو غيره ذلك! هذه الخوارزميات, لا تتعامل مع الـ Containers و إنما مع شيء يسمى الـ Iterators و هي أشباه مؤشرات, نعم أدوات تشبه المؤشرات, و لكن تستخدم لأغراض مختلفة عنها. بالطبع, سيطرأ السؤال التالي: لماذا بحق من في السماء يقوم أحدهم بتصميم المكتبة بهذه الطريقة! لماذا لا تعمل هذه الخوارزميات مباشرة على الـ Containers! مالداعي لوجود شيء اسمه Iterator و ما هو أصلاً؟!

سنتعرف على الـ Containers بعد قليل, و لكننا لن نسرد خصائصها و هكذا, و إنما سنتعرف على المكتبة, و نضع النقاط على الحروف بالنسبة للـ Containers لكي نمد جسراً للوصول إلى الخوارزميات و الـ Iterators و هما قلب المكتبة النابض و سر قوتها!

تحياتي...

جزاك الله خيرا اخى خالد

متابع معك بإذن الله

و فقك الله لما يحبه و يرضاه

مالفرق بين vector أو ما يسمى غالباً بالـ Dynamic Array و بين list أو ما يسمى غالباً linked list بأنواعها العديدة, double linked list أو single linked list ؟!

الفرق يكمن في كيفية عمل كل واحد من هذه الأنواع, و لكن ليس هناك فرق من وجهة نظر مستخدمها. بمعنى أن كلاهما Sequence Containers. أي أنك عندما تضيف العناصر إلى أحدهما فإن العناصر يمكنك استرجاعها بالترتيب الذي أضيفت به. ببساطة, أن العناصر فيها تخزن حسب الزمن الذي أدخلت فيه تلك العناصر. فلو أدخلنا 4 ثم 3 ثم 2 ثم 1 ثم 99 فإن العناصر تكون على الشكل التالي:

4 3 2 1 99

بالنسبة للفرق بينها في حين أن الأول يخزن عناصره في أماكن متجاورة في الذاكرة, و الثاني يخزن عناصره في أماكن متفرقة و يبقي على سهم للعنصر التالي أو السابق في السلسلة, فهذا ليس له علاقة في مفهوم الـ Sequence Containers لأن تلك الـ Containers تخزن عناصرها بشكل متتالي, على اختلاف الطريقة. هل تذكرون ما قلناه عن deque, قلنا عنه بأنه يشبه المصفوفات, و هو يحاكي الـ Double linked list, من حيث المفهوم, بأن كلاهما لهما بدايتان و نهايتان. الأنواع vector و list و deque عبارة عن Sequence Containers بكل بساطة.

في دراسة الحاسوب النظرية, فإن هناك ما يسمى PDA, ببساطة push down automaton, ببساطة أكثر Stack :) و لكن الفرق أننا نطلق Stack على الكود المكتوب بلغات برمجة, و PDA عندما نتكلم عن الخوارزمية, دون أخذ الحجم و العوامل الحقيقية, و إنما عبارة عن مفهوم رياضي لا أكثر. عندما تريد كتابة Stack فأنت إما أن تقوم بكتابة Stack يخزن عناصره بشكل متجاور في الذاكرة أو أنك تخزن العناصر في سلسلة, و في كلا الحالتين فأنت قمت بتخزين العناصر على شكل Sequence. يمكنك بناء Stack تعتمد داخلياً على على vector أو أخرى تعتمد على list حسب رغبتك و حاجتك. و لكن هذا مضيعة للوقت, و تشتيت لمستخدم الـ Stack أو Stacks التي قمت ببنائها على اختلاف بنيتها الداخلية. لاحظ أن Stack و Queue كلاهما عبارة عن مفاهيم, و لا يهم سواء كانت العناصر مخزنة في list أو vector في النهاية المستخدم له دوال محددة يمكنه استخدامها في حالة كل واحد منهما. من الطبيعي أن نقوم باستخدام vector أو list لبناء Stack أو Queue بدلاً كتابة Sequence بشكل مضمن فيهما. سيواجهنا سؤال آخر, هذا السؤال هو ماهي الـ Sequence التي سنقوم باستعمالها كـ low level data structure؟!

علينا أن نقرر إما أن نبني نسختان, لكل من Stack و نسختان لكل من Queue, أو أن نوفر Generic Class بحيث ندع للمستخدم تحديد الـ Sequence المطلوبة وقت استخدام Stack أو Queue!

هنا يكمن الفرق بين STL و باقي مكتبات الـ Data Structure التي ستواجهها في حياتك كلها. كيف سنقوم ببناء Generic Data Structure, لأنها كل ما كانت عامة أكثر, كلما كانت ذا فائدة أكبر, و استخدمها المبرمجون بدلاً من استخدام أكواد يقومون بكتابتها لحالات خاصة. لن نمر من هنا قبل أن نلقي نظرة من بعد, عن الـ policy-based design. فكرة رائعة, و لكن تحتاج إلى تفتيح مخ قليلاً, ضع كل كتب OOP جانباً, و انظر إلى الـ Generic Programming على حقيقتها :)

نتكلم في الرد التالي,,,

تحياتي ....

سنتكلم في هذا الرد حول الـ policy-based design. و ماهو و كيف نطبقه, سنقوم بتطبيق الفكرة بطريقتين, الأولى بطريقة كائنية و الثانية بطريقة الـ Templates. سنرى قوة هذا المفهوم, و كيف أن OOP ليست كافية لحل جميع المشاكل التي سنواجهها. و بشكل أدق, كيف أن هناك حلول أفضل بكثير حسب مواصفات الأداء التي تكلمنا عنها في البداية, و كيف أن الناتج النهائي ليس Generic بشكل حقيقي!

ماهو الـ policy-based design:

حتى الآن, قلنا بأننا نريد بناء Generic Stack. هذه الـ Stack بسيطة جداً لذلك أخذتها كمثال. لنتصور أن الـ Stack توفر لنا هذه الدوال أو ما يسمى بالواجهة:

class stack
{
public:
	int& top();
	void pop();
	void push(const int& element);
	bool isempty();

private:
	// .....
};

حسناً و لكن من يحتاج إلى Stack عناصره عبارة عن int ؟! ربما يريد المستخدم أن يكون عبارة عن stack of double أو أي كائن يريده! المستخدم يريد Stack و لكن ليس من الضروري أن تكون فقط لـ int!

أول خطوة هو أن نقوم هو أن نجعل مستخدم الـ Stack يحدد نوع العناصر, بدلاً من توفير Stack لكل نوع, الحل الكائني يتلخص في التالي:

class object
{
	// type of stack elements.
	// it is a dummy class!
};

class stack
{
public:
	object* top();
	void pop();
	void push(const object* element);
	bool isempty();

private:
	// .....
};

هل تلاحظ أصبح الـ Stack بإمكانه التعامل مع object, أو أي نوع منحدر من object. بمعنى أنني إذا أردت تخزين أي نوع في Stack, فكل ما علي هو الوراثة من object و تطبيق مبدأ الـ Polymorphism لا أكثر:

class myclass : public object
{
	// any class!
};

.....

stack s;
object* obj = new myclass;
s.push(obj);
...
myclass* element = dynamic_cast<myclass*>(s.top());

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

العيب الأول, إذا كانت اللغة تفرق بين الأنواع الأساسية, و بين الـ Classes و بالتالي فالكائنات تختلف عن int و double و غيرهم, كما في #C و Java, فيجب بناء Stack لكل نوع اساسي! أو أن نقوم ببناء كائنات خاصة اسمها Integer و Double و ....

ثم عند استخدام الأنواع الأساسية يتم معاملتها معاملة خاصة من قبل اللغة! هذا يسمى الـ Boxing و الـ Unboxing:

stack s;
Integer n = new Integer(4); // Integer inherits from object!
s.push(n);

هل ترى هذه اللفة الأليمة للتغلب على عيب في التصميم! الـ Stack الذي قمنا ببنائه, أخيراً أصبح يستقبل أي نوع, في Java و #C تم استحداث ما يمسى بالـ Autoboxing!

stack s;
s.push(3); // = s.push(new Integer(3));
int n = s.top(); // convert from Integer to int

في السطر الثالث, فإن عملية التحويل من Integer إلى int تستدعي تعديل اللغة, و توفير ميزة في اللغة اسمها Autoboxing للقيام بما رأيته.

العيب الثاني, هو أن الـ Stack الذي قمنا ببنائه, يستطيع حمل أي نوع يرث من object! تصور أن مستخدم الـ Stack أراد Stack من النوع Double ثم أضاف String و كلاهما يرثان من object:

stack s;
Double d = new Double(6.5);
String s = new String("khaled!");
.....
s.push(d);
s.push(s);

لايستطيع المترجم اكتشاف الخطأ بأي صورة! فأنت بالفعل أضفت كائنات من النوع object سواء كان ذلك الوريث الأول أم الثاني. متى سيظهر الخطأ إذاً ؟

سيظهر عندما تريد التعامل مع أي من العناصر:

Double* d = dynamic_cast<Double*>(s.top()); // run-time ERROR!

ستفشل عملية تحول كائن النص إلى Double! و هذا يعني أن المستخدم لا يمكن أن يثق بـ Stack و يجب عليه فحص نوع العنصر الذي يقرأه من الـ Stack في كل مرة, و هذا يعني يجب أن تكون الـ Exceptions حاضرة دائماً حيثما أردنا التعامل مع Stack!

العيب الثالث, هو عملية التحويل التي ليس لها داعي أصلاً! لأنني أردت Stack مكونة من Double و ليس أي Stack! فلماذا أخزن عناصري في صيغة أخرى object و عندما أقرأها أحولها إلى Double!

العيب الرابع ندعه للمقارنة بين الـ OOP و الـ Templates في هذه السلسلة, بعد أن نستعرض طريقة الـ Generic Programming و بالأخص طريقة ++C :wink:

يكمل بإذن الله,

تحياتي ..

انتهينا من بناء Generic Class. هذا هو التطور الطبيعي, لهذه الـ Class, فقد بدأنا بـ Stack لـ int ثم قمنا بتعميمها إلى Stack يحدد نوعها المستخدم, رأينا كيف أن عيوباً عديدة بدأت تظهر في تصميمنا. و الأهم من ذلك أننا نريد تطوير الـ Stack إلى واحدة أكثر عموماً!

الـ Stack من الكود الجامد الغير قابل للتكيف, إلى الـ Generic Stack الحقيقي:

نتكلم عن الـ Stack هنا لأنها بسيطة جداً, و لكنها مثال حقيقي يوصلنا إلى مفهوم الـ policy-based design. لنبني Generic Stack, فإننا ننظر إلى مكونات تلك الـ Stack. هناك مكونان, الأول نوع العناصر, و الثاني هو البنية الداخلية لتلك الـ Stack. هل تذكر يوم أن قلنا هل سنضطر إلى بناء نسخين, الأولى تعتمد على list و الثانية على vector ؟! تلك بالضبط مهمتنا الآن, لأننا سنقوم ببناء Stack تسمح للمستخدم بتحديد نوعها, و إضافة إلى ذلك فإننا سنسمح للمستخدم باختيار vector أو list لحظة استعمال ذلك الـ Stack:

class stack
{
public:
	// pass the sequence in the constructor
	stack(Sequence* vSeq) { seq = vSeq; }
	object& top();
	void pop();
	void push(const object& element);
	bool isempty();

private:
	Sequence* seq;
};

ماهي Sequence ؟!

Sequence عبارة عن واجهة اخترعناها بالضبط كما هو الحال في object, لكي نسمح للـ Stack باستقبال أي نوع من الـ Sequences لحظة استخدامه!

فمثلاً سيصبح بإمكاننا التالي:

stack sv(new vector);
stack sl(new list);

هل أصبحت Generic كفايةً ؟! بالطبع, أكثر من هذا قد يعتبر overdesign و ربما أصبح استخدامها معقداً, من يدري!

هل أصبنا الأهداف التي وضعناها قبل البدء بهذا التصميم الكائني ؟!

بالطبع ليس بشكل كامل, و الدليل أن هناك حلول أفضل بكثير, سنراها في الرد القادم :)

هذا هو الـ policy-based design. ليس هناك شيء جامد, و لكن كل قطعة كود عبارة عن مجموعة أدوات تعمل معاً, و يمكننا استبدال ما نشاء بما نشاء متى ما أردنا. أتمنى أن تكون غرابة التسمية قد زالت عن policy-based design, بمعنى أن قطع الكود محكومة بقوانين فيما بينها,

فالـ Stack يطلب Sequence و التي بدورها تعتمد على قطع أخرى من الكود. و بذلك نستطيع مزج الأدوات مع بعضها للحصول على أداة نستخدمها في النهاية, بحيث ينتج عن مزج الأدوات Abstraction مناسب لمبرمجي التطبيقات. مبرمجو التطبيقات يحتاجون إلى Abstraction جاهزة, لكي يقوموا ببناء تطبيقات تحتك مع المستخدم النهائي.

كل ما رأيته منذ بداية تصميم الـ Stack حتى الآن, كان في محاولة جعل الـ Stack قطعة يسهل استخدامها مجدداً, هذا هو شعار كل مبرمج Reusability -_-

أصبح الـ Stack الخاص بنا, عاماً إلى حد أن لم يعد هناك حالات أخرى من حالات الاستخدام, يمكن أن نغطيها. كما رأينا أن لحلنا عيوب, و لنتفادى تلك العيوب يجب أن ننظر إلى أدوات أخرى غير OOP.

لا تفهم من هذا الكلام أني أريد إزالة OOP من حياتك :lol: على العكس, نريد مزج الأدوات, لا أن نجبر على استخدام أداة واحدة لحل المشكلة!

سنبرمج بالـ Free Style إن أحببت تسميته بذلك, سنخلط أسلوب الـ Generic Programming مع أسلوب Data Abstraction مع أسلوب الـ Procedural Programming مع أسلوب الـ Functional Programming!!!!!

قائمة طويلة عريضة, لكن الفكرة أسهل مما تتصور :)

تحياتي ...

عندما انتهينا من تصميمنا الكائني الـ Generic للـ Stack. فإن بعض العيوب ظهرت, و ما سنراه في السطور القادمة, هو أننا سنجرب أداة أخرى لحل المشكلة, و هي الـ Templates. إن لم تكن تعرف ماهي الـ Templates فهي تشبه الـ Generics في Java و #C لمن يعرفهما أكثر.

الـ Templates عبارة عن Static Polymorphism وقت ترجمة البرنامج. هل تذكر كيف استخدمنا الـ run-time polymorphism لتمرير الـ Sequence و object ؟! المترجم لا يقوم بأي عملية تحقق, و بالتالي فإن مستخدم الـ Stack كان يجب عليه التحقق من أخطاء معينة كنوع العنصر, و تحويل المؤشر الذي يستقبله من الـ Stack, إلى النوع المراد.

الـ Templates تقوم بتوفير الحل. تصور أن الـ Templates عبارة عن OOP وقت الترجمة, و أن ما بين الأقواس:

template <...>

عبارة عن الـ Constructor في عالم OOP:

template <typename type>
class stack
{
public:
	type& top();
	void pop();
	void push(const type& element);
	bool isempty();

private:
	// .....
};

لاحظ أننا اخترعنا نوع جديد أسميناه type, يقوم المستخدم بتحديده وقت استخدام الـ Stack, فمثلاً:

stack<int> s;
s.push(5);

الذي يحصل بالضبط, هو أن المترجم حينما يرى:

stack<int>

فإنه يقوم داخلياً, بعملية استنساخ للـ Template الأصلي, و بناء class جديدة اسمها stack و لكنه يستبدل type في أي مكان يراه بـ int و يحفظها في مكان داخله, للاستعمال مرة أخرى إن قام المستخدم بتعريف stack من نوع int مرة أخرى.

class stack
{
public:
	int& top();
	void pop();
	void push(const int& element);
	bool isempty();

private:
	// .....
};

الآن هل ترى ما الفرق بين طريقة OOP و بين طريقة الـ Templates ؟

الفرق هو أن المترجم يقوم بإنشاء كود لـ stack من نوع int كما لو أنها كتبت يدوياً! و بالتالي الحصول على جميع المزايا و المنافع التي يمكن الحصول عليها, دون التضحية بعمومية الـ Stack التي نقوم ببنائها.

عيوب OOP اختفت, و ظهر مكانها القوة. فأصبح بإمكاننا استخدام أي نوع, سواء كان ذلك النوع عبارة عن class أو نوع أساسي في اللغة. و حل معها مشكلة التحويل من النوع الذي يستطيع الـ Stack حمله, بجعله نوعاً وهمياً, بحيث يقوم المترجم بتلك المهمة,

فبعد إنشاء Stack حقيقية من النوع int, لا يمكن بحال من الأحوال أن يعمل السطر التالي, الذي كان يعمل بشكل (خاطئ, خفي) في حالة OOP:

stack<int> s;
string s = "Khaled!";
s.push(55);
s.push(s); // oops...ERROR! compiler is smart!

بالطبع لم يعد هناك حاجة على الإطلاق للتحقق من نوع العنصر عند أخذه من قمة الـ Stack لأن المترجم قام بالتحقق من ذلك مسبقاً! هذا يسمى Exception Safe Design!

int element = s.top(); // 100% sure, there are only int(s) in stack!

بالنسبة للعيب الرابع الذي تعرضنا له في التصميم الأول, و هو أداء الـ Stack, فإننا سنتعرض إليه, بعد أن نلقي نظرة على تطويرنا الأخير للـ Stack بالـ Templates لكي نرى كيف ستصبح عملية اختيار الـ Sequence المطلوبة!

نلتقي من جديد,

تحياتي ...

ماشاء الله اخي Khaled.Alshaya موضوع اكثر من رائع و يعتبر متقدم تقنياً, انا متابع معك ولكن لدي سؤال لم افهمه:

ما الفرق بين استخدام Sequence في ال Stack و بين استخدام Object لم افهم كثيراً ارجوا التوضيح اكثر.

ايضا لدي سؤال أخر: كيف يمكن صنع Stack نخزن فيه جميع انواع البيانات التي نريد مع امكانية استرجاعها في اي وقت دون حصول اخطاء؟!

أهلاً أخي وائل :)

اقتباس

ما الفرق بين استخدام Sequence في ال Stack و بين استخدام Object لم افهم كثيراً ارجوا التوضيح اكثر.

مانريده, هو أن نبني Data Structure و لكنها تكون صالحة للاستخدامات العامة, أي نريدها Generic. بالطبع عندما نقول عن شيء بأنه Generic فهذه فكرة, يمكن أن نطبقها بأدوات عديدة. تكلمنا عنها باستخدام OOP و تكلمنا عن استخدام الـ Templates أيضاً.

أخذنا Stack كمثال. و أردنا أن نصممها بشكل احترافي, بالطبع, لكي تكون تلك الـ Stack مصممة بشكل احترافي للاستخدام الدائم, كقطعة Reusable, يجب عليها قبل كل شيء أن تطيع المستخدم. فالمستخدم لايريد أن يقوم بعملية قص و لصق, ثم يقوم بعملية بحث و استبدال عن طريق محرر نصوص, لتبديل نوع العناصر في الـ Stack! أليس هذا صحيحاً ؟ ما يريده المبرمج هو أن تكون اللغة نفسها تدعم الـ Reusablility. تكلمنا عن أداتين في ++C الأولى OOP و الثانية الـ Templates, و كلاهما يسمح لك بجعل الكود Generic و لكن بطريقتين مختلفتين.

بالنسبة لـ Sequence فقلنا بأن الـ Implementation الخاص بالـ Stack لهم إن كان list أو vector داخلياً, و لكن لجعل الـ Stack أقوى, سندع المستخدم يحدد نوع الـ Implementation لحظة استعماله للـ Stack, و أعطينا مثال:

stack sv(new vector); // create vector, and let the stack use it!
stack sl(new list); // // create list, and let the stack use it!

بالطبع كلاهما يرثان الواجهة Sequence. كما ترى Sequence عبارة عن مفهوم, هذا المفهوم, يمكن أن يقوم مقامه vector أو list أو أي Data Structure تمثل متتابعة من العناصر في داخلها.

بالنسبة, لـ object, فنحن إن أردنا أن نجعل الـ Stack تقبل أي نوع, بمعنى أننا نريد Stack مكونة من عناصر string ثم أردنا استعمال الـ Stack class من جديد مع نوع آخر كـ double, فإننا لن نستطيع فعل ذلك بشفافية, و إنما يجب أن نبني هرماً وراثياً و نجعل الصنف الأساسي فيه الذي يرث الجميع منه, كـ نوع لعناصر الـ Stack التي قمنا ببنائها. و كما رأيت, في حالة كون اللغة تفرق بين الأنواع الأساسية و بين الكائنات, ستبدأ المشكلات بالظهور, و لن تنتهي!

أتمنى أن تكون الفكرة توضحت :)

أنا بدأت بهذا المثال, لكي يكون بوابة للدخول في عوالم STL العجيبة, و هذه مازالت البداية لا أكثر, و إن شاء الله يتضح الكثير مع الأيام القادمة,

تحياتي ...

يبدوا أنك من مغرمي STL و أمور ال Generic, أمور في غاية الأهمية فإي شخص يهمه زيادة ال Performance لتطبيقه يجب عليه الغوص في STL و استخدام اللوائح السابقة,شكرا لك على التوضيح ما قصدته بسؤالي الآخر شيئ من هذا القبيل:

و من ثم لاستخدامه نقوم بشيئ مثل

أخي الغالي Khaled.Alshaya

والله كاني ودي ان اواصل معاكم هاي الشرح الرائع لكن للاسف

الى الان لم افهم هاي الشباتر

1-Arrays,Records and Pointers

2-Linked Lists

3-Stacks,Queues,Recursion

4-Trees

ياليت تساعدنا وتدلنا على كتاب عربي يشرح هاي الشباتر او مضوع في المنتدى يشرح الداتا من الصفر

لا اتستطيع فهم ما هو مكتوب الان سوى اني اعرف العناوين وكيفيت عملها مثل stack queue اعرف كيف تعمل ولم اطبقها

ياليت تدلنا على موضوع يفيدنا

أهلاً وائل :)

اقتباس

ايضا لدي سؤال أخر: كيف يمكن صنع Stack نخزن فيه جميع انواع البيانات التي نريد مع امكانية استرجاعها في اي وقت دون حصول اخطاء؟!

جميل فهمت السؤال, تريد تخزين مجموعة أنواع, أي أن الـ stack أو الـ Data Structure التي نتعامل معها Heterogeneous. رغم أن هذا السؤال سابق لحينه, إلا أني سأعرض مالدي حول الفكرة, و بعض الأمثة التي يمكنك تطبيقها في ++C.

سنستعرض طريقتين, الأولى باستخدام OOP و الثانية باستخدام الـ Generic Programming و بالتحديد الـ Templates في ++C, و لكننا سنتكلم عن Boost حصراً في حالة الـ Templates :)

لو عدنا للمثال الأول باستخدام OOP:

class object
{
	// type of stack elements.
	// it is a dummy class!
};

class stack
{
public:
	object* top();
	void pop();
	void push(const object* element);
	bool isempty();

private:
	// .....
};

في Java على سبيل المثال, فإن جميع الكائنات ترث من Object. بالتالي فإن الـ Stack التي سنقوم ببنائها و تعتمد على Object تستطيع حمل أي كائن آخر, لأنه في النهاية الجميع يرث منها. بالنسبة لتخزين النوع, فهذا لاداعي له أصلاً, لان الـ run-time environment يجب أن تحمل جميع المعلومات المطلوبة حول الكائن الذي قمنا بتخزينه في الـ Stack. فمثلاً في Java, يمكنك قول شيء كهذا:

stack s = new stack();
s.push(new String("Wael"));
s.push(new Double(1.0));

المشكلة ليست في إدخال الكائنات إلى الـ Stack فيمكنك إدخال ما تريد, و لكن المشكلة أننا لا نعرف نوع الكائن الحقيقي, و إنما نتعامل مع واجهة(في هذه الحالة Object Class). و لمعرفة النوع الحقيقي لكائن موجود في الـ Stack فيمكنك القيام بشيء كهذا:

Object o = s.pop();
String str;
if(o instanceof String)
  str = (String)o;

بالطبع الكلام في الأعلى ينطبق حتى لو كنت تريد تخزين أكثر من نوع في نفس الـ Stack فليس هناك شيء يمنع:

Object o = s.pop()
String str;
Double number;

if(o instanceof String)
  str = (String)o;
else if(o instanceof Double)
  number = (Double)o;

instanceof كل ما تقوم به هو أن تعيد true إذا كان o من النوع الذي نقوم بالتحقق منه.

هذا يدخلنا في متاهات الـ Exceptions لمشكلة يمكن أن تحل من الأساس بالتحقق وقت الترجمة, بالطبع يجب أن تدعم اللغة الـGenerics, فمثلاً في Boost يوجد أداتان لحل المشكلة, الأولى هي بالطريقة الكائنية و تسمى any و الثانية تسمى variant.

بالنسبة لـ any فهي تقوم بالضبط بما تكلمنا عنه في حالة OOP. بينما variant فإنها تتبع الـ Generics

typedef boost::variant<int, std::string> var;
stack<var> s;

s.push(5); // OK!
s.push("Khaled!"); // OK!
s.push(5.0); // Error! Compiler catch it!

سنتكلم عن هذا الموضوع بشكل موسع, لأن هذه النقطة جميلة جداً في عالم الـ Generics :)

تحياتي ...

سأحاول إكمال ما تبقى بإذن الله من مثال الـ Stack باستخدام الـ Templates. نحن قمنا بالفعل بجعلها تقبل أي نوع, و بقي علينا أن نتيح للمستخدم حرية اختيار الـ Container المناسب له لحظة استعمال الـ Stack. هل تذكر كيف قمنا بتمرير النوع باستخدام الـ Templates ؟

template <typename type>
class stack
{
.....
};

بنفس الطريقة سنقوم بتمرير الـ Container الذي نريده!

template <typename type, typename Container>
class stack
{
.....
};

إذا كنت شديد الملاحظة فسيتوضح لك ما أريد فعله بـ Container مباشرة! كلا type و Container عبارة عن أنواع مجهولة, و بالتالي كما أمكنني استخدام type لتحديد النوع الذي نريد تخزينه, يمكنني بكل بساطة تعريف متغير داخل الـ Stack ليكون الـ Container!

template <typename type, typename Container>
class stack
{
public:
	type& top();
	void pop();
	void push(const type& element);
	bool isempty();

private:
	Container<type> c;
};

الآن أصبح بإمكاننا استخدام c أينما أردنا, فمثلاً سيصبح شكل الـ Stack:

template <typename type, typename Container>
class stack
{
public:
	type& top() { return c.lastElement(); }
	void pop() { c.remove(topElementIndex); topElementIndex--; }
	void push(const type& element) { c.push_back(element); }
	bool isempty() { return c.size() == 0; }

private:
	Container<type> c;
};

بالطبع يمكنك استخدام الكود كالتالي على سبيل المثال:

stack<int, myvector> s1;
stack<String, mylist> s2;

كما تلاحظ مررنا النوع myvector من خلال الـ Templates Parameters, الشيء الوحيد المطلوب من النوع myvector أو mylist هو أن توفرا الدوال التي استعملناها في داخل الـ Stack كما تلاحظ عندما عرفنا كائناً من نوعها اسمه c.

إذا لم يجد المترجم هذه الدوال, فإنه سيقوم بالإعتراض و إصدار خطأ وقت الترجمة, يعملنا فيه أن myvector لايحقق الشروط المطلوب لكي يكون Container داخل الـ Stackالتي يقوم المبرمج باستخدامها.

الآن بعيداً عن الـ Type Safety و توفر المترجم بجانبنا عند حصول انتهاك شنيع في كودنا, هنا أمر أكثر أهمية بكثير, و هو ما يجعل ++C الخيار الأول عندما يكون لدينا تصاميم معقدة و في نفس الوقت نريد الحفاظ على أداء معقول!

كلامنا التالي, سيكون عن الفرق بين ما كتبناه باستخدام OOP و ماكتبناه باستخدام الـ Templates.

أنا متأكد أني وضعت الكثير من الكود دون شرح كاف, و لكن ذلك فقط لكي تأخذ نظرة, و بعدها سنفصل خطوة خطوة, كيف سيفرق كود الـ Templates عند استعماله عن كود OOP من ناحية أدائه.

تحياتي ...

الآن سنلقي نظرة على كيفية عمل الـ Templates, و السبب أنها سهلة إلى أبعد الحدود, و لكنها عصية على الفهم أحياناً. بكل بساطة, سنتعرف على كيفية تعامل المترجم مع الـ Templates.

لكي نفهم ماهية الـ Templates, فإنه لابد في البداية أن نفهم سبب وجودها. و سبب وجودها الحقيقي, هو ملاحظة علماء الحاسب الكبار كمصممي ADA و غيرهم مثل Stroustrup, أن المترجم يمكن ان يقوم بالمزيد من العمل, بدلاً من ترك مهمة التحقق من كثير من الأمور للمبرمج. بالطبع المبرمج سيقوم بعمليات التحقق من ضمن الكود الذي يقوم بكتابته, و بالتالي فإن عمليات التحقق هذه تحصل وقت تشغيل البرنامج, ضمن منطق البرنامج نفسه. لتفادي هذه اللخبطة, تم تطوير ما يسمى بالـ Generics, هذه الـ Generics تشبه الـ Polymophism إلى حد كبير. الفرق أن OOP تطبق الـ Polymorphism لحظة تشغيل البرنامج, و الـ Generics تطبقها لحظة ترجمة البرنامج.

فمثلاً, تصور أن لدينا الهرم الكائني التالي, أحد أشهر الأمثلة في الجامعات - مبرمجو OOP يحبون الحيوانات كثيراً :lol: :

class Animal
{
public:
	virtual void eat();
	.....
};

class Tiger : public Animal
{
public:
	virtual void eat()
	{
		std::cout << "Tiger is eating";
	}
	.....
};

class Lion : public Animal
{
public:
	virtual void eat()
	{
		std::cout << "Lion is eating.";
	}
	.....
};

ماهي الفائدة الوحيدة التي تتوقعها من هرم كائني كهذا ؟ بكل بساطة يسمح لنا بالقيام بالتالي:

void printAnimal(Animal* animal)
{
	animal->eat();
}

الفائدة من هذا الكود هو أننا ببساطة عندما نريد إضافة Class جديد يرث من Animal, و لديه دالة تسمى eat مثل كل الكائنات التي ترث من Animal, فلن نحتاج إلى تغيير حرف واحد في الدالة print. بالتالي, يمكننا تطوير الهرم الوراثي, و جعل الدوال عامة بشكل تام. بشكل أبسط, عندما نمرر Animal, مهما كان ذلك الـ Animal فإننا نفترض وجود مجموعة دوال موجود في كل Animal! هذه هي الفائدة كلها من وراء الـ Polymorphism! أضفنا Cat, إلى الهرم, جميع الدوال التي تتعامل مع Animal ستقبلها بشكل تلقائي.

الآن تصور أننا لم يكن لدينا Polymorphism. مالذي كان يجب عمله لمحاكاة OOP ؟ يمكننا أن نتبع الطريقة الـ Procedural كما في Pascal أو C, فإما أن نقوم بعمل دالة طباعة لكل نوع struct أو Record سمه ما شئت:

void printTiger(struct Tiger* t);
void printLion(struct Lion* t);

أو أن نقوم بكتابة دالة طباعة عامة, و نضع معلومات النوع نفسه, ضمن الـ struct أو Record

void print(struct Animal* animal)
{
	switch(animal.type)
	{
		case 0; // Tiger
			animal->eat();
			break;
		case 1; // Lion
			animal->eat();
	}
}

كما ترى, في حالة الكود الـ Procedural فإن إضافة أي نوع تعني المساس بـ print, سواء كان ذلك بإضافة printNewAnimal جديدة, أو بتعديل switch ضمن كود print إذا كانت عامة. OOP توفر الحل, و ذلك بأن يقوم المترجم نفسه, بإدراج switch ضمن الكود بدلاً من المبرمج, و بشكل تلقائي. بالطبع المترجم سيضيف معلومات لكل نوع ضمنياً و تلك بالطبع من ضمن بيانات الملف التنفيذي الناتج, فالمترجم لا يقوم بهذه المهمة ببلاش!

عندما تكلمنا في البداية, قلنا بأن مكتبات الـ Data Structure, لايتصدى لها إلا الخبراء, و كتابة كود يتصف بصفتين متعاكستين, أولاً يجب أن يكون Efficient و الأهم أن يكون Reuseable.

الآن لنقم بكتابة, الكود الذي قمنا بكتابته في الأعلى و لكن بطريقة Generic. سيتضح لك أن switch التي رأيناها في الأعلى, لن يعود لها فائدة!

فنحن يمكن أن نقوم بكتابة Tiger و Lion, كل نوع على حدة, دون وجود أي هرم وراثي على الأطلاق يجمعهما.

class Tiger
{
public:
	void eat()
	{
		std::cout << "Tiger is eating";
	}
	.....
};

class Lion
{
public:
	void eat()
	{
		std::cout << "Lion is eating.";
	}
	.....
};

و نقوم بكتابة print بهذه الطريقة:

template <typename Animal>
void print(Animal& animal)
{
	animal.eat();
}

الآن عندما نقوم باستدعاء الكود كالتالي على سبيل المثال:

Tiger tiger;
Lion lion;
......
print(tiger);
print(lion);

فإن المترجم يقوم برؤية نوع الكائن الممر إلى print. حينها, يذهب إلى الدالة print التي قمنا بكتابتها, و يستبدل Animal بـ tiger في print الأولى و الكود المستنسخ هو الكود الذي يقوم المترجم باستخدامه في الحقيقة بعد ذلك:

void print(Tiger& animal)
{
	animal.eat();
}

و في حالة Lion:

void print(Lion& animal)
{
	animal.eat();
}

و إن كانت العملية واضحة لك حتى الآن, فيجب أن تعلم أن هناك دالتان في الملف التنفيذي و ليس دالة واحدة. بالتالي, يقوم المترجم فعلياً بإنتاج دوال بعدد الأنواع المستخدمة. هل ترى كيف أن المترجم قام بعمل switch داخلياً ؟

مالذي يجعل الـ Templates أكثر كفاءة من OOP ؟

في الحقيقة إن تتبع العملية باختصار سيوضح لنا الكثير, ففي دالة print:

void print(Animal* animal)
{
	animal->eat();
}

يقوم المترجم في هذه الحالة, عند تنفيذ eat, برؤية نوع الـ Animal الممرر, و كل كائن أصلاً نقوم بإنشائه, يحمل معلومات عن نوعه, و بالتالي, يحدد الدالة المراد تنفيذها, هل هي موجود و إذا لم تكن موجودة فإنه يستدعي الدالة الموجودة في Animal, الذي يرث منه Tiger و Lion.

بالطبع, لكل class لابد من معرفة الدوال التي توفرها, إضافة إلى نوع الكائن, و معلومات أخرى هذا كله غير الـ member variables التي قمت بتعريفها فيه أصلاً!

بالطبع, نرى أن عملية استدعاء eat, ليست عملية استدعاء مباشرة, أي أننا يجب أن ننتظر حتى تشغيل البرنامج, و يقوم الكود الذي أدرجه المترجم بالتحقق من النوع و استدعاء الدالة المناسبة.

بينما في حالة الـ Templates:

template <typename Animal>
void print(Animal& animal)
{
	animal.eat();
}

فإن الدالة معروفة, و بالتالي يمكن للمترجم أن يقوم بعمل inlining مباشرة إذا استدعى الأمر, و هو ما يحصل في الحقيقة, و هذا يعني تخفيضاً في استخدام الذاكرة, إضافة إلى استدعاء الدالة مباشرة, إضافة إلى السهولة و المرونة في الاستخدام, ماذا بعد ؟ :P

كمعلومة جانبية, خوازمية الترتيب الموجودة في المكتبة القياسية لـ ++C, تتفوق على جميع خوارزميات الترتيب التي تأتي مع المكتبات القياسية لأي لغة :wink:

فبينما في Java يتم تطبيق مبدأ الـ Polymorphism لتمرير دالة مقارنة لدالة الترتيب, يتم عمل inlining لدالة المقارنة بشكل شبه دائم في مترجمات ++C.

يمكننا أن نلقي عليها نظرة, فيما بعد إن شاء الله,

تحياتي...

بارك الله فيك اخي خالد وزادك علما,, متابعين معك بإذن الله...

سأتكلم الآن, عن أول أداة في STL! و هي أشهر مكوناته بكل صراحة! رحبوا معي بـ vector :blush:

قبل أن أبدأ بعرض دواله و كيفية استخدامه و يصبح الأمر مملاً بالنسبة لي و لكم, دعني أطرح السؤال التالي, ماهو vector أو لنلقل ماهي الـ Dynamic Array التي يمثلها vector في ++C ؟!

إذا كنت تعتقد بأن الإجابة هي أن هناك Static Arrays و Dynamic Arrays لا أكثر و لا أقل, فلابد أن تقرأ السطور التالية.

هناك ثلاثة أنواع من المصفوفات حسب التقسيم الأشمل و الأعم بنظري. هو ليس تقسيماً نظرياً بمعنى الكلمة و إنما تقسيم عملي, و كل نوع ينقسم إلى قسمين.

سنطرح مثالاً لكل نوع, ثم سنناقش المثال.

النوع الأول: حينما يبدأ البرنامج أبدأ معه و أنا جزء منه, و أنتهي حينما ينتهي البرنامج!

double yourNumbers[5] = {0, 1, 2, 3, 4};
double myNumbers[5];

int main()
{

}

لاحظ أني وضعت main فارغة, لكي أشير إلى أننا بالفعل نقصد أن تلك المصفوفات معرفة كـ global variables, و ليست ضمن أي دالة حتى الدالة الرئيسية main!

هذا النوع من المصفوفات يأتي على شكلين, الشكل الأول, كما في yourNumbers, سيقوم المترجم بحفظ تلك القيم في الملف التنفيذي, و حينما سيعمل البرنامج, فإن المنطقة التي سيوضع فيها البرنامج ستحتوي على تلك المصفوفة أو بشكل أصح قيم تلك المصفوفة.

بالطبع سيخبرك أحدهم, بأنها قد توضع في الـ Data Section للبرنامج, و لكن هذا غير مهم بالنسبة لنا, و لكن معظم أنظمة التشغيل, تقسم المنطقة التي سيعمل منها البرنامج فب الذاكرة لحظة تحميله إلى قسمين. قسم للبيانات العامة Data Section و قسم آخر لكود البرنامج Code Section و تسمى في Windows و غيره Text Section!

يمكن للمترجمات أن تقوم بعملية جميلة, كما في الحالة الثانية myNumbers. كما تلاحظ أن هذه المصفوفة لم نملأها بالبيانات بعد, أو لنقل أننا لم نقم بعمل initialization. في هذه الحالة, فإن المترجم يستطيع الطلب من نظام التشغيل الذاكرة لحظة تشغيل البرنامج, و يتم تخزين حجم طلب الذاكرة العامة ضمن البرنامج, أو بشكل أصح ضمن Header الملف التنفيذي.

ماهي الفائدة من هذا النوع ؟

إذا كان لديك مصفوفة من العناصر الثابتة, و تريد تعميمها على البرنامج كله و تريد السماح للجميع بالوصول إليها, فلا مانع من جعلها عامة بهذه الطريقة.

الأمر الآخر, إن كنت تستخدم C و تعمل على إنتاج برنامج لـ Embedded Processors فأنت في الغالب تعرف هذا الموضوع قبل أن اتكلم عنه :)

تحياتي....

النوع الثاني : حينما تعمل الدالة, أكون موجوداً, و حينما تذهب أذهب معها!

أحد أشهر الأخطاء الشائعة, و الشنيعة لدى متعلمي C هو الخطأ التالي:

int* function()
{
	int a[5] = {0, 1, 2, 3, 4};
	return a;
}

و كما تلاحظ قمنا بإعادة عنوان المصفوفة, و لكن أي مصفوفة ؟! الحقيقي أن المصفوفة a يتم إنشاؤها على الـ Stack الخاص بالبرنامج. و بمجرد الخروج من الدالة, فإن المنطقة التي توجد عليها a تصبح حرة للاستعمال من جديد.

هذا النوع من المصفوفات يحاكي الـ local variables. و كلاهما بالفعل يتم إنشاؤه على الـ Stack!

قد تعتقد في بداية تعلمك للغة C أنه لا يمكنك تعريف مصوفة متغيرة الحجم على الـ Stack! في الحقيقة أن هذا ممكن و عائد لمرونة C في عزل اللغة عن المكتبات:

void* p = alloca(12); // 12 bytes on the STACK!
int* i = (int*)p;

يمكنك القيام بهذا الشيء في C و ++C! كل ما تقوم به alloca هو حجز الذاكرة على الـ stack الخاصة بالدالة حتى لو كانت الحجم غير معلوم وقت كتاب البرنامج, أي أنها بالضبط كـ malloc و new من هذه الناحية.

أود التعليق على الموضوع هنا قليلاً :)

المشكلة في حجز المصفوفات على الـ Stack هو أن أنظمة التشغيل لا تسمح بأخذ مساحة كبيرة جداً, كما هو الحال في الذاكرة الحرة heap. و لكن عملية حجز الذاكرة على الـ Stack ذات سرعة عالية جداً, و هي عبارة عن تعليمة في لغة الآلة لا أكثر. بينما الحجز على في الـ heap يعتبر مكلفاً إذا قمت بالحجز بشكل دوري. لأن عملية الحجز من الـ heap تستدعي البحث عن مساحة فارغة تناسب الحجم, و لا ننسى أن المعلومات حول المساحات الفارغة و المساحات المحجوزة يجب أن تكون مخزنة هي الأخرى! و بالتالي هي عملية معقدة فعلياً!

دخلنا في الموضوع, هو أن نطلع على أحد البرامج الحقيقية و كيف استفاد من مرونة ++C و خصوصاً الـ policy-based design. برنامجنا الجميل هو Google Chrome :)

أراد مصممو البرنامج سرعة عالية جداً في حجز مصفوفات لاستخدامها بشكل متكرر, و لكن كما قلنا بأن عنق الزجاجة سيصبح في عملية الحجز من الذاكرة. لو أنك تعمل بلغة تحد من المرونة من أجل السهولة, لقمت ببناء vector جديد, أو لنقل مصفوفة ديناميكية جديدة, تتم عملية الحجز فيها على الـ Stack. و لكن لماذا نبني مصفوفة ديناميكة جديدة, و كل ما نريد تغييره هو عملية الحجز ؟!

vector في ++C يستقبل Template Parameteres. و هم كالتالي:

template <class type, class allocator = std::allocator<type> >
class vector
{
.....
};

كما ترى يجب علينا تمرير شيئين, الأول هو نوع بيانات العناصر, و الثاني هو الـ Allocator. ببساطة الـ Allocator عبارة عن مجموعة دوال لحجز الذاكرة. فبدلاً من أن يقوم vector باستدعاء new و delete أو malloc و free بشكل مباشر, يقوم باستدعاء دوال الـ allocator الممر. و إذا لم تمرر بإنه بشكل افتراضي يقوم باستخدام الـ allocator القياسي الموجود في المكتبة القياسية, و الذي بدوره يستخدم دوال حجز الذاكرة القياسية كـ new و delete و غيرهم دون أن نشعر. هل تسائلت يوماً ماهو الـ Allocator :P

قام مطورو Chrome ببناء Allocator جديد, لحجز الذاكرة على الـ Stack. و استخدموه مع العديد من الـ Containers الموجودة في STL للحصول على أقصى سرعة!

تصور لو أن المطلوب هو بناء مكتبة جديدة يعتمد الحجز فيها على الـ Stack! هذه STL العجيبة التي لا يقدرها الكثيرون في صلب برنامج حقيقي :wink:

يمكنك الحصول على الكود الذي قام مطوروا Chrome بكتابته من هنا:

stack_container

تحياتي, و إن شاء الله المرة القادمة نختم الكلام بآخر نوع من المصفوفات, و نتكلم حينها عن vector

تحياتي...

النوع الأخير من المصفوفات هو المصفوفات التي نحجزها من الـ heap.

هذا النوع نقوم بطلبه وقت تشغيل البرنامج من نظام التشغيل, أو بمعنى أصح من مدير الذاكرة الموجود في نظام التشغيل, و إن لم يكن هناك نظام تشغيل, و كنت تبرمج دون نظام تشغيل, فإنه عليك بناء memory manager مناسب لاحتياجك إن كنت تريد استخدام دوال حجز و تحرير الذاكرة!

مايميز هذا النوع, هو المرونة الفائقة التي يوفرها, فإبمكاننا الاستعاضة عن جميع أنواع المصفوفات بهذا النوع, و لكن للأسف ليس هناك شيء كامل, لأن المرونة التي يوفرها هذا النوع, تأتي على حساب تعقيد الـ memory manger. فمثلاً الـ global arrays أسرع الأنواع و أقلهم تكلفة. و لكن هذا لا يعني أن لا نستخدم الـ dynamic memory, على العكس إن كنت تبرمج في لغة لا توفر هذا النوع فأنت بالتأكيد تبرمج باستخدام Fortran القديمة على أصولها :lol:

عموماً, لا يجب أن نخلط بين أمرين, الأمر الأول هو المصفوفات التي نحجزها في الـ heap. و هذه بمجرد حجزها فإننا لا يمكن أن نغير حجمها, و لذلك نضطر لبناء الحالة العامة من أنواع المصفوفات, و هي الـ Dynamic Array. فهذا النوع, يمكنك من الإضافة و الحذف و إدراج عناصر جديدة بين عناصره الموجودة أصلاُ فيه, و يسهل عملية التعامل مع المصفوفات التي تحجز على الـ heap إلى درجة كبيرة. عندما بدأنا الموضوع, تكلمنا عن الـ Generics و دخلنا في OOP لكي نصل إلى هذه النقطة. أن المبرمجين يحتاجون إلى أدوات عامة. و لا يجب عليهم استخدام الأدوات الخاصة إلا في الحالات الخاصة! و لذلك ستجد أن الـ Dynamic Arrays هي ما يستخدمه المبرمجون في 99% من الأوقات, و ليس الأنواع الأخرى, لأنه من الممكن أن تحل مكان أي نوع آخر, مع ميزة إضافية و هي أننا معتادون على أدواتها الجاهزة, بدلاً من القيام بما تقوم به مباشرة في كودنا!

عموماً, أنا متأكد بأنك لا تتعلم STL هنا, و لتعلم STL عليك بأمهات الكتب لأصحاب المكتبة و كبار المبرمجين. لذلك بما أننا وصلنا إلى هذه النقطة, سنطلع بعد ذلك على مفهوم الـ Sequence في STL. و كيف أنه بإمكاننا معاملة أي من list و vector و deque بنفس الطريقة تماماً. و سنطرح بعض الأمثلة على كتابة Generic Code لهم بطريقة احترافية.

تحياتي...

اخي الكريم

شرحك رائع جداً يمزج بين التطبيق النظري والعملي ... درست ه>ا الموضوع ايام الكلية لكنني لم افهمه خصوصا الاكواد كما الان .. وبالفعل الstack مهم لانه يستخدم كثيرا وبالاخص في قراءة الصور

جزاك الله عنا بمليون خير وجعله في ميزان حسناتك ... شكرا جزيلا ولي عودة ان شاء الله

ما شاء الله موضوع ممتاز

فيه بعض الملاحظات

لنفترض اني كتبت دالة بالشكل الاتي

void SaveToFile(Animal *animal)
{
file.write(static_cast<Animal*>(animal),sizeof(Animal));
}

اذا كان عندي بناء هرمي كالسابق في هذه الدالة الن احتاج لمعرفة نوع Animal باستخدام RTTI حتي امرر الحجم المظبوط الي الدالة write

لي طلب كيف ابدأ بتعلم Boost library ال Documentation مش واضح ؟؟؟

اقتباس

اذا كان عندي بناء هرمي كالسابق في هذه الدالة الن احتاج لمعرفة نوع Animal باستخدام RTTI حتي امرر الحجم المظبوط الي الدالة write

لاحظ أن Animal ليس POD, هو Polymorphic Type. و الـ Layout Representation له في الذاكرة, ليس محدداً من قبل اللغة نفسها, و بالتالي كل مترجم يمكن أن يقوم بتخزين "الكائن" بطريقته الخاصة.

لذلك العملية من الأساس و افتراض أن الكائن الذي يشير إليه المؤشر الذي نملكه بياناته متجاورة في الذاكرة, خاطئ من الأساس.

يجب علينا أن نقوم بعمل Serialization لكل member في Animal, حتى يتم الأمر بشكل صحيح, و الكلام السابق ينطبق على العناصر الـ Polymorphic أي مثل Animal, بحيث نقوم بعمل Serialization لذلك الـ Type بالتفصيل.

عموماً, مسألة الـ Serialization ليس سهلة كما تتصور, و الافضل أن تلقي نظرة على "مكتبات" الـ Serialization مثل boost::serialization أو Google Protocol Buffers.

اقتباس

لي طلب كيف ابدأ بتعلم Boost library ال Documentation مش واضح ؟؟؟

و الله أنا أرى العكس, أن أفضل مافي هذه المكتبة هي الـ docs. لاحظ أنهم يعطون الكثير من الأمثلة من البسيط و حتى البرامج الكاملة, لتوضيح عمل المكتبة هذا بالطبع غير المراجع.

إذا كنت تفضل قراءة الكتب, فلا مشكلة, ألقي نظرة على الكتاب المرفق كبداية, و من ثم جرب قراءة الـ docs الخاصة بكل مكتبة,

و لا تنسى أن Boost ليست Framework بل عبارة عن قطع منفصلة يمكن تعلم إحداها بكل سهولة, و اختيار ما تريد, لأن فيها الكثير من المكتبات "المتقدمة جداً", و لن تفيدك إلا إذا كنت تقوم بتصميم "مكتبات".

بعض المواضيع المتعلقة:

هل تستخدم Boost ؟

قم ببناء Boost خطوة بخطوة

تحياتي,

Beyond The C++ Standard Library - An Introduction To Boost (2005) - allbooksfree.tk.chm