Unieke en bestelde containers in C++

6, 10, 2, 8, 4 is een verzameling; 2, 4, 6, 8, 10 is een verzameling van dezelfde gehele getallen, gerangschikt in oplopende volgorde. In de wiskunde heeft een verzameling unieke elementen (verschillende elementen), en dat wil zeggen dat geen enkel element meer dan één keer voorkomt. Verder is een multiset een verzameling, waarbij elk element meer dan één keer kan voorkomen. 6, 6, 10, 2, 2, 8, 4, 4, 4 is een multiset. 2, 2, 4, 4, 4, 6, 6, 8, 10 is dezelfde multiset, maar met de elementen in oplopende volgorde. Dit artikel gaat niet over multiset. Het behandelt de C++ datastructuur genaamd set.

Een kaart in software is als een array, maar het is een array met twee kolommen in plaats van één. De eerste kolom heeft de sleutels en de tweede kolom heeft de waarden. Elke rij is één paar, waardoor een sleutel/waarde-paar ontstaat. Een sleutel is direct gerelateerd aan zijn waarde.

Een voorbeeld van een kaart is 'c',30, 'b',20, 'd',30, 'e',40, 'a',10. Het eerste sleutel/waarde-paar dat hier wordt ingevoegd, is 'c',3, waarbij 'c' de sleutel is en 30 de waarde. Deze kaart is niet geordend op sleutels. Het bestellen van deze kaart met toetsen levert 'a',10, 'b',20, 'c',30, 'd',30, 'e',40. Merk op dat er dubbele waarden kunnen zijn, maar geen dubbele sleutels. Een geordende kaart is een kaart geordend op toetsen.

Een multiset is voor een set, zoals een multimap is voor een kaart. Dit betekent dat er kaarten zijn met dubbele sleutels. Een voorbeeld van een multimap is 'a',10, 'b',20, 'b',20, 'c',30, 'c',30, 'd ',30, 'e',40. En zoals hierboven vermeld, gaat dit artikel niet over multimap, maar over de C++-gegevensstructuur genaamd map.

In C++ is een gegevensstructuur een structuur met eigenschappen (gegevensleden) en methoden (lidfuncties). De gegevens van de structuur zijn een lijst; een set is een lijst; een kaart is een lijst van sleutel/waarde-paren.

Dit artikel bespreekt de basisprincipes van sets en kaarten in C++, en om dit artikel beter te begrijpen, zou de lezer een basiskennis van C moeten hebben gehad++.

Artikel Inhoud:

Klasse en zijn objecten
Een set of een kaart maken
Basisprincipes van iterator
Elementtoegang voor set en kaart
Volgorde van elementen in een set of kaart
Andere veelgebruikte lidfuncties
Conclusie

Klasse en zijn objecten:

In C++ worden de set, de kaart en andere soortgelijke structuren containers genoemd. Een klasse is een gegeneraliseerde eenheid met gegevensleden, die variabelen zijn, en lidfuncties die gerelateerd zijn. Wanneer gegevensleden waarden krijgen, wordt een object gevormd. Een object wordt echter gevormd in een proces dat instantiatie wordt genoemd. Omdat een klasse kan leiden tot verschillende waarden voor dezelfde gegevenslidvariabelen, kunnen vervolgens verschillende objecten worden geïnstantieerd uit dezelfde klasse.

In C++ is een onbruikbare set een klasse, evenals een onbruikbare kaart. Wanneer een object wordt geïnstantieerd vanuit de onbruikbare set of de onbruikbare kaart, wordt het object de echte gegevensstructuur. Met de set- en kaartgegevensstructuren is het belangrijkste gegevenslid een lijst. Welnu, de set en de kaart vormen een groep containers genaamd, bestelde associatieve containers. Ongeordende set en de ongeordende kaart bestaan ook, maar die komen helaas niet aan bod in dit artikel.

Een set of een kaart maken:

Het instantiëren van een set uit de set-klasse is het creëren van een set; het instantiëren van een kaart vanuit de kaartklasse is het maken van een kaart. Het zo gemaakte object krijgt een naam naar keuze van de programmeur.

Om een set te maken, moet het programma beginnen met:

#include
#include
namespace std; gebruiken;

Let op de richtlijn “#include ”, die de set-bibliotheek bevat die de set-klasse heeft waaruit set-gegevensstructuren zullen worden geïnstantieerd.

Om een kaart te maken, moet het programma beginnen met:

#include
#include
namespace std; gebruiken;

Let op de richtlijn “#include ”, die de kaartbibliotheek bevat met de kaartklasse waaruit kaartgegevensstructuren zullen worden geïnstantieerd.

De syntaxis om een lege set te maken is:

set objectnaam

Voorbeeld:

set setObj;

Een voorbeeld om een set met inhoud te maken is:

set setObj(6, 10, 2, 8, 4);

De syntaxis om een lege kaart te maken is:

kaart objectnaam

Voorbeeld:

kaart kaartObj;

Een voorbeeld om een kaart met inhoud te maken is:

kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Iterator-basis:

Een iterator is een uitgewerkte aanwijzer, die kan worden gebruikt om de lijst van de datastructuur van het begin tot het einde te doorlopen.

Het begin() lid Functie

De lidfunctie begin() retourneert een iterator die verwijst naar het eerste element van de lijst. Het volgende voorbeeld illustreert dit voor de set:

set setObj(6, 10, 2, 8, 4);
set::iterator iter = setObj.beginnen();
cout << *iter << '\n';

Let op de manier waarop begin() is gebruikt met setObj en de puntoperator. iter is het geretourneerde iteratorobject. Let ook op de manier waarop het is gedeclareerd. * is de indirecte operator. Zoals gebruikt met iter, retourneert het het eerste element van de set; het eerste element is 2 in plaats van 6 - zie uitleg hieronder.

Het volgende voorbeeld illustreert het gebruik van de functie begin() voor de kaart:

kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
kaart::iterator iter = mapObj.beginnen();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Let op de manier waarop begin() is gebruikt met mapObj en de puntoperator. iter is het geretourneerde iteratorobject. Let ook op de manier waarop het is gedeclareerd. "eerste", zoals hier gebruikt, verwijst naar de sleutel. "seconde" verwijst naar de waarde die overeenkomt met de sleutel. Observeer hoe ze zijn gebruikt met iter om de startelementcomponenten van de lijst te verkrijgen. Het eerste element is a,10 in plaats van c,30 - zie uitleg hieronder.

De "begin() const" lid Functie

De lidfunctie "begin() const" retourneert een iterator die verwijst naar het eerste element van de lijst wanneer de verklaring van de set begint met const (voor constante). Onder deze voorwaarde kan de waarde in de lijst, waarnaar wordt verwezen door de geretourneerde iterator, niet worden gewijzigd door de iterator. Het volgende voorbeeld illustreert het gebruik ervan voor de set:

const set setObj(6, 10, 2, 8, 4);
set::const_iterator iter = setObj.beginnen();
cout << *iter << '\n';

Let op de manier waarop begin() is gebruikt met setObj en de puntoperator. Er is geen "const" getypt net na begin(). Echter, "const" is voorafgegaan aan de verklaring. iter hier is het geretourneerde constante iterator-object, dat verschilt van de normale iterator. Let ook op de manier waarop het is gedeclareerd. * is de indirecte operator; zoals gebruikt met iter, retourneert het het eerste element van de set. Het eerste element is 2 in plaats van 6 - zie uitleg hieronder.

Het volgende voorbeeld illustreert het gebruik van de functie "begin() const" voor de kaart:

const-kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
kaart::const_iterator iter = mapObj.beginnen();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Let op de manier waarop begin() is gebruikt met mapObj en de puntoperator. Er is geen "const" getypt net na begin(). Echter, "const" is voorafgegaan aan de verklaring. iter hier is het geretourneerde constante iterator-object, dat verschilt van de normale iterator. Let ook op de manier waarop het is gedeclareerd. "eerste", zoals hier gebruikt, verwijst naar de sleutel; "tweede", zoals hier gebruikt, verwijst naar de waarde die overeenkomt met de sleutel. Observeer hoe ze zijn gebruikt met iter om de startelementcomponenten van de lijst te verkrijgen. Het eerste element is a,10 in plaats van c,30 - zie uitleg hieronder.

Het end() lid Functie

De lidfunctie end() retourneert een iterator die net na het einde van de lijst wijst. Het volgende voorbeeld illustreert dit voor de set:

set setObj(6, 10, 2, 8, 4);
set::iterator iter = setObj.einde();
cout << *iter << '\n';

Let op de manier waarop end() is gebruikt met setObj en de puntoperator. iter is het geretourneerde iteratorobject. Let ook op de manier waarop het is gedeclareerd. * is de indirecte operator; zoals gebruikt met iter, retourneert het het laatste+1 element van de set. In de computer van de auteur is dit laatste+1 element 5, wat niet op de lijst staat. Zorg er dus voor dat u dit element niet gebruikt.

Het volgende voorbeeld illustreert het gebruik van de functie end() voor de kaart:

kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
kaart::iterator iter = mapObj.einde();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Let op de manier waarop end() is gebruikt met mapObj en de puntoperator. iter is het geretourneerde iteratorobject. Let ook op de manier waarop het is gedeclareerd. * is de indirecte operator; zoals gebruikt met iter, retourneert het het laatste+1 element van de kaart. Op de computer van de auteur is dit laatste+1 element ,0, dat niet in de lijst staat. Zorg er dus voor dat u dit element niet gebruikt.

De "end() const" lid Functie

De lidfunctie "end() const" retourneert een iterator die net na het einde van de lijst wijst wanneer de verklaring van de set begint met const (voor constante). Onder deze voorwaarde kan de waarde in de lijst, waarnaar wordt verwezen door de geretourneerde iterator, niet worden gewijzigd door de iterator. Het volgende voorbeeld illustreert het gebruik ervan voor de set:

const set setObj(6, 10, 2, 8, 4);
set::const_iterator iter = setObj.einde();
cout << *iter << '\n';

Let op de manier waarop end() is gebruikt met setObj en de puntoperator. Er is geen "const" getypt net na het einde(). Echter, "const" is voorafgegaan aan de verklaring. iter is het geretourneerde iteratorobject. Let ook op de manier waarop het is gedeclareerd. * is de indirecte operator; zoals gebruikt met iter, retourneert het het laatste+1 element van de set.

Het volgende voorbeeld illustreert het gebruik van de functie "end() const" voor de kaart:

const-kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
kaart::const_iterator iter = mapObj.einde();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Let op de manier waarop end() is gebruikt met mapObj en de puntoperator. Er is geen "const" getypt net na het einde(). Echter, "const" is voorafgegaan aan de verklaring. iter is het geretourneerde constante iteratorobject, dat verschilt van de normale iterator. Let ook goed op de manier waarop het is gedeclareerd.

Elementtoegang voor set en kaart:

Instellen

Met de set wordt het element gelezen met behulp van de indirecte-operator. De eerste twee elementen van een set worden in het volgende voorbeeld gelezen:

set setObj(6, 10, 2, 8, 4);
set::iterator iter = setObj.beginnen();
cout << *iter << '\n';
++iter;
cout << *iter << '\n';

De output is 2, gevolgd door 4 - zie uitleg hieronder. Om naar het volgende element van de lijst te wijzen, wordt de iterator verhoogd.

Opmerking: een element kan niet worden gewijzigd met de indirecte-operator voor de set the. Bijvoorbeeld: "*iter = 9;" is niet mogelijk.

kaart

Een kaart bestaat uit sleutel/waarde-paren. Een waarde kan worden gelezen met behulp van de bijbehorende sleutel en worden gewijzigd met dezelfde sleutel. Het volgende codesegment illustreert dit:

kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj['b'] << '\n';
mapObj['b'] = 55;
cout << mapObj['b'] << '\n';

De uitvoer is:

20
55

De puntoperator is hier niet gebruikt. In plaats daarvan is de operator voor vierkante haken, die de sleutel als inhoud aanneemt, gebruikt.

Volgorde van elementen in een set of kaart:

Elementen kunnen in elke volgorde in een set worden ingevoegd. Eenmaal ingevoegd, herschikt de set zijn elementen echter in oplopende volgorde. Oplopende volgorde is de standaardvolgorde. Als aflopende volgorde nodig is, moet de set worden gedeclareerd zoals in het volgende voorbeeld:

set > setObj(6, 10, 2, 8, 4);

Dus, na het type, e.g., int, voor de sjabloon is er een komma, gevolgd door "groter"” tussen de punthaken.

Elementen kunnen in elke volgorde in een kaart worden ingevoegd. Eenmaal ingevoegd, herschikt de kaart zijn elementen echter in oplopende volgorde per sleutel (alleen) terwijl de relatie tussen elke sleutel en zijn waarde behouden blijft. Oplopende volgorde is de standaardvolgorde; als aflopende volgorde nodig is, dan moet de kaart worden gedeclareerd zoals in het volgende voorbeeld:

kaart > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Dus, na het typepaar, e.g., "char, int", voor de sjabloon, is er een komma, gevolgd door "groter” tussen de punthaken.

Een verzameling doorlopen

De while-loop of for-loop met de iterator kan worden gebruikt om een set te doorkruisen. In het volgende voorbeeld wordt een for-lus gebruikt om een set te doorlopen die in aflopende volgorde is geconfigureerd:

set > setObj(6, 10, 2, 8, 4);
voor (set::iterator iter = setObj.beginnen(); iter != setObj.einde(); ++iter)

cout << *iter << ";

De uitvoer is:

10 8 6 4 2

Het verhogen van een iterator wijst het naar het volgende element.

Een kaart doorkruisen

De while-loop of for-loop met de iterator kan worden gebruikt om een kaart te doorkruisen. In het volgende voorbeeld wordt een for-lus gebruikt om een kaart te doorlopen die in aflopende volgorde is geconfigureerd:

kaart > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
voor (kaart::iterator iter = mapObj.beginnen(); iter != kaartObj.einde(); ++iter)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

De uitvoer is:

e, 40, d, 30, c, 30, b, 20, a, 10,

Het verhogen van een iterator wijst het naar het volgende element. "eerste", in de code, verwijst naar de sleutel en "tweede" verwijst naar de overeenkomstige waarde. Merk op hoe deze waarden zijn verkregen voor de uitvoer.

Andere veelgebruikte lidfuncties:

De maat () Functie:

Deze functie retourneert een geheel getal, wat het aantal elementen in de lijst is. Voorbeeld instellen:

set > setObj(6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

De uitvoer is 5.

Voorbeeld kaart:

kaart > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj.size() << '\n';

De uitvoer is 5.

De insert()-functie

set

set staat geen duplicaat toe. Dus elk ingevoegd duplicaat wordt stilzwijgend afgewezen. Met de set is het argument van de functie insert() de waarde die moet worden ingevoegd. De waarde wordt ingepast in een positie, waarbij de volgorde in de set oplopend of aflopend blijft. Voorbeeld:

set setObj(6, 10, 2, 8, 4);
setObj.invoegen (6);
setObj.invoegen (9);
setObj.invoegen (12);
voor (set::iterator iter = setObj.beginnen(); iter != setObj.einde(); ++iter)

cout << *iter << ";

De uitvoer is:

2 4 6 8 9 10 12

Opmerking: de functie insert() member kan worden gebruikt om een lege set te vullen.

kaart

kaart staat geen duplicaat per sleutel toe. Dus elk ingevoegd duplicaat wordt stilzwijgend afgewezen. Met de kaart is het argument voor de functie insert() het sleutel/waarde-paar tussen accolades. Het element wordt per toets in een positie gepast, waarbij de volgorde in de kaart oplopend of aflopend blijft. Voorbeeld:

kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
kaartObj.invoegen('e',80);
kaartObj.invoegen('f',50);
kaartObj.invoegen('g',60);
voor (kaart::iterator iter = mapObj.beginnen(); iter != kaartObj.einde(); ++iter)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

De uitvoer is:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

Opmerking: de functie insert() member kan worden gebruikt om een lege kaart te vullen.

De lege() functie

Deze functie retourneert waar als de lijst leeg is, en onwaar als anders. Voorbeeld instellen:

set setObj(6, 10, 2, 8, 4);
bool ret = setObj.leeg();
cout << ret << '\n';

De uitvoer is 0 voor false, wat betekent dat de set hier niet leeg is.

Voorbeeld kaart:

kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
bool ret = mapObj.leeg();
cout << ret << '\n';

De uitvoer is 0 voor false, wat betekent dat de kaart hier niet leeg is.

De erase() functie

set

Overweeg het volgende codesegment:

set setObj(10, 20, 30, 40, 50);
set::iterator iter = setObj.beginnen();
set::iterator itr = setObj.wissen(iter);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
itr = setObj.wissen (itr);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';

De uitvoer is:

nieuwe maat: 4
volgende waarde: 20
nieuwe maat: 3
volgende waarde: 30

De functie erase() neemt een iterator die naar een element verwijst als argument. Na het wissen van het element, retourneert de functie erase() een iterator die naar het volgende element verwijst.

kaart

Overweeg het volgende codesegment:

kaart mapObj('a',10,'b',20,'c',30,'d',40,'e',50);
kaart::iterator iter = mapObj.beginnen();
kaart::iterator itr = mapObj.wissen(iter);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
itr = mapObj.wissen (itr);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

De uitvoer is:

nieuwe maat: 4
volgende waardepaar: b,20
nieuwe maat: 3
volgende waardepaar: c,30

De functie erase() neemt een iterator die naar een element verwijst als argument. Na het wissen van het element, retourneert de functie erase() een iterator die naar het volgende element verwijst.

De clear()-functie

De functie clear() verwijdert alle elementen in de lijst. Voorbeeld instellen:

set setObj(6, 10, 2, 8, 4);
setObj.Doorzichtig();
cout << setObj.size() << '\n';

De uitgang is 0.

kaart voorbeeld:

kaart mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
kaartObj.Doorzichtig();
cout << mapObj.size() << '\n';

De uitgang is 0.

Conclusie:

Een vaste datastructuur in C++ is een structuur waarin de lijst met elementen standaard in oplopende volgorde wordt opgeslagen, of in aflopende volgorde naar keuze van de programmeur. Alle elementen van de set zijn uniek. Een kaartgegevensstructuur in C++ is een structuur waarin de lijst een hash is van sleutel/waarde-paren, standaard opgeslagen in oplopende volgorde van sleutels, of in aflopende volgorde van sleutels naar keuze van de programmeur. De sleutels zijn ook uniek en er kunnen dubbele waarden zijn. Het belangrijkste gegevenslid van een van de structuren is de lijst. Elke structuur heeft lidfuncties, waarvan sommige vaak worden gebruikt.