עזרה בבחירת מבנה נתונים ליישום פשוט בשפת c++

[FARKASH7]

מבנה הנתונים צריך לתמוך בהכנסה והוצאה בזמן לוגריתמי. כאשר האיברים בו ממיונים לפי מפתח.

כמו כן הוא צריך לאפשר לי לחפש איבר בזמן לוגריתמי ולבדוק כמה איברים עם מפתח גדול ממנו יש בזמן קבוע.

חשבתי להשתמש במבנה map של c++.

הבעיה שחיפוש בmap מחזיר לי מצביע לאיבר ולא אינדקס שלו במבנה. כך שאני לא יכול להשוות אותו לגודל הmap וכך לדעת כמה איברים בmap גדולים ממנו.

האם יש למישהו פתרון אלגנטי לבעיה? כי כל פתרון שאני חושב עליו מצריך תוספת של ווקטור למשל עם מצביעים כדי לקבל אינדקס.

*רק העיר שהוספת שדה אינדקס בכל איבר בmap שבו מצוין האינדקס של האיבר או כמה איברים גדולים ממנו היא בעייתית כי היא דורשת תחזוקה וכך נפגע זמן ההכנסה והוצאה.

[doker]

אולי משהו בסגנון AVL?

הכנסה והוצאה לוגרתמי.

חיפוש גם.

אתה יכול לשמור בכל איבר את מספר האיברים הגדולים ממנו. ולכן יצא O(1)

זה לא משפיע על הסיבוכיות כי בהוספה והכנסה אתה גם ככה עובר על אותו הקודקוד ואתה יודע אם אתה צריך להוסיף או להחסיר.

לא ידוע איך map פועל בc++

אבל אני חושב שזה עושה שימוש בhashtables כלומר אין סדר ולכן לא תוכל להשוות בין הגודל לבין המיקום שלו.

[FARKASH7]

חשבתי על AVL, פשוט map היה נראה לי בהתחלה אידאלי עד שנתקלתי בבעיה שפירטתי.

חשבתי שאולי פספסתי משהו וניתן לפתור את זה בצורה פשוטה ואלגנטית. כנראה שהתבדתי.

טוב כנראה שאעבור לAVL. יש לך המלצה לחבילה בנויה בc++?

[Gil28]

לפעמים פיתרון נחמד יכול להיות תחזוק של שני מבני נתונים במקביל - לפעמים כאלה שמכילים את אותם איברים ולפעמים אחד מהם מחזיק מצביעים לאיברים במבנה הנתונים השני.

[FARKASH7]

כן גיל אתה צודק. בהודעה הראשונה שלי כתבתי שחשבתי להוסיף אולי ויקטור עם מצביעים. במחשבה שניה הבנתי שרשימה פשוטה דו כיוונית יהיה רעיון טוב יותר.

בפתרון פשוט ונחמד התכוונתי לשיטה או שימוש בשיטות של maps, כזה שפיספסתי, אבל ממה שאתם כותבים אני מבין שאין.

[Gil28]

הדרישות שלך פשוט זועקות עץ AVL

[FARKASH7]

כן אני יודע.גם כתבתי שאעבור למבנה מבוסס עץ מאוזן.