Алгоритмдер мен ассоциативтік жиымдар

 

21.4.2 Класс мүшелеріндегі  предикаттар

 

Бұрын көріп кеткеніміздей стандартты алгоритмдер негізгі типті (int, double) элементтер реттілігімен жақсы жұмыс істейді. Бірақ кейбір пәндік аймақтарда қолданушы класстарының объектілер контейнерлері кеңірек қолданылады. Көптеген аймақтарды басты рөл атқаратын мысал қарастырайық (жазуларды бірнеше критерий бойынша сорттау):

 

struct Record {

string name;      // стандартная строка

char addr[24];    // старый стиль для

// с базами данных

//  ...

};

vector<Record> vr;

 

Кейде біз  vr векторын аты бойынша, кейде адресі бойынша сорттағымыз келеді. Келесі код жазуымызға болады:

 

// . . .

sort(vr.begin(), vr.end(), Cmp_by_name()) ; // аты бойынша сорттау

// . . .

sort(vr.begin(), vr.end(), Cmp_by_addr()) ; // адресі бойынша сорттау

// . . .

 

 Cmp_by_name – бұл Record классының екі объектісін name мүшесі арқылы салыстыратын функция-объект. Sort стандартты алгоритмінде қолданушыға іздеу критерийлерін тағайындауға мүмкіндік беру үшін үшінші қажетті емес аргумент ескерілген. Cmp_by_name() функциясы sort() алгоритмі үшін Cmp_by_name объектісін Record классының объектілерін салыстыру үшін құрады. Бізден керектісі тек Cmp_by_name және Cmp_by_addr класстарын құру.

 

// Record классының объектілерінің әр-түрлі салыстырулары

 

struct Cmp_by_name {

bool operator()(const Record& a, const Record& b) const

{ return a.name < b.name; }

};

struct Cmp_by_addr {

bool operator()(const Record& a, const Record& b) const

{ return strncmp(a.addr, b.addr, 24) < 0; } // !!!

};

 

Cmp_by_name классы айқын болып табылады. Функцияны шақыру операторы operator()name – нің тіркестерін < операторын қолданып салыстырады. Ал Cmp_by_addr классындағы салыстыру өте жаман! Оның себебі біз адресті 24 символдан тұратын (және нөлмен аяқталмайтын) массив ретінде алдық. Бұлай істеген себебіміз функция-объектіні әдемі емес және қателерге осал код үшін қалай пайдалануға болатынын көрсеткіміз келді, сонымен бірге STL кітапханасының тіптен осындай жаман есептерді шығара алатынын. Салыстыру функциясы стандартты strncmp() функциясын қолданады, ол екі тіркесті лексикографиялық түрде салыстырады және бір тіркес екіншісінен үлкен болса теріс сан қайтарады. Сізге осындай ескірген салыстыруды істеу қажет болса, осы функцияны еске алыңыз!

 

21.5 Сандық алгоритмдер

STL кітапханасының көпшілік стандартты алгоритмдері мәліметтерді өңдеумен айналысады: олар мәліметтерді көшіреді, сорттайды, олардың ішінде іздеу жүргізеді. Бірақ олардың кейбіреулері есептеумен де айналысады. Олар нақты бір есепті шешуге тиімді болуы мүмкін, сонымен қатар STL кітапханасының сандық алгоритмдерін іске асыру принциптерін көрсету үшін де тиімді болып табылады. Бұндай алгоритмдердің тек 4 түрі бар.

 

Numerical algorithms

Сандық алгоритмдер

 

x=accumulate(b,e,i) Реттіліктерді қосындылайды; мысалы {a,b,c,d} реттілігі үшін нәтиже a+b+c+d болады. x типінің нәтижесі і бастапқы мәнімен сәйкес келеді

x=inner_product(b,e,b2,i) Екі реттіліктегі жұп мәндерінің еөбейтіндісінің қосындысын береді. Мысалы, {a,b,c,d} және {e,f,g,h} реттіліктері үшін нәтиже a*e+b*f+c*g+d*h болады. x типінің нәтижесі і бастапқы мәнімен сәйкес келеді

r=partial_sum(b,e,r) Берілген реттілікің бірінші n элементтерінің қосындысынан тұратын жаңа реттілік береді. Мысалы, {a,b,c,d} үшін нәтиже {а, a+b, а+Ь+с, a+b+c+d) болады

r=adjacent_difference(b,e,b2,r)   Мұнда {a,b,c,d} үшін нәтиже {a,b-a,c-b,d-c} болады

21.5.1 accumulate() алгоритмі

Сандық  алгоритмдердің ішіндегі ең оңайы әрі  тиімдісі accumulate() алгоритмі болып табылады. Ең қарапайым вариантында ол реттілікті қосындылайды:

 

template<class In, class Т> Т accumulate (In first, In last, T init) {

while  (first!=last) {

init = init + *first;

++first;

}

return init;

}

 

init  алғашқы мәнін алып, ол [first,last) реттілігінің қосындысын қайтарады. Қосынды жиналатын init  айнымалысын аккумулятор(accumulator) деп атайды. Мысал қарастырайық:

 

int а[]   = { 1,  2,  3,  4,  5 };

cout << accumulate(a, a+sizeof(a)/sizeof(int), 0);

 

Бұл код фрагменті 15 мәнін  шығарады (0+1+2+3+4+5), мұнда 0 бастапқы мән. accumulate() алгоритмін кез-келген реттілікке қолдануға болады.

 

void f(vector<double>& vd,  int* p, int n) {

double sum = accumulate (vd. begin (), vd.end(), 0.0);

int sum2 = accumulate(p,p+n,0) ;

}

 

accumulate() алгоритмі аккумулятор ретінде қолданатын нәтиже(қосынды) типі айнымалы типімен сәйкес келеді. Бұл өте маңызды рөл ойнайтын иілгіштікті қамтамасыз етеді. Мысал қарастырайық:

 

void f(int* р,  int n) {

int s1 = accumulate (p, p+n, 0);    // бүтін сандарды int-қа қосындылайды

long s1 = accumulate(p, p+n, long(0)); // бүтін сандарды long-қа қосындылайды

double s2 = accumulate(p, p+n, 0.0);      // бүтін сандарды double-ға қосындылайды

}

 

Кейбір компьютерлерде long типі int типіне қарағанда көбірек цифрлардан тұрады. Double типті айнымалы int типті айнымалыларына қарағанда үлкен не кіші сандарды көрсете алады, бірақ мүмкін кішірек дәлдікпен. 24-ші бөлімде біз қайтадан диапазон мен дәлдік тақырыбына қайта ораламыз.

 

 init  айнымалысын аккумулятор ретінде қолдану, аккумулятор типін беруге болатын кең таралған идиомаға сәйкес келеді.

 

void f (vector<double>& vd, int* p, int n)

{

double s1 = 0;

s1 = accumulate (vd. begin () , vd.end(), s1);

int s2 = accumulate (vd. begin () , vd.end(),  s2) ;  // ой

float s3 = 0;

accumulate (vd. begin () , vd.end(), s3) ; // ой

}

 

 Аккумуляторды инициализациялауды  және  accumulate() алгоритмінің нәтижесін бір айнымалыға меншіктеуді ұмытпаңыз! Бұл мысалда инициализатор ретінде s2 айнымалысы алынған, бірақ алгоритмді шақыру кезінде оған бастапқы мән берілмеген; мұндай шақырудың нәтижесін болжауға болмайды. Біз s3 айнымалысын accumulate() алгоритміне бердік, бірақ нәтижені ештеңеге меншіктемедік; мұндай компиляция жай уақытты бос жоғалту болып табылады.

 

21.5.2  accumulate() алгоритмін  жалпылау

 

Сонымен, 3 аргументтен тұратын негізгі accumulate() алгоритмі қосындылауды жүзеге асырады. Бірақ қосындылаудан басқа көбейту және бөлу сияқты басқа да тиімді операциялар бар. Соған байланысты STL кітапханасында 4 аргументтен тұратын accumulate() алгоритмінің тағы бір версиясы бар, мұнда керекті операцияны тағайындауға болады.

 

template<class In, class Т, class BinOp>

T accumulate(In first, In last, T init, BinOp op) {

while (first != last) {

init = op(init, *first);

++first;

}

return init;

}

 

Мұнда аккумулятор типімен сәйкес келетін екі аргументті кез-келген бинарлық операцияға қолдануға болады. Мысал қарастырайық:

 

array<double,4> а = { 1.1,  2.2,  3.3, 4.4 }; // 20.9 бөліміе қарау

cout << accumulate (a.begin() ,a.end() , 1.0, multiplies<double> ());

 

Бұл код  фрагменті баспаға 35.1384 санын шығарады, яғни 1.0*1.1*2.2*3.3*4.4 (1.0 – бастапқы мән). Аргумент ретінде берілетін multiplies<double> () бинарлық операторы көбейтуді орындайтын стандартты функция-объект болып табылады. Басқа да бинарлық функция-объектілер бар: оларға plus (қосу), minus (азайту), divides және modulus (бөлуден қалдықты есептеу). Бұлардың барлығы <functional> тақырыбында анықталған.

 Жылжымалы нүктелі сандарды көбейту үшін бастапқы мән ретінде 1.0 алынғанына назар аударыңыздар! Sort() алгоритмындағы мысалдағыдай бізді қарапайым типті мәліметтер емес, класстардағы объектілерде сақталатын мәліметтер қызықтырады. Мысалы біз тауарлардың жалпы көлемі мен бірлігінің бағасын біліп, олардың жалпы бағасын есептей алар едік.

 

struct Record {

double unit_price;

int units;  // бірліктердің сатылған саны

//...

};

 

Біз accumulate() алгоритмінің анықтауында кез-келген операторға units – тан мәліметтер алғызып, оны Record классының сәйкес элементіне көбейте аламыз.

 

double price(double v, const Record& r) {

return v + r.unit_price * r.units;  // бағаны есептейді

// және қорытындыны сақтайды

}

void f(const vector<Record>& vr) {

double total = accumulate(vr.begin(), vr.end(),  0.0, price);

//  ...

}

 

Біз ерініп есептеу үшін функция-объект емес жай функцияны қолданғанымыз, бұлай да істеуге болатынын көрсету  үшін. Сонда да функция-объектілерді келесі жағдайларда қолданған жөн  болар:

• Егер шақырулар арасында мәліметтерді сақтауға қажет болса.
• Егер олардың қысқалығы соншалық, оларды ауыстырып қоюға мүмкін болатын жағдайларда.

 

Бұл жағдайда біз тізімнің екінші пунктіне сүйеніп, функция-объектіні қолдана алар едік.

 

 Байқап көріңіз

vector<Record> классын анықтаңыз , үстідегі функцияларды қолдана отырып, өз қалауыңыз бойынша 4 жазу инициализациялап олардың жалпы бағасын есептеңіз.

_____________________________________________________________________________

 

21.5.3  inner_product алгоритмі

 

Екі вектор алып, оларды жұп-жұбымен көбейтіп осы көбейтінділерді қосыңыз. Бұл есептеудің нәтижесі екі вектордың скаляр көбейтіндісі (inner product) деп аталады. Бұл операция көптеген пәндік аймақтарда кең таралған (мыс: физика, сызықтық алгебра).

Мысалы:

 

template<class In, class In2, class Т>

Т inner_product(In first, In last, In2 first2, T init)

// ескерту: екі вектордың скаляр көбейтіндісін есептейді

{

while(first!=last) {

init = init +  (*first)  *  (*first2);  // элементтерді

// көбейтеміз

++first;

++first2;

}

return init;

}

 

Бұл алгоритмнің версиясы кез-келген типті кез-келген реттілік үшін скаляр көбейту ұғымын жалпылайды. Мысал ретінде биржалық индексті қарастырайық. Ол компанияларға белгілі бір салмақтарды меншіктеу арқылы есептеледі. Мысалы, Доу-Джонсытың Alcoa индексі жазу моментінде 2,4808 – ге тең болған. Осы индекстің қазіргі шамасын есептеу үшін, әрбір компанияның акциясын оның салмағына көбейтіп, шыққан нәтижені қосамыз. Әлбетте, бұдан шығатыны бағалар мен салмақтардың саляр көбейтіндісі. Мысал қарастырайық:

 

//Доу-Джонс индексін есептеу

vector<double> dow_price;   // әрбір компанияның акциясының бағасы

dowjprice.push_back(81.86);

dowjprice.push_back(34.69);

dowjprice.pushjback(54.45);

// .  . .

list<double> dow_weight;   // әрбір компанияның салмағы индексте

dow_weight.push_back(5,8549);

dow_weight.push_back(2.4808) ;

dowweight.push_back(3.8940) ;

// . . .

double dji_index = inner_product (// жұптарды көбейтеміз (weight,value)

//және  қосындылаймыз

dow_price.begin(), dow_price.end(), dow_weight.begin() , 0.0) ;

cout «  "Значение DJI ? << dji_index << '\n';

 

 inner_product() алгоритмі екі реттілікті алатынына назар аударыңыздар! Сол уақытта ол тек 3 аргумент алады: екінші реттілікте тк оның басы беріледі. Екінші реттілікте бірінші реттілікке қарағанда элементтер саны кем емес деп болжамданады. Керісінше жағдайда біз қате туралы хабарлама аламыз.  Бірақ inner_product() алгоритмінде біріншіге қарағанда элементтер саны көбірек болуы мүмкін; артық элементтер қолданылмай қалады.

 Екі реттілік бірдей типті  немесе олардың элементтері бір типті болуы шарт емес. Бұны көрсету үшін біз бағаларды vector классының объектісіне, ал салмақтарды list классының объектісіне жаздық.

 

21.5.4  inner_product алгоритмін  жалпылау

 

inner_product() алгоритмін accumulate() алгоритмі сияқты жалпылауға болады. Бірақ алдыңғы алгоритмге қарағанда inner_product() алгоритміне тағы екі аргумент қажет: біріншісі – аккумуляторды жаңа мәнмен байланыстыру үшін, ал екіншісі – жұптар мәнімен байланыстыру үшін.

 

template<class In, class In2, class Т, class BinOp, class BinOp2 >

T inner_product(In first,  In last, In2 first2, T init, BinOp op, BinOp2 op2)

{

while(first!=last) {

init = op(init, op2(*first, *first2));

++first;

++first2;

}

return init;

}

 

 

 

 

 

21.6 Ассоциативтік контейнерлер

 Vector классынан кейін қолдану кеңдігі жағынан екінші орында тұратыны map контейнері болып табылады. Ол жұптардың (кілт, мән) реттелген реттілігінен тұрады және мәнді кілт арқылы табуға мүмкіндік береді; мысалы, my_phone_book[“Nicholas”] элементі Николастың телефон номері болуы мүмкін. Map классының жалғыз бәсекелесі болып unordered_map бола алады, ол тіркес ретінде көрсетіледі және кілттер үшін оптимизацияланған. Map және unordered_map контейнерлеріне аналогты мәліметтер құрылымдарына мыналар жатады: ассоциативтік жиымдар (associative arrays), хеш-таблицалар (hash tables) және қызыл-қара талдар (red-black trees). Танымал және тиімді ұғымдардың аттары көп болып келеді. Біз олардың барлығын ассоциативтік контейнерлер деп атаймыз. Стандарт кітапханада 8 ассоциативтік контейнер бар.

 

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

_____________________________________________________________________________

 

map    Жұптардың (кілт, мән) реттелген контейнері

set    Кілттердің реттелген контейнері

unordered_map  Жұптардың (кілт, мән) реттелмеген контейнері

unordered_set  Кілттердің реттелмеген контейнері

multimap   Кілт бірнеше рет кездесе алатын map контейнері

multiset   Кілт бірнеше рет кездесе алатын set контейнері

unordered_ multimap Кілт бірнеше рет кездесе алатын unordered_map контейнері

unordered_ multiset  Кілт бірнеше рет кездесе алатын unordered_ multiset      контейнері

 

Бұл контейнерлер <map>, <set>, <unordered_map> және <unordered_set> тақырыптарында анықталған.

 

21.6.1 Ассоциативтік жиымдар

 

Қарапайым мысалды қарастырайық: Текстке сөздердің ену тізімінің нөмірлерін құрайық.

 

int main () {

map<string,int> words; // жұптар сақтайды

 

string s;

while  (cin>>s)  ++words[s]; // words контейнері тіркестермен индекстеледі

typedef map<string,int>::const_iterator Iter;

for  (Iter p = words.begin(); p!=words.end() ; ++p)

cout << p->first << ":  " << p->second << '\n';

}

 

Бұл программаның ең қызықты жері ++words[s] болып табылады. main () фунциясының бірінші жолында көрініп тұрғандай, words айнымалысы бұл жұптардан тұратын(string,int) map классының объектісі. Сонымен, біз string класс объектісін words контейнерімен индекстегенде, s тіркесіне сәйкес келетін int типті санға words[s] элементі ссылка болып табылады. Нақты мысал қарастырайық.

 

words["sultan"]

 

 

 

 Егер "sultan" тіркесі әлі болмаса, онда ол words контейнеріне мәнімен (үнсіз келісім бойынша int типті 0) бірге кірістіріледі. Енді words контейнерінде ("sultan",0) элементі бар. Бұдан шығатыны, егер "sultan" тіркесі әлі енгізілмеген болса, онда ++words[sultan] "sultan" тіркесін 1 мәнімен байланыстырады. Дәлірек айтқанда, map классының объектісі "sultan" тіркесінің жоқ екендігін біліп, ("sultan",0) жұбын енгізеді, содан соң ++ операторы бұл мәнді бір бірлікке арттырады, соның нәтижесінде ол 1-ге тең болады.

Енді цикл мағынасы түсінікті.

while  (cin>>s)  ++words[s];

Ол әрбір (пробелмен  бөлінген) сөзді енгізу ағынынан оқып, оның контейнерге ену санын анықтайды. Енді бізге нәтижені шығару ғана қалды. map контейнері бойынша STL кітапханасының кез-келген контейнері сияқты жылжуға болады. map<string,int> контейнерінің элементтері pair<string,int> типіне ие. pair классы объектісінің бірінші мүшесінің first – ке тең, ал екіншісі – second. Шығару циклі былай көрсетіледі:

 

typedef map<string,int>::const_iterator Iter;

for (Iter p = words .begin () ; p ! = words. end () ; ++p)

cout << p->first << ":  " << p->second << '\n';

 

typedef операторы программаның ыңғайлы жұмысы мен ыңғайлы оқылуы үшін қажет. Текст ретінде біз The С++ Programming Language кітабының кіріспе текстін алдық: