Asociativní kontejnery - Associative containers - Wikipedia

Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Ne důvod vyčištění bylo upřesněno. Prosím pomozte vylepšit tento článek jestli můžeš. (Prosinec 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Ve výpočetní technice, asociativní kontejnery odkazovat na skupinu šablon tříd v standardní knihovna z Programovací jazyk C ++ objednané nářadí asociativní pole.^[1] Bytost šablony, lze je použít k ukládání libovolných prvků, jako jsou celá čísla nebo vlastní třídy. V aktuální revizi standardu C ++ jsou definovány následující kontejnery: soubor, mapa, multiset, multimapa. Každý z těchto kontejnerů se liší pouze na omezeních umístěných na jejich prvcích.

Asociativní kontejnery jsou podobné neuspořádané asociativní kontejnery v C ++ standardní knihovna, jediný rozdíl je v tom, že neuspořádané asociativní kontejnery, jak naznačuje jejich název, ne objednat jejich prvky.

Design

Vlastnosti

• Klíčová jedinečnost: v mapa a soubor každý klíč musí být jedinečný. multimapa a multiset toto omezení nemáte.
• Složení prvku: v mapa a multimapa každý prvek se skládá z klíče a namapované hodnoty. v soubor a multiset každý prvek je klíčový; neexistují žádné mapované hodnoty.
• Objednávání prvků: prvky následují a přísné slabé objednávání^[1]

Asociativní kontejnery jsou navrženy tak, aby byly zvláště účinné při přístupu k jeho prvkům pomocí jejich klíče, na rozdíl od sekvenčních kontejnerů, které jsou efektivnější při přístupu k prvkům podle jejich polohy.^[1] Je zaručeno, že asociativní kontejnery budou provádět operace vkládání, mazání a testování, zda je prvek v něm, v logaritmickém čase - O (log n). Jako takové se obvykle implementují pomocí samovyvažující binární vyhledávací stromy a podporuje obousměrnou iteraci. Iterátory a Reference nejsou znehodnoceny operacemi vkládání a mazání, s výjimkou iterátorů a odkazů na vymazané prvky. Definující charakteristikou asociativních kontejnerů je, že prvky jsou vkládány v předdefinovaném pořadí, například seřazené vzestupně.

Asociativní kontejnery lze seskupit do dvou podmnožin: mapy a sady. Mapa, někdy označovaná jako slovník, se skládá z páru klíč / hodnota. Klíč se používá k objednání sekvence a hodnota je nějakým způsobem spojena s tímto klíčem. Například mapa může obsahovat klíče představující každé jedinečné slovo v textu a hodnoty představující počet zobrazení slova v textu. Sada je jednoduše vzestupný kontejner jedinečných prvků.

Mapa i sada umožňují do kontejneru vložit pouze jednu instanci klíče nebo prvku. Pokud je požadováno více instancí prvků, použijte multimap nebo multiset.

Mapy i sady podporují obousměrné iterátory. Další informace o iterátorech najdete v tématu Iterátory.

I když nejsou oficiálně součástí standardu STL, hash_map a hash_set se běžně používají ke zkrácení doby hledání. Tyto kontejnery ukládají své prvky jako hashovací tabulku, přičemž každá položka tabulky obsahuje obousměrně propojený seznam prvků. Chcete-li zajistit nejrychlejší časy vyhledávání, ujistěte se, že hashovací algoritmus pro vaše prvky vrací rovnoměrně distribuované hodnoty hash.

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Prosinec 2011)

Výkon

The asymptotická složitost z operací, které lze použít na asociativní kontejnery, jsou následující:

Přehled funkcí

Kontejnery jsou definovány v záhlavích pojmenovaných za názvy kontejnerů, např. soubor je definován v záhlaví <set>. Všechny kontejnery splňují požadavky Kontejner pojem, což znamená, že mají začít(), konec(), velikost(), max_size (), prázdný(), a vyměnit () metody.

Používání

Následující kód ukazuje, jak používat map <řetězec, int> počítat výskyty slov. Používá slovo jako klíč a počet jako hodnotu.

#zahrnout <iostream>#zahrnout <string>#zahrnout <map>int hlavní(){    std::mapa<std::tětiva, int> slovníky;    std::tětiva s;    zatímco (std::cin >> s && s != "konec")        ++slovníky[s];    zatímco (std::cin >> s && s != "konec")        std::cout << s << ' ' << slovníky[s] << ' n';}

Po spuštění uživatel nejprve zadá řadu slov oddělených mezerami a slovo „konec“, které označuje konec vstupu; pak může uživatel zadávat slova k dotazu, kolikrát se každé slovo vyskytlo v předchozí sérii.

Výše uvedený příklad také ukazuje, že operátor [] vloží nové objekty (pomocí výchozího konstruktoru) do mapy, pokud k klíči není přidružen žádný. Integrální typy jsou tedy inicializovány nulou, řetězce jsou inicializovány na prázdné řetězce atd.

Následující příklad ilustruje vkládání prvků do mapy pomocí funkce vložení a hledání klíče pomocí iterátoru mapy a funkce hledání:

#zahrnout <iostream>#zahrnout <map>#zahrnout <utility> // make_pairint hlavní(){    typedef std::mapa<char, int> MapType;    MapType moje_mapa;    // vkládání prvků pomocí funkce vkládání    moje_mapa.vložit(std::pár<char, int>('A', 1));    moje_mapa.vložit(std::pár<char, int>('b', 2));    moje_mapa.vložit(std::pár<char, int>('C', 3));    moje_mapa.vložit(MapType::typ hodnoty('d', 4)); // všechny standardní kontejnery poskytují tento typedef    moje_mapa.vložit(std::make_pair('E', 5));      // může také použít užitnou funkci make_pair    moje_mapa.vložit({'F', 6});                    // pomocí seznamu inicializátorů C ++ 11        // klíče mapy jsou tříděny automaticky od nižší po vyšší.     // Takže my_map.begin () ukazuje na nejnižší hodnotu klíče, nikoli na klíč, který byl vložen jako první.    MapType::iterátor iter = moje_mapa.začít();    // smaže první prvek pomocí funkce mazání    moje_mapa.vymazat(iter);    // vypíše velikost mapy    std::cout << "Velikost mé_mapy:" << moje_mapa.velikost() << ' n';    std::cout << „Zadejte klíč, který chcete vyhledat:“;    char C;    std::cin >> C;    // find vrátí iterátor odpovídajícímu prvku, pokud je nalezen    // nebo na konec mapy, pokud klíč nebyl nalezen    iter = moje_mapa.nalézt(C);    -li (iter != moje_mapa.konec() )         std::cout << „Hodnota je:“ << iter->druhý << ' n';    jiný        std::cout << „Klíč není v mé_mapě“ << ' n';    // vymazat položky na mapě    moje_mapa.Průhledná();}

Ve výše uvedeném příkladu je pomocí funkce vložení zadáno šest prvků a poté je odstraněn první prvek. Poté se vygeneruje velikost mapy. Dále je uživatel vyzván k vyhledání klíče. Pomocí iterátoru funkce find vyhledá prvek s daným klíčem. Pokud najde klíč, program vytiskne hodnotu prvku. Pokud ji nenajde, je vrácen iterátor na konec mapy a na výstupu je, že klíč nebyl nalezen. Nakonec jsou všechny prvky ve stromu vymazány.

Iterátory

Mapy mohou pomocí iterátorů ukazovat na konkrétní prvky v kontejneru. Iterátor má přístup k klíči i mapované hodnotě prvku:^[1]

mapa<Klíč,T>::iterátor to; // deklaruje iterátor mapyto->za prvé;               // hodnota klíče to->druhý;              // namapovaná hodnota(*to);                   // „hodnota prvku“, která je typu: pair 

Níže je uveden příklad procházení mapou k zobrazení všech klíčů a hodnot pomocí iterátorů:

#zahrnout <iostream>#zahrnout <string>#zahrnout <map>int hlavní(){    std::mapa <std::tětiva, int> data{     { „Bobs score“, 10 },     { „Martys score“, 15 },     { "Skóre Mehmets", 34 },     { "Rockysovo skóre", 22 },     { "Rockysovo skóre", 23 } / * přepíše 22, protože klíče jsou identické * /    };        // Iterujte nad mapou a vytiskněte všechny páry klíč / hodnota.    pro (konst auto& živel : data)    {        std::cout << „Who (key = first):“ << živel.za prvé;        std::cout << "Skóre (hodnota = sekunda):" << živel.druhý << ' n';    }    vrátit se 0;}

Pro kompilaci výše uvedeného vzorku na kompilátoru GCC musíte použít konkrétní standardní výběrový příznak.

G++ -std=C++11 zdroj.cpp -Ó src

Tím se vygenerují klíče a hodnoty celé mapy seřazené podle klíčů.

Reference

Viz také

• Kontejner (abstraktní datový typ)
• Standardní knihovna šablon # kontejnerů