Уникални и подредени контейнери в C ++

6, 10, 2, 8, 4 е набор; 2, 4, 6, 8, 10 е набор от същите цели числа, подредени във възходящ ред. В математиката набор има уникални елементи (отделни елементи) и тоест нито един елемент не се появява повече от веднъж. Освен това мултимножество е набор, където всеки елемент може да се появи повече от веднъж. 6, 6, 10, 2, 2, 8, 4, 4, 4 е мултифункция. 2, 2, 4, 4, 4, 6, 6, 8, 10 е същото мултимножество, но с елементите, подредени във възходящ ред. Тази статия не се занимава с мултимножество. Той се занимава със структурата на данни на C ++, наречена set.

Картата в софтуера е като масив, но е масив с две колони вместо една. Първата колона има ключовете, а втората колона има стойностите. Всеки ред е една двойка, което прави двойка ключ / стойност. Ключът е пряко свързан със стойността му.

Пример за карта е 'c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10. Първата двойка ключ / стойност, вмъкната тук, е 'c', 3, където 'c' е ключът, а 30 е стойността. Тази карта не е подредена по ключове. Подреждането на тази карта по ключове води до 'a', 10, 'b', 20, 'c', 30, 'd', 30, 'e', 40. Забележете, че може да има дублирани стойности, но не и дублирани ключове. Подредената карта е карта, подредена по ключове.

Мултимножество е към набор, както мултикарта е към карта. Това означава, че има карти с дублиращи се ключове. Пример за мултикарта е 'a', 10, 'b', 20, 'b', 20, 'c', 30, 'c', 30, 'd ', 30, ' e ', 40. И както беше посочено по-горе, тази статия не се занимава с мултимап, а по-скоро се занимава със структурата на данни на C ++, наречена map.

В C ++ структурата на данните е структура със свойства (членове на данни) и методи (функции на членове). Данните на структурата са списък; набор е списък; карта е списък на двойки ключ / стойност.

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

Съдържание на статията:

Клас и неговите обекти
Създаване на комплект или карта
Основи на итератора
Достъп до елемент за набор и карта
Ред на елементите в набор или карта
Други често използвани членски функции
Заключение

Клас и неговите обекти:

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

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

Създаване на комплект или карта:

Инсталирането на набор от неговия клас създава набор; инстанцирането на карта от нейния клас на карта създава карта. Така създаденият обект получава име по избор на програмиста.

За да създадете набор, програмата трябва да започне с:

#include
#include
използване на пространство от имена std;

Обърнете внимание на директивата „#include ”, Която включва библиотеката на множество, която има класът на набор, от който ще бъдат създадени екземпляри на структури от данни.

За да създадете карта, програмата трябва да започне с:

#include
#include
използване на пространство от имена std;

Обърнете внимание на директивата „#include ”, Която включва библиотеката на картата, която има класа на картата, от който ще бъдат създадени инстанции на структурите на данните на картата.

Синтаксисът за създаване на празен набор е:

комплект objectName

Пример:

комплект setObj;

Пример за създаване на набор със съдържание е:

комплект setObj (6, 10, 2, 8, 4);

Синтаксисът за създаване на празна карта е:

карта objectName

Пример:

карта mapObj;

Пример за създаване на карта със съдържание е:

карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Основи на итератора:

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

Функцията член () член

Функцията член () член връща итератор, който сочи към първия елемент от списъка. Следващият пример илюстрира това за комплекта:

комплект setObj (6, 10, 2, 8, 4);
комплект:: итератор iter = setObj.начало ();
Cout << *iter << '\n';

Обърнете внимание на начина, по който begin () е използван с setObj и точковия оператор. iter е върнатият обект на итератор. Освен това обърнете внимание на начина, по който е деклариран. * е операторът на непрякост. Както се използва с iter, той връща първия елемент от набора; първият елемент е 2 вместо 6 - вижте обяснението по-долу.

Следващият пример илюстрира използването на функцията begin () за картата:

карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
карта:: итератор iter = mapObj.начало ();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Обърнете внимание на начина, по който begin () е използван с mapObj и точковия оператор. iter е върнатият обект на итератор. Освен това обърнете внимание на начина, по който е деклариран. „First“, както се използва тук, се отнася до ключа. „Втори“ се отнася до стойността, съответстваща на ключа. Наблюдавайте как са били използвани с iter за получаване на началните елементи на елемента от списъка. Първият елемент е a, 10 вместо c, 30 - вижте обяснението по-долу.

Функцията на член “begin () const”

Функцията член “begin () const” връща итератор, който сочи към първия елемент от списъка, когато декларацията на набора започва с const (за константа). При това условие стойността в списъка, посочена от върнатия итератор, не може да бъде променена от итератора. Следващият пример илюстрира използването му за комплекта:

const set setObj (6, 10, 2, 8, 4);
комплект:: const_iterator iter = setObj.начало ();
Cout << *iter << '\n';

Обърнете внимание на начина, по който begin () е използван с setObj и точковия оператор. Не е въведена „const“ веднага след начало (). „Const“ обаче е предшествал декларацията. iter тук е върнатият обект на постоянен итератор, който е различен от нормалния итератор. Освен това обърнете внимание на начина, по който е деклариран. * е непряк оператор; както се използва с iter, той връща първия елемент от набора. Първият елемент е 2 вместо 6 - вижте обяснението по-долу.

Следващият пример илюстрира използването на функцията “begin () const” за картата:

const карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
карта:: const_iterator iter = mapObj.начало ();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Обърнете внимание на начина, по който begin () е използван с mapObj и точковия оператор. Не е въведена „const“ веднага след начало (). „Const“ обаче е предшествал декларацията. iter тук е върнатият обект на постоянен итератор, който е различен от нормалния итератор. Освен това обърнете внимание на начина, по който е деклариран. „Първи“, както е използван тук, се отнася до ключа; "Втори", както се използва тук, се отнася до стойността, съответстваща на ключа. Наблюдавайте как са били използвани с iter за получаване на началните елементи на елемента от списъка. Първият елемент е a, 10 вместо c, 30 - вижте обяснението по-долу.

Функция на крайния () член

Функцията член end () връща итератор, който сочи непосредствено след края на списъка. Следващият пример илюстрира това за комплекта:

комплект setObj (6, 10, 2, 8, 4);
комплект:: итератор iter = setObj.край();
Cout << *iter << '\n';

Обърнете внимание на начина, по който end () е използван с setObj и точният оператор. iter е върнатият обект на итератор. Освен това обърнете внимание на начина, по който е деклариран. * е непряк оператор; както се използва с iter, той връща последния + 1 елемент от набора. В компютъра на автора този последен + 1 елемент е 5, който не е в списъка. Така че, внимавайте да не използвате този елемент.

Следващият пример илюстрира използването на функцията end () за картата:

карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
карта:: итератор iter = mapObj.край();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Обърнете внимание на начина, по който end () е използван с mapObj и точковия оператор. iter е върнатият обект на итератор. Освен това обърнете внимание на начина, по който е деклариран. * е непряк оператор; както се използва с iter, той връща последния + 1 елемент на картата. В компютъра на автора този последен + 1 елемент е , 0, който не е в списъка. Така че, внимавайте да не използвате този елемент.

Функцията член „end () const“

Функцията член „end () const“ връща итератор, който сочи точно след края на списъка, когато декларацията на набора започва с const (за константа). При това условие стойността в списъка, посочена от върнатия итератор, не може да бъде променена от итератора. Следващият пример илюстрира използването му за комплекта:

const set setObj (6, 10, 2, 8, 4);
комплект:: const_iterator iter = setObj.край();
Cout << *iter << '\n';

Обърнете внимание на начина, по който end () е използван с setObj и точният оператор. Не е въведено „const“ веднага след края (). „Const“ обаче е предшествал декларацията. iter е върнатият обект на итератор. Освен това обърнете внимание на начина, по който е деклариран. * е непряк оператор; както се използва с iter, той връща последния + 1 елемент от набора.

Следващият пример илюстрира използването на функцията “end () const” за картата:

const карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
карта:: const_iterator iter = mapObj.край();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Обърнете внимание на начина, по който end () е използван с mapObj и точковия оператор. Не е въведено „const“ веднага след края (). „Const“ обаче е предшествал декларацията. iter е върнатият обект на постоянен итератор, който е различен от нормалния итератор. Също така внимателно наблюдавайте начина, по който е деклариран.

Достъп до елемент за набор и карта:

Комплект

При набора елементът се чете с помощта на оператора за насочване. Първите два елемента от набор се четат в следния пример:

комплект setObj (6, 10, 2, 8, 4);
комплект:: итератор iter = setObj.начало ();
Cout << *iter << '\n';
++iter;
Cout << *iter << '\n';

Резултатът е 2, след което последван от 4 - вижте обяснението по-долу. За да посочи следващия елемент от списъка, итераторът се увеличава.

Забележка: Елемент не може да бъде променен с помощта на оператора за насочване за комплекта. Например „* iter = 9;“ не е възможно.

карта

Картата се състои от двойки ключ / стойност. Стойността може да се прочете с помощта на съответния ключ и да се промени с помощта на същия ключ. Следният кодов сегмент илюстрира това:

карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
Cout << mapObj['b'] << '\n';
mapObj ['b'] = 55;
Cout << mapObj['b'] << '\n';

Резултатът е:

20
55

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

Ред на елементите в набор или карта:

Елементите могат да бъдат вмъкнати в набор, в произволен ред. Веднъж поставен, обаче, комплектът пренарежда елементите си във възходящ ред. Възходящ ред е редът по подразбиране. Ако е необходим низходящ ред, тогава комплектът трябва да бъде деклариран както в следния пример:

комплект > setObj (6, 10, 2, 8, 4);

И така, след типа, напр.ж., int, за шаблона има запетая, последвана от „по-голяма”В ъгловите скоби.

Елементите могат да се вмъкват в карта във всякакъв ред. След като бъде поставена обаче, картата пренарежда елементите си във възходящ ред по ключ (само), като същевременно поддържа връзката между всеки ключ и неговата стойност. Възходящ ред е поръчката по подразбиране; ако е необходим низходящ ред, тогава картата трябва да бъде декларирана както в следния пример:

карта > mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

И така, след двойката типове, напр.ж., „Char, int“, за шаблона има запетая, последвана от „по-голяма”В ъгловите скоби.

Преминаване на набор

Цикълът while или for-loop с итератора може да се използва за обхождане на набор. Следващият пример използва for-loop за пресичане на набор, който е конфигуриран в низходящ ред:

комплект > setObj (6, 10, 2, 8, 4);
за (комплект:: итератор iter = setObj.начало (); iter != setObj.край(); ++ iter)

Cout << *iter << ";

Резултатът е:

10 8 6 4 2

Увеличаването на итератор го насочва към следващия елемент.

Преминаване по карта

Цикълът while или for-loop с итератора може да се използва за пресичане на карта. Следващият пример използва for-loop за пресичане на карта, която е конфигурирана в низходящ ред:

карта > mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
за (карта:: итератор iter = mapObj.начало (); iter != mapObj.край(); ++ iter)

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

Резултатът е:

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

Увеличаването на итератор го насочва към следващия елемент. „Първи“ в кода се отнася до ключа, а „втори“ се отнася до съответната стойност. Обърнете внимание как са получени тези стойности за изхода.

Други често използвани членски функции:

Функция за размер ()

Тази функция връща цяло число, което е броят на елементите в списъка. Дайте пример:

комплект > setObj (6, 10, 2, 8, 4);
Cout << setObj.size() << '\n';

Изходът е 5.

Пример за карта:

карта > mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
Cout << mapObj.size() << '\n';

Изходът е 5.

Функция за вмъкване ()

комплект

set не позволява дублиране. Така че всеки вмъкнат дубликат се отхвърля мълчаливо. С набора аргументът на функцията insert () е стойността, която трябва да се вмъкне. Стойността се монтира в позиция, при която редът в комплекта остава възходящ или низходящ. Пример:

комплект setObj (6, 10, 2, 8, 4);
setObj.вложка (6);
setObj.вложка (9);
setObj.вложка (12);
за (комплект:: итератор iter = setObj.начало (); iter != setObj.край(); ++ iter)

Cout << *iter << ";

Резултатът е:

2 4 6 8 9 10 12

Забележка: Функцията член () може да се използва за попълване на празен набор.

карта

map не позволява дублиране по ключ. Така че всеки вмъкнат дубликат се отхвърля мълчаливо. При картата аргументът на функцията insert () е двойката ключ / стойност в скоби. Елементът е монтиран в позиция чрез ключ, при който редът в картата остава възходящ или низходящ. Пример:

карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapObj.вмъкване ('e', 80);
mapObj.вмъкване ('f', 50);
mapObj.вмъкване ('g', 60);
за (карта:: итератор iter = mapObj.начало (); iter != mapObj.край(); ++ iter)
Cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

Резултатът е:

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

Забележка: Функцията член () може да се използва за попълване на празна карта.

Функцията празен ()

Тази функция връща true, ако списъкът е празен, и false, ако е друго. Дайте пример:

комплект setObj (6, 10, 2, 8, 4);
bool ret = setObj.празен ();
Cout << ret << '\n';

Изходът е 0 за false, което означава, че наборът тук не е празен.

Пример за карта:

карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
bool ret = mapObj.празен ();
Cout << ret << '\n';

Изходът е 0 за false, което означава, че картата тук не е празна.

Функцията за изтриване ()

комплект

Помислете за следния кодов сегмент:

комплект setObj (10, 20, 30, 40, 50);
комплект:: итератор iter = setObj.начало ();
комплект:: итератор itr = setObj.изтриване (iter);
Cout << "new size: " << setObj.size() << '\n';
Cout << "next value: " << *itr << '\n';
itr = setObj.изтриване (itr);
Cout << "new size: " << setObj.size() << '\n';
Cout << "next value: " << *itr << '\n';

Резултатът е:

нов размер: 4
следваща стойност: 20
нов размер: 3
следваща стойност: 30

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

карта

Помислете за следния кодов сегмент:

карта mapObj ('a', 10, 'b', 20, 'c', 30, 'd', 40, 'e', 50);
карта:: итератор iter = mapObj.начало ();
карта:: итератор itr = mapObj.изтриване (iter);
Cout << "new size: " << mapObj.size() << '\n';
Cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
itr = mapObj.изтриване (itr);
Cout << "new size: " << mapObj.size() << '\n';
Cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

Резултатът е:

нов размер: 4
следваща двойка стойности: b, 20
нов размер: 3
следваща двойка стойности: c, 30

Функцията clear ()

Функцията clear () премахва всички елементи в списъка. Дайте пример:

комплект setObj (6, 10, 2, 8, 4);
setObj.ясно ();
Cout << setObj.size() << '\n';

Изходът е 0.

пример за карта:

карта mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapObj.ясно ();
Cout << mapObj.size() << '\n';

Изходът е 0.

Заключение:

Зададена структура от данни в C ++ е структура, в която списъкът с елементи се съхранява във възходящ ред по подразбиране или в низходящ ред по избор на програмиста. Всички елементи от комплекта са уникални. Структура на данните на картата в C ++ е структура, в която списъкът е хеш от двойки ключ / стойност, съхранявани във възходящ ред на ключове по подразбиране или в низходящ ред на ключове по избор на програмиста. Ключовете също са уникални и може да има дублирани стойности. Основният член с данни на някоя от структурите е списъкът. Всяка структура има функции на членове, някои от които често се използват.