کلاس map در stl - ابهامها و سوالها

[Sepidar]

سلام
برای ذخیره سازی اطلاعات در یک پروژه احتیاج به یک درخت دودویی دارم.
اگر چه کلاس map در این زمینه وسوسه کننده است، اما در بعضی مستندات تاکید شده بود که نمیتوان مطمئن بود که ساختمان داده بکار رفته شده در کلاس map از نوع tree باشد.
1. آیا گزاره فوق صحیح است؟ یا اینکه میتوان مطمئن بود که map یک درخت است؟
2. اگر map یک درخت نیست، گزینه مناسب کدام است؟ (یا شاید بهتر است که کلاس درخت خودم را داشته باشم؟)
3. در صورتیکه حجم اطلاعات یک map مشخص باشد، آیا اس تی ال allocatore مناسب را دارد؟

[sh_roohani]

سلام،

راستش تا اونجایی که من اطلاع دارم (و اگه اشتباه نکنم) تعریف مشخصات STL دست پیاده ساز رو برای پیاده سازی بیشتر ساختمانهای داده ای باز می گذاره و تنها روی interface تاکید می کنه. بنابراین مثلا شما می تونید یه صف رو بر پایه فهرست پیوندی پیاده سازی کنید یا بر پایه یک آرایه ساده. حالا شاید در این مورد هم همینطور باشه. اگه من بودم کلاس درخت خودم رو پیاده سازی می کردم.

[Sepidar]

سلام،

راستش تا اونجایی که من اطلاع دارم (و اگه اشتباه نکنم) تعریف مشخصات STL دست پیاده ساز رو برای پیاده سازی بیشتر ساختمانهای داده ای باز می گذاره و تنها روی interface تاکید می کنه. بنابراین مثلا شما می تونید یه صف رو بر پایه فهرست پیوندی پیاده سازی کنید یا بر پایه یک آرایه ساده. حالا شاید در این مورد هم همینطور باشه. اگه من بودم کلاس درخت خودم رو پیاده سازی می کردم.
بنا بر پاسخ شما نتیجه میگیریم که (و نتیجه گیری غلطی هم نیست که) دانش من در مورد stl هنوز اندک است.
اگر در مورد مطالبی که گفتید منبعی دارید لطفا معرفی کنید.

اگرچه براساس تجربه هنوز حدس میزنم که علاوه بر معرفی یک interface پیاده سازی های مختلف stl احتمالا از یک خط مشی مشترک پیروی می کنند.

[sh_roohani]

راستش منابع من در مورد STL خیلی پراکنده س. چند تا e-book که روی کامپیوتر شخصی خودم دارم (و متاسفانه چند روزیه که BIOS ام رو به باد فنا دادم و بنابراین در دسترسم نیست!). اما در مورد خط مشی مشترک پیاده سازی شاید حق با شما باشه، درست مثل پیاده سازی کامپایلرهای ++C/C. در بعضی جاها که spec زبان ++C، در مورد روش پیاده سازی قابلیت خاصی سکوت کرده، کامپایلر ها باز هم اون قابلیت رو تقریبا مشابه هم پیاده سازی می کنن. به هر صورت اگه دیر نمی شه یه چند روزی صبر کنین تا من بتونم BIOS ام رو برگردونم. متاسفانه هاردم رو نمی تونم بیارم محل کارم.

[someCoder]

سلام؛

اگه من بودم کلاس درخت خودم رو پیاده سازی می کردم.به نظر من اختراع دوباره چرخ اشتباهه!

یه نگاهی به این بنداز، فکر میکنم خیلی کمک کنه:

While the C++ standard does not specifically require that the map container be implemented using any specific data structure, the time complexity requirements imposed by the standard for each map operation suggest a balanced binary search tree. Many STL implementations use a red/black tree to implement map.
http://www.mtsu.edu/~csjudy/STL/Map.html

[Sepidar]

با توجه به اینکه از ابتدا میدانم چه حجم اطلاعاتی ذخیره میکنم در باره allocator چه پیشنهادی دارید؟
اساسا به طور خاص در مورد ساختارهای مبتنی بر درخت استفاده از allocator ها مختلف موثر خواهد بود؟

[Sepidar]

این هم در مورد allocator ها
http://www.codeproject.com/cpp/allocator.asp