cpp как да се сравни с карти


Отговор 1:

Математически, Map е модел, който взема ключ и отговаря със стойност. Наборът е специализиран случай на Карта, където ключът е идентичен със стойността, към която се картографира. Тази концепция се разпростира върху изпълнението на C ++ на тези два обекта.

Кога е std :: map полезно: Помислете за база данни, съхраняваща потребителски акаунти, да предположим, че те са акаунти в netflix. Картата, която представлява тази таблица на потребителите на netflix, може да получи потребителски идентификатор и да върне потребителския обект, свързан с този идентификационен номер. След това можем да използваме идентификатора, за да извлечем потребителския акаунт за O (1) време, като хешираме уникалния потребителски идентификатор към акаунта и за търсене на акаунт всичко, от което се нуждаете, е идентификаторът, за да извлечете всички тези потребителски данни.

Можем ли да направим това със std :: set? Как можем да приложим този предишен пример с набор? Можем да вмъкнем потребителски акаунти в нашия std :: set, но когато искаме да търсим потребителски акаунт, ще изискваме целия потребителски акаунт, за да извършим търсене на нашия потребителски запис. Изчакайте малко, ако вече имаме информация за потребителския акаунт, защо ще трябва да я търсим? Също така, ако имаме само идентификационен номер на потребителя, вече не можем да извлечем акаунта за O (1) време, трябва да повторим цялата таблица, за да намерим акаунта, който съвпада и това ще бъде O (N).

Кога може да искате да използвате std :: map срещу кога може да искате да използвате std :: map за примитиви? Помислете за структура, предназначена да съхранява всички прости числа под някаква произволна стойност N. Ако просто искаме да знаем дали числото е член на множеството прости числа, тогава std :: set има смисъл, може просто да искаме да проверим дали произволно цяло число стойност 'k' съществува в нашия набор и може да не ни безпокои каквото и да е понятие за индекс или ключ. Ако обаче се интересуваме от последователността на прости числа, тогава може да искаме сдвояване ключ-стойност. Може би бихме искали да моделираме последователността p = {2, 3, 5, 7, 11, ...} и бихме искали да знаем дали p [j] = k за някои произволни стойности на j & k. В последния случай тогава може да помислим за std :: map (макар че std :: vector може да е добър избор).

Така накратко:

  1. Зададената структура от данни е специализиран тип структура на данните на картата, където ключ == стойност, а дефинициите на C ++ STL отразяват тази концепция
  2. std :: map от std :: set обикновено е по-полезен, тъй като std :: map осигурява бързо търсене по ключ за обобщени стойности (цели обекти, а не примитиви).
  3. std :: set често е по-полезен за примитиви, тъй като картографирането на примитивна стойност k-> k е доста произволно

Отговор 2:

Много от отговорите не успяват да засегнат промяната в изпълнението на map и set контейнери за C ++ 17, дори когато е уместно, така че ще разгледам това изключително.

Как можете да преместите възел от един контейнер в друг?

Как можете да промените ключа на възел на картата?

Ако сте поставили подвижни, но не копируеми данни в карта или набор, как можете да ги върнете отново?

Всички те са отговорени в C ++ 17 чрез добавяне на нова непрозрачна структура от данни ... манипулатор на възела ... и две нови функции на член за всеки набор или контейнер на карта, които работят с манипулатори на възела ... екстракт, който извлича възел от карта или зададен в манипулатор на възел и ново претоварване на вмъкване, което взема възел от манипулатор на възел и го вмъква в карта или набор. Съществува и нов метод за удобство, merge, който премества всички недублиращи се възли в една карта или задава в друга.

Манипулатор на възел (C ++ 17)

Манипулатор на възел има множество свойства. Той притежава извлечен възел по същия начин, както std :: unique_ptr, и така също е подвижен, но не може да се копира. Ако манипулатор на възел притежава възел, когато е разрушен, възелът се унищожава и освобождава ... което означава, че той също трябва да има копие на разпределителя, използван в неговия контейнер, за да извърши освобождаване. Това означава, че разпределителите, използвани в два контейнера, трябва да се сравняват по равно (operator == връща true), за да бъде преместен възел от един контейнер в другия. Всички разпределители по подразбиране се сравняват равни, така че това обикновено не е проблем.

Докато възел е собственост на възел манипулатор nh, той може да се управлява по начини, които са невъзможни, докато е в рамките на карта или набор. Например, на извлечен възел на карта може да се промени ключът му чрез присвояване на nh.key () и да се премести некопируема картографирана стойност с помощта на std :: move (nh.mapped ()). Извлеченият възел може да има некопируема стойност, изнесена с помощта на std :: move (nh.value ()).


Отговор 3:

В момента C ++ предлага 8 стандартни

асоциативни контейнери

в това пространство:

  • std :: set
  • std :: multiset
  • std :: unordered_set
  • std :: unordered_multiset
  • std :: map
  • std :: multimap
  • std :: unordered_map
  • std :: unordered_multimap

Може да забележите, че тук има 3 оси на вариация:

  • набор срещу карта.
  • подредени срещу неподредени.
  • уникален ключ срещу мулти ключ.

Питахте за набор срещу карта; обаче си струва да знаете как да избирате между всичките 8 комбинации.

набор срещу карта

Комплектът съдържа набор от ключове. Можете да вмъквате и премахвате ключове от комплекта, да проверявате дали ключът присъства в комплекта и да преглеждате набора от всички ключове. След като ключът е вмъкнат в комплекта, той е неизменен. Не можете да промените ключ, след като е вмъкнат. По-скоро трябва да го изтриете и да вмъкнете новия ключ, ако искате да промените съществуващ ключ.

Карта свързва стойност с всеки ключ. Стойностите могат да бъдат различен тип от самия ключ. Обикновено стойностите също са променливи. Мога да търся стойност по нейния ключ и да я променя, след като я намеря.

Искате да използвате set, когато сте загрижени само за комплекта ключове, които имате. Искате да използвате карта, когато се занимавате с проследяване на куп стойности, които имат ключове, свързани с тях.

Да предположим например, че исках да проследя всички хора, присъстващи на събрание. Комплектът може да е подходящ за това. Всеки участник е член на набора и мога да прегледам всички членове на набора, за да генерирам списък с участниците.

Да предположим, че срещата ми се обслужва и искам да проследя предпочитанията за хранене на всички хора, присъстващи на срещата ми. Сега искам карта на присъстващите да предпочитат храненето. Ключът в този случай е присъстващият, а стойността е предпочитанието за хранене. Можете да промените предпочитанията за хранене на всеки участник, без да променяте самия участник. (По-малко неудобно е по този начин ...)

подредени срещу неподредени

Асоциативните контейнери без

неподредени

в офертата за име

O (\ lg n)

време за достъп. Те изискват ключове, които са

Сравним

и

Строг слаб ред.

Те обикновено са изградени от балансирани бинарни дървета за търсене. Ако прегледате всички елементи, ще посетите клавишите в не намаляващ ред. (Или не увеличаващ се ред, ако използвате обратни итератори.)

Асоциативните контейнери с неподредени в името предлагат амортизирано O (1) време за достъп, при условие че можете да изградите O (1) хешираща функция за вашия ключ. В разговорно изражение те са известни като хеш таблици. Нуждаете се от ефективна хешираща функция, за да работят неподредените контейнери ефективно. Ако прегледате всички елементи, ще посетите ключовете в произволен ред.

Кога трябва да използвате подредени срещу неподредени? Това зависи от няколко неща:

  • Трябва ли често да посещавате всички ключове в детерминиран ред? Ако е така, поръчаният контейнер може да бъде разумен избор.
  • По-бързо или по-бавно е сравнението от хеширането? Ако е много по-бързо, поръчаното може да е по-добре. Ако е много по-бавно, неподредените може да са по-бързи.
  • Знаете ли приблизителния общ размер на контейнера предварително? Преоразмеряването на неподреден контейнер може да струва скъпо, докато вмъкването в подреден контейнер обикновено няма диви промени в производителността.
  • Какъв отпечатък на паметта можете да понесете? Неподредените контейнери са склонни да търгуват по размер за скорост.

Ако пишете кода си внимателно, можете да опитате да превключвате между подредени и неподредени контейнери към бенчмарк, който се представя по-добре за вашето конкретно натоварване.

Едно приложение, което написах, завърши с интересна комбинация от поръчани и неподредени контейнери, базирани на точно такъв бенчмаркинг. Бях малко изненадан кои контейнери къде спечелиха и как това се промени, когато промених свойствата на ключовете. По-специално, преминаването от std :: string към низ таблица, индексирана от цели числа, промени цената на хеширащите функции забележимо.

уникален ключ срещу мулти-ключ

Асоциативните контейнери без мулти в името позволяват само един екземпляр на всеки ключ в контейнера. Тоест всеки ключ трябва да е уникален. Това осигурява подобна семантика на едномерния масив, където всеки индекс съдържа един елемент. Вмъкването на ключ, който вече съществува в контейнера, е логична грешка.

Асоциативните контейнери с multi в името позволяват множество екземпляри на всеки ключ. Можете да вмъкнете всеки клавиш колкото пъти искате. Повтарящите се клавиши се поддържат в реда за вмъкване.

Забележка: Това има значение дори за мултимножество, тъй като критериите за сравнение разграничават еквивалент от равен. Два ключа са еквивалентни, ако нито един не сравнява по-малко от другия; функцията за сравнение обаче не се изисква, за да вземе предвид всички полета на ключовия обект.

Коя да изберете? Това наистина зависи от проблема, който се опитвате да разрешите. Анекдотично, рядко съм имал нужда от мултисетове или мултимапи.

Ако трябва да следите всички екземпляри на „ключ“, които виждате, независимо дали някои от тях се сравняват като равни, тогава мултимножество или мултимап е правилният избор. В противен случай вероятно ще искате не-мулти наборите или картите.

Една интересна употреба за std :: multiset или std :: multimap е като опашка с приоритет. Използвайте приоритета като ключ. Елементът, върнат от begin (), е вашият елемент с най-висок приоритет. Списъкът на елементите се поддържа в сортиран ред, така че даден итератор, който сочи към елемент, можете бързо да определите какво е точно преди и непосредствено след него. По-специално, ако приоритетът всъщност е представен от времето - тоест тази опашка с приоритети всъщност е опашка за събития, подредени по време - тогава можете евтино да определите какви събития са планирани в близост до определено време.

Това обаче работи само с поръчаното мултимножество и подредено мултимап.

std :: priority_queue

може да е по-добър избор, ако се нуждаете само от бърз достъп до елемент с най-висок приоритет и не се възползвате от напълно сортирания характер на мултимножество или мултимап. (Вижте

std :: priority_queue

за повече информация.)


Отговор 4:

Ами мога да отговоря на това.

Карти

Картите изискват ключове. За всеки ключ имате определен вид стойност.

Сега ключ може да бъде всичко, цяло число, низ или дори обект (снабден с допълнителна функционалност за сравнение). Така могат да бъдат и стойностите.

Виж това:

карта М; // целочислен ключ - целочислена стойностМ [3] = 2;карта С; // низ ключ - целочислена стойностS ["ahar"] = 26;

Това е очарователно.

Да предположим, че искате да съхранявате рождените дни на приятелите си. Просто декларирате карта и съхранявайте имената и датите им на раждане само като направите просто задание. Това е като речник в Python.

Комплекти

Това не важи за комплектите. Комплектите не се нуждаят от сдвояване (ключ, стойност). Те просто съдържат какъвто и да е вид стойности (разбира се с функции за сравнение или претоварване на оператора, когато е необходимо), които искате да съдържат. Например:

комплект С;S.insert (13);комплект T;S.insert ("ahar");комплект Х;S.insert (yourObject);

От гледна точка на изпълнението те имат прилики. Търсенето, вмъкването, изтриването и т.н. са подредени по

O (влизане)

и в двамата (благодарности отиват на

Червено черно дърво

, нещото, от което се страхувахте в курса си за Структура на данни: P). Но поради разликите в изпълнението и употребата може да има определени режийни разходи.

Допълнителна бележка:

Ако направите наблюдение, ще откриете, че от основната структурна перспектива наборите и картите са различни. Така че въпросът, който зададохте, може да бъде малко по-интересен, ако го мислите по начин, при който можете да използвате набори като алтернатива на картите и обратно.

Това може да ни отведе до интересен въпрос: каква е разликата между множеството > и карта ? Това е доста валиден въпрос, защото в този сценарий можете да мислите за първия елемент от двойката в набора, еквивалентен на ключа в картата!

Например:

карта М;M.insert ({"motta", 13});комплект > S;S.insert ({"motta", 13});

Виждате, че написаният по-горе набор може да бъде потенциална алтернатива на картата.

Е, те еквивалентни ли са? Е, не.

Първо, картата не може да съдържа различни цели числа за същия ключ, както декларирахме по-горе. Но комплект може.

Така,

M.insert ({"ahar", 13)};S.insert ({"ahar", 13});M.insert ({"ahar", 26});S.insert ({"ahar", 26});

прави размера на комплекта равен на 2, но за картата е 1.

Второ, вече трябва да знаете, че тези C ++ контейнери използват итератори, които се използват за насочване на елементи в тези контейнери. За да го мислим просто, итераторите са това, от което се нуждаете за достъп до данните в тези контейнери.

Сега вижте това:

комплект > S;S.insert ({"ahar", 26});автоматично то = S.begin (); // вече е итератор за ("ahar", 26)

По някаква причина възнамерявате да промените стойността на съответната двойка, итерирана от нея, от 26 на 13. Опитайте следното:

то-> второ = 13;

Ъъъ ... не. Не можеш да го направиш.

Причината е донякъде сложна. Най-просто казано, итераторите за C ++ набор са като постоянни итератори. Така че не можете просто да промените съответната стойност на данните на място. Трябва да го изтриете от набор и след това да добавите новата си стойност, по следния начин:

S.erase (то);двойка p = {"ahar", 13};S. вмъкване (p);

: |

В случай на карти, това е напълно валидно:

карта М;M.insert ({"motta", 13});автоматично то = M.begin ();то-> второ = 26;

Надявам се да съм разбрал всичко както трябва. : P

Благодаря за четенето.


Отговор 5:

Картата е структура от данни, използвана за търсене на стойности по ключове, докато наборът е просто колекция от стойности.

По отношение на изпълнението, те обикновено не се прилагат по различен начин и и двете обикновено използват червено-черни дървета под капака, за да получат логаритмична времева сложност за повечето операции. Една разлика, в зависимост от изпълненията, е, че даден набор ще бъде червено-черно дърво на елементи, докато картата ще бъде червено-черно дърво на (ключови, стойностни) туплейни елементи, сортирани според първия елемент (ключа) в кортеж.


Отговор 6:

Карта съпоставя един обект с друг. Наборът е подреден набор от обекти. Карта често се използва за достъп до обекти чрез индекс по такъв начин, че objectMap [i] съдържа обекта с индекс i. Набор може да се използва за съхраняване на обекти, с допълнителното предимство, че даден набор идентифицира дали даден обект вече се съдържа в него и съхранява само един обект от обектите. Можете обаче да осъществите достъп до обекти в даден набор само чрез итерация върху него или получаване на първия или последния елемент от набора.


Отговор 7:

std :: map е асоциативен, подреден масив. Това означава, че съхранява двойки и чрез ключа можете да стигнете до стойността. Също така, можете да прегледате двойки и итерацията ще последва добро подреждане на ключовете.

std :: set е само колекция от стойности. Отново можете да итерирате върху него и отново итерацията ще последва добро подреждане на стойностите. Но няма асоциация като по-горе, можете да задавате само въпроси като „тази стойност в комплекта ли е?“ И за това вече трябва да имате въпросната стойност.