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

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

21.1 Стандарт кітапхананың алгоритмдері

21.2 find() қарапайым алгоритмі

21.2.1 Жалпыланған алгоритмдерді  қолданудың мысалдары

21.3 find_if() әмбебап іздеу алгоритмі

21.4 Функция-объектілер

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

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

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

21.5.3  inner_product алгоритмі

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

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

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

21.6.3 Ассоциативтік жиымның тағы бір мысалы

21.6.4 Unordered_map() алгоритмі

21.6.5. Көп мүшеліктер(Множества)

21.7 Көшіру (копирование)

21.7.1 Copy() алгоритмі

21.7.2 Итераторлар ағындары

 

 

21.1 Стандарт кітапхананың  алгоритмдері

Стандарт библиотекада 60-қа жуық алгоритмдер  бар. Олардың барлығы кей жағдайларда пайдалы; біз көпшілік жиі қолданатын және кейбір есептерді шешуге пайдалы алгоритмдерге көңіл аударамыз.

_____________________________________________________________________________

Таңдаулы стандарт алгоритмдер

 

r = find(b,e,v)   r итераторы v элементінің [b : e) реттілігіне бірінші рет енуін сілтейді

r = find_if(b,e,p) r итераторы x элементінің [b : e) реттілігіне бірінші рет енуін p(x) предикатының мәні true болған кезде сілтейді

x = count(b,e,v) x – бұл v элементінің [b : e) диапазонына ену саны

x = count_if(b,e,p) x – бұл v элементінің [b : e) диапазонына p(x) предикатының мәні true болған кездегі ену саны

sort(b,e)  < операторы арқылы [b : e) реттілігін реттеу

sort(b,e,p)  p предикаты арқылы [b : e) реттілігін реттеу

copy(b,e,b2) [b : e) реттілігін [b2 : b2 + (e-b)) реттілігіне көшіреді; b2 итераторынан кейін жеткілікті ұяшықтар болуы тиіс

unique_ copy(b,e,b2) [b : e) реттілігін [b2 : b2 + (e-b)) реттілігіне көшіреді; көршілес дубликаттар ескерілмейді

merge(b,e,b2,e2,r) негізінде бұл v элементін бинарлық түрде іздеу

equal(b,e,b2) [b : e)  мен [b2 : b2 + (e-b)) реттіліктерінің элементерін теңдікке тексереді

x=accumulate(b,e,i) x – бұл [b : e) реттілігінің і элементтерінің қосындысы

x=accumulate(b,e,i,op)  accumulate-тің басқа алгоритмдеріне ұқсас, бірақ сумма op операциясымен есептеледі

x=inner_product(b,e,b2,i)  x – бұл [b : e) және [b2 : b2 + (e-b))

x=inner_product(b,e,b2,i,op,op2)  inner_product-ің басқа алгоритмдеріне ұқсас, бірақ + және * операцияларының орнына op және op2 операцияларын қолданады

 

Үнсіз келісім бойынша теңдікті тексеру == операторы арқылы орындалады, ал реттеу

<(кіші) операторы арқылы. Стандартты кітапхананың алгоритмдері <algorithm> тақырыбында анықталған. Бұдан да нақты мәліметтерді оқырмандар Б.5 және 20.7 қосымшаларында таба алады. Бұл алгоритмдер бір немесе екі реттілікпен жұмыс істей алады. Берілген реттілік жұп итераторлармен анықталады, ал нәтижелік реттілік оның бірінші элементіне орнатылған итератормен анықталады. Ереже бойынша, алгоритм бір немесе бірнеше операциямен параметрлененді, оларды функция-объект немесе функция арқылы анықтауға болады. Алгоритмдер негізінен үзілістер туралы хабар беріп, берілген реттіліктің соңында орналасқан итераторды қайтарады. Мысалы, find(b,e,v) алгоритмі e элементін қайтарады егер v мәнін таппаса.

21.2 find() Қарапайым алгоритмі

Қарапайым алгоритмдердің ішіндегі find() ең оңайы деп есептеуге болады. Ол реттіліктен берілген мәнмен анықталған элементті табады.

 

template<class In, class T>

In find(In first, In last, const T& val)

//val – ға тең бірінші элементті [first,last) реттілігінен табады

{

while(first != last && *first != val) ++first;

return first;

}

 

find() алгоритмінің анықтауын қарайық. Сіз find() алгоритмін оның қалай жүзеге асырылғанын білмей-ақ қолдана аласыз. Біз оны бұрын қолданғанбыз (мысалы, 20.6.2 бөлімінде). Бірақ find() алгоритмі көптеген пайдалы жобалық идеяларды көрсетеді, сондықтан оны зерттеудің мәні бар.

Барлығынан бұрын find() алгоритмі жұп итераторлармен анықталған реттілікке қолданылады. Біз val мәнін жартылайашық [first,last) реттілігінен іздейміз. find() функциясының қайтартын нәтижесі итератор болып табылады. Ол val мәніне тең реттіліктің бірінші элементін немесе last элементін нұсқайды. Итератордың реттіліктің ең соңғы элементінен кейінгі элементін қайтаруы, STL кітапханасының алгоритмдерінің элемент табылмағаны жөніндегі хабарлауының ең кең таралған түрі. Сонымен біз find() алгоритмін келесі түрде қолдана аламыз:

 

void f (vector<int>& v, int x)

{

vector<int>::iterator p = find(v.begin(), v.end(), x);

if(p != v.end()) {

//біз x-ті v-дан таптық

}

else {

//v-да x-ке тең элемент жоқ

}

//…

}

 

Бұл мысалда, сонымен бірге көпшілік жағдайларда, реттілікте контейнердің барлық элементтері бар (біздің жағдайда вектордың). Біз қайтарылған итераторды реттілік соңымен, ізделініп жатқан элемент табылғанын білу үшін, салыстырамыз.

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

 

template<class In, class T>

In find(In first, In last, const T& val)

//val – ға тең бірінші элементті [first,last) реттілігінен табады

{

for (In р = first; p != last; ++p) if (*p == val)  return p; return last;

}

 

Бұл екі анықтау логикалық эквивалентті болып табылады және жақсы компилятор бұл екеуіне де бірдей код шығарады. Бірақ практикада көптеген компиляторлар (р) артық айнымалысын алып тастап, барлық тексерулер бір жерде болатындай етіп істей алмайды. Бұл не үшін керек? Себебі, find() алгоритмінің бірінші версиясының стилі кең қолданылады және біз оны басқалардың программаларын оқу үшін білуіміз керек, сонымен қатар тағы бір себебі, үлкен көлемді мәліметтермен жұмыс істейтін шағын функцияларда тиімділік үлкен рөл атқарады.

 

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

Сіз осы  екі анықтау логикалық эквивалентті екеніне сенімдісіз бе? Неге? Олардың  эквивалентті екеніне дәлел көрсетіп көріңіз. Содан кейін осы екі  алгоритмді бір мәліметтер жиынтығына қолданып көріңіз. Компьютерлік ғылымдардың  әйгілі маманы Дон Кнут кезінде айтып кеткен: “Мен тек қана алгоритмнің дұрыс екенін дәлелдедім, бірақ оны тексерген жоқпын”. Тіптен математикалық дәлелдерде қателіктер бар. Өз дұрыстығыңызды білу үшін дәлелдермен қатар, тестілеу нәтижелері де болуы керек.

_____________________________________________________________________________

 

21.2.1 Жалпыланған алгоритмдерді  қолданудың мысалдары

 find() алгоримті жалпыланған болып табылады. Бұл дегеніміз оны әр-түрлі мәліметтер типіне қолдануға болады.

• find() алгоримтін STL кітапханасының стиліндегі кез-келген реттілікке қолдануға болады.
• find() алгоримтін кез-келген элементтер типіне қолдануға болады.

Бірнеше мысал қарастырайық (егер оар сізге күрделі болып көрінсе 20.4 бөліміндегі диагаммаға қараңыз):

void f (vector<int>& v, int x) // бүтінсанды векторлармен жұмыс істейді {

vector<int>:: iterator p = find (v.begin(),v.end() ,x);

if  (p!=v.end()) 

{ /* біз x-ті таптық */ } //  .   . .

}

 

Мұндағы find() алгоримтінде қолданылған итераторларға қолданылатын операциялар, vector<int>:: iterator; типіндегі итераторларға қолданылатын операциялар болып табылады. Басқаша айтқанда ++ операторы нұсқауышты жадыдағы келесі ұяшыққа ауыстырады, ал * операторы бұл нұсқауышты ажыратады. Итераторларды салыстыру нұсқауыштарды салыстаруға айналады, ал мәндерді салыстыру қарапайым сандарды салыстыруға алып келеді.

Алгоритмді list классындағы оъектіге қолданып көрейік:

 

void f (list<string>& v, string x)  // тіркестер тізімімен жұмыс істейді

{

list<string>::iterator p = find(v.begin(),v.end(),x);

if (p!=v.end()) { /* біз x-ті таптық */ } // .  . .

}

 

 

 Мұндағы find() алгоримтінде қолданылған итераторларға қолданылатын операциялар, list<string>:: iterator; классындағы итераторларға қолданылатын операциялар болып табылады. Бұл операторлар сәйкес мағынаға ие, себебі оның жұмыс істеу алгоритмі алдыңғы мысалға ұқсас. Бірақ олар әр-түрлі болып жүзеге асырылған; (++first - тегі) ++ операторы тізімнің келесі түйініне орнатылған нұсқауыштың артынан жүреді, ал (*first - тегі) * операторы link түйініндегі мәнді табады. Итераторларды салыстыру *link классты нұсқауыштарды салыстаруға айналады, ал мәндерді салыстыру string классындағы != операторы арқылы жолдарды салыстыру болып табылады.

Сонымен, find() алгоримті өте иілгіш болып табылады: егер біз итераторлармен жұмыс істеу ережесін ұстансақ, онда find() алгоримтін кез-келген контейнердегі кез-келген реттіліктегі элементті іздеу үшін қолдана аламыз. Мысалы, find() алгоримті арқылы біз Document (20.6 бөлім) классындағы объектідегі символды іздей аламыз:

 

void f (Document& v , char x)  //Document классындағы объектілермен жұмыс істейді {

Text_iterator p = find(v.begin(),v.end() ,x) ;

if (p!=v.end())  { /* біз x-ті таптық*/ } // .  . .

}

 

Бұл иілгіштік STL кітапханасындағы алгоритмдердің айқын сипаты болып табылады және оларды өте ыңғайлы етеді.

 

21.3 find_if() әмбебап іздеу  алгоритмі

 

Бізге белгілі  бір нақты элементті іздеу  сирек кездеседі. Негізінен белгілі  бір шарттарды қанағаттандыратын  мәнді іздеу кеңінен таралған. Біз find операциясынан да пайдалы операцияны жүзеге асыруымыз мүмкін, егер өзіндік іздеу критерийлерін анықтай алғанда. Мысалы, біз 42 санынан үлкен сандарды іздеуіміз мүмкін. Сонымен бірге тіркестерді регистрді(үлкен не кіші) ескермей-ақ  салыстыруымыз мүмкін. Сонымен бірге бірінші тақ санды табуымыз немесе "17 Cherry Tree Lane" деген жазуды табуымыз мүмкін.

Іздеудің қолданушы анықтаған  критерий бойынша іздеудің стандартты алгоритмі find_if() деп аталады:

template<clase In, class Pred>

In find_if(In first, In last, Pred pred)

{

while  (first != last && !pred(*first)) ++first; return first;

}

 

Бұл алгоритм find() алгоримтіне ұқсас болып келеді, бірақ мұндағы шартта *first != val; емес !pred(*first) қолданылады. Басқаша айтқанда алгоритм іздеуді pred() ақиқат болғанда тоқтатады.

 Предикат (predicate) – бұл true немесе false мәнін қайтаратын функция. find_if() алгоритмі бір аргументті қабылдайтын предикатты pred(*first) дұрыс болуы үшін талап етеді.

Мысалы, біз  бүтінсанды векторда бірінші тақ  санды таба аламаыз:

^{bool odd (int х)  { return х%2; } // % модуль бойынша бөлу}

void f(vector<int>&v) {

vector<int>: : iterator p = find_if (v.beginO , v.end(), odd); if  (p!=v.end())  { /* біз тақ санды таптық */ } //  .   . .

}

 

Бұл щақыруда find_if() алгоритмі odd() функциясын әрбір элементке бірінші тақ санды таппағанша қолданады. Аналогты түрде біз тізімнің 42-ден асатын бірінші элементін таба аламыз:

 

bool larger_than_42 (int х)  { return х>42; }

void f(list<double>& v) {

list<double>: : iterator p = find_if (v.beginO , v.end(), larger_than_42) ;

if (p!=v.end())  { /*біз 42-ден асатын мәнді таптық */ } // .   . .

}

 

Бірақ соңғы мысал қанағаттанарлық емес. Мәселен біз 19-дан немесе 42-ден үлкен элемент тапқымыз келсе ше? жаңа функция жазу? Басқа тәсіл болуы керек!

Мысалы:

 

int v_val; // larger_than_v() предикаты өз аргументімен

// салыстыратын мән

bool larger_than_v(int х)  { return x>v_val; }

void f(list<double>& v, int x) {

v_val = 31; // v_val айнымалысын 31-ге теңестіреміз

list<double>::iterator р = f ind_if (v.begin () , v.end(),

larger_than_v);

if (p!= v.end()) { /* біз 31-ден асатын мәнді таптық */ }

v_val = х;    //v_val айнымалысын х-ке теңестіреміз

list<double>: : iterator q = f ind_if (v.begin () , v.end(), larger_than_v);

if (q != v.end())  { /* х-тен асатын мәнді таптық*/ }

// .  . .

}

 

 Өте жаман! Мұндай программа жазған адамдар оңбайтын шығар!

Қайталаймыз: Басқа тәсіл болуы керек!

 

21.4 Функция-объектілер

 

Сонымен біз find_if() алгоритміне предикат бергіміз келеді және де осы предикат біз оның аргументі ретінде тағайындаған мән элементтерді салыстыруы керек. Мәселен біз мынадай код жазымыз келеді:

 

void f (list<double>& vf  int x) {

list<double>: : iterator p = find_if (v.begin () , v.end(),

Larger_than(31)); if  (p!=v.end())  { /* 31-ден асатын сан табылды */ }

 

list<double>:: iterator q = f ind_if (v.begin () , v.endO,

Larger_than(x));

if (q!=v.end())  { /* х-тен асатын сан табылды*/ }

...

}

 

Larger_than функциясы екі шартты қанағаттандыруы керек:

• Оны предикат ретінде шақыруға болады, мысалы pred(*first)
• Ол шақыруда берілетін мән сақтауы мүмкін

 

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

 

class Larger_than {

int v;

public:

Larger_than(int vv)   : v(vv)  { } // аргумент сақтайды

bool operator() (int x) const { return x>v; } // салыстыру

 

Ескере  кететін жағдай, бұл анықтау дәл  біз предикаттан талап еткенді  көрсетеді.

 

21.4.1 Функция-объектілерге абстрактілі  көзқарас

 

  Сонымен бізде өзіне керекті мәліметтерді сақтайтын функциясы бар механизм бар№. Функция-объектілер мықты, ыңғайлы әрі әмбебап механизмді құрайды. Функция-объект түсінігін тереңірек қарастырайық.

 

class F {     // S функция-объектінің абстрактілі мысалы

S s;   // қалып-күй

public:

F(const S& ss)  :s(ss) { /* бастапқы мән орнатады */ }

Т operator()   (const S& ss) const

{

// ss аргументімен бірдеңе істейді

// Т титі мән қайтарады (негізінен Т — бұл void,

// bool немесе S)

}

const S& state () const { return s; } // қалып-күйді көрсетеді

void reset(const S& ss)  { s = ss; }    // қалып-күйді қайтарады

};

 

F объектісінің классы өзінің s мүшесінде мәліметтер сақтайды. Қажеттілік бойынша функция-объектіде көптеген мүше-мәліметтер бола алады. Кейде “бірдеңе мәліметтер сақтайды” сөйлемінің орнына “бірдеңе қалып-күйде болады” дейді. F объектісінің классын құрған кезде біз осы қалып-күйді инициализациялай аламыз. Қажет болса бұл қалып-күйді оқи аламыз. F классында қалып-күйді оқу үшін state() операциясы, ал жазу үшін reset() операциясы қолданылады. Бірақ функция-объектіні құрған кезде, біз оның қалып-күйіне ену тәсілін өз еркіміз бойынша тағайындай аламыз.

Әлбетте, біз функция-объектіні  қарапайым белгілеулер жүйесін  қолданып, тікелей немесе жанама шақыра аламыз. Шақыру кезінде F функция-объектісі бір аргумент алады, бірақ біз қанша болса да параметр қабылдай алатын функция-объектілерді шақыра аламыз.

 Функция-объектілерді қолдану  STL кітапханасындағы параметризацияның негізгі тәсілі болып табылады. Біз функция-объектілерді іздеу алгоритміне бізге нақты не керек екендігін нұсқай аламыз, сонымен бірге сорттаудың критерийлерін анықтауға, сандық алгоритмдерде арифметикалық операцияларды нұсқауға, қандай объектілер тең екендігін көрсетуге және т.б.

 Функция-объектілер өте тиімді  болып табылады. Мәселен, шағын  функция-объектіні мәні бойынша  шаблондық-функцияға аргументі ретінде жіберу ұтымды өнімділікті қамтамасыз етеді. Себебі қарапайым, бірақ функцияға аргументі ретінде жіберу механизмін жақсы білетін адамдарға таңқаларлық. Бұл пікір ақиқат, тек қана объект кішкентай болса немесе ссылка бойныша жіберілсе, сонымен қатар функцияны шақыру операторы үлкен емес болса. Осы бөлімдегі және осы кітаптағы көпшілік мысалдар осы мысалды ұстанады. Осындай шағын әрі қарапайым функция-объектілірінің жоғары өнімділігінің негізгі себебі, олар компиляторға ұтымды код жасау үшін тип туралы жеткілікті информациямен қамтамасыз етеді. Әдетте функцияны шақыру қарапайым салыстыруға қарағанда 10-50 есе көп уақытты талап етеді. Сонымен қатар оның коды да көбірек.