קבוצת החזקה +MAP ב CPP

[helloworld5]

קבוצת החזקה +MAP ב CPP

שלום רב
2 שאלות ב CPP
1-במידה ואני מקבל STRING שכתובבו {1,2,3} אני רוצה להחזיר רשימה שתכיל את שכל איבר בה יהיה תת קבוצה
{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}
אני לא מצליח לחשוב על אלגוריתם כזה, אשמח לאלגוריתם/פסודו/הסבר טוב במילים

2- אני עושה MAP <string,int> אני רוצה לבדוק כמה פעמים כל STRING הוזכר
הבעיה איך להבדיל בין הפעם הראשונה שאני מקבל את ה STRING הזה ואז אני צריך לאפס את ה VAL שלו ל 1 ובין הפעם השניה שאז לעשות ל VAL שלו ++
myMap[name] =1
ובשאר הפעמים
myMap[name] =++
הדרך הכי יעילה לבדוק האם STRING לא נמצא לי ב MAP זה לעשות

  if (myMap.find(name) == myMap.end())
        cout << "no";

(ראיתי את הקוד הזה ב STACKOVERFLOW )
זה מוזר... כי הרי הפונקציה end אמורה להחזיר לי מצביע לסוף ה MAP שזה לכאורה האיבר האחרון, לא?(ואז אם אחפש את האיבר האחרון הוא יגיד לי שהכתובת שלו שווה ל END ?
הרי ככה עושים שמריצים ITERATOR, עד שהITERATOR שונה מ myMap.end שזה בעצם האיבר האחרון
(אני בכוונה לא רוצה לחפש עם לולאה ידנית של איטרטור)

תודה חברים!

תודה חברים

 

[הפרבולה]

לגבי 1

תעשה מונה של 3 ביט ( שיספור מ 0 עד 7 כולל ) וכל פעם לפי אם הביט המתאים הוא 1 אז תדפיס את האיבר המתאים לו בקבוצה.

 

[helloworld5]

נשמע טוב,תוכל להראות מימוש??

ניסיתי ולא הצלחתי לממש כך
אשמח למימוש אם תוכל להראות...?
(אני מקבל מערך של מילים ואני רוצה להחזיר את קבוצת החזקה שלו)
תודה

 

[BravoMan]

לגבי 2:

לא ככה עובדים איטרטורים ב-++C.
end תמיד מחזיר לך מצביע לאלמנט אחד אחרי הסוף, כלומר, אלמנט שלא קיים.
זו הסיבה שבלולאות תמיד רצים עד שמגיעים אליו, אבל אותו עצמו לא בודקים.

 

[helloworld5]

שאלה כללית על map

באמת הכנסה והוצאה זה בo(1)?
זה עושה כמו טבלת הש?
או שהוא סורק את כל הטבלה?
אני שואל כדי לדעת יעילות מבחינת זמני ריצה
עד כמה(והאם)זה יותר מהיר משימוש בווקטור\רשימה שכדי לגלות האם איבר קיים צריך לרוץ על כל המבנה?
&nbsp
תודה

 

[BravoMan]

זה תלוי איך מימשו את ה-map הספציפי שאתה משתמש בו.

בד"כ, ה-STL של ++C ממש את map בעזרת red black tree.
לדיון למה וכמה קרא כאן:
http://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-a-red-black-tree