Новини во програмскиот јазик C++
Програмскиот јазик C++, како и останатите помодерни програмски јазици, добива нови функционалности и можности со развојот на техниката. Во ова предавање, ќе се запознаеме со неколку корисни придобивки од верзијата C++11 на програмскиот јазик C++, која е веќе поддржана од сите позначајни компајлери и интегрирани развојни околини. Овие функционалности ќе ни помогнат да пишуваме подобар код, како и да избегнеме дел од проблемите кои беа дел од C++ во неговите претходни верзии.
Подесување на Code::Blocks
По правило, Code::Blocks ја користи старата верзија на програмскиот јазик C++. За да овозможиме пишување на код во верзијата C++11, потребно е да ја направиме следната промена:
- Од кога ќе го отвориме Code::Blocks, од горното мени (каде што се наоѓаат копчињата File, Edit, View, Search, итн), одбираме Settings, па Compiler.
- Во новоотвореното прозорче, штиклирајте ја следната опција: "Have g++ follow the C++11 ISO C++ language standard"
- Притиснете на копчето OK, на дното на прозорчето. (Доколку не можете да ги пронајдете овие подесувања, осигурајте се дека ја имате инсталирано последната верзија на Code::Blocks - за што можете да најдете линк во ова предавање)
Доколку имате проблеми, разгледајте ја следната слика. На истата, се претставени чекорите кои треба да ги преземете.
Поедноставно создавање на структури
Во претходното предавање, каде се запознавме со можностите на Стандардната библиотека на шаблони во C++, зборувавме и за создавање на парови, и како тоа може да се направи со помош на функцијата make_pair. Дополнително, зборувавме и за разни други податочни структури и како истите се користат во C++.
Во новите верзии на програмскиот јазик C++, можеме да создаваме парови со едноставно наведување на потребните вредности помеѓу заградите { и }. Дополнително, истата функционалност можеме да ја користиме и за создавање на низи со динамичка големина, множества и слично. Поконкретно, сите овие примери се валидни и може да се користат:
pair<int, int> coordinates = {3, 5};
vector<int> v = {1, 2, 3, 4, 5};
set<int> s = {1, 2, 3, 4, 5};
Во продолжение, ќе ја користиме оваа функционалност и кај конкретни програми.
Поедноставено запишување на циклуси
Дополнително, покрај начините за дефинирање на циклуси кои ви се веќе познати, во C++11 постои и дополнителен начин за движење низ елементите на податочни структури. Притоа, тоа го правиме со кoристење на исказот for, но запишан поинаку од она што ни е веќе познато. Имено, овој пат, го користиме податочниот тип на елементите, и името на променливата - без да има потреба да дефинираме ништо друго. За низа со динамичка големина numbers<int>, која чува цели броеви, може да го запишеме следното:
for(int x : numbers){
cout << x << endl;
}
Овој код ќе ги отпечати сите елементи кои се наоѓаат во numbers. Притоа, ова поедноставно запишување на циклуси, покрај кај низите со динамичка големина, можеме да го користиме и кај листите, и кај множествата. Дополнително, вакво движење низ елементите може да правиме и кај мапите, со таа разлика што, во for циклусот, променливата ќе биде од податочен тип pair<>, каде првата вредност (first) ќе покажува на клучот, додека втората (second) ќе покажува на тековната вредност. Да ја разгледаме следната програма:
Програма 5.1
//koristi C++11 - http://mendo.mk/Lecture.do?id=26
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int, string> names;
names[0] = "Darko";
names[1] = "Bojan";
names[2] = "Elena";
for(pair<int, string> value : names)
{
cout << value.first << ": " << value.second << endl;
}
//0: Darko
//1: Bojan
//2: Elena
return 0;
}
Во примерот даден погоре, со коментари на крајот е означен излезот од програмата. Интересно, кога се работи за движење низ елементите на една низа со динамичка големина, можеме и да ги менуваме вредностите на истата директно. За тоа, кај for исказот, користиме референца до самиот елемент, со помош на операторот &. На пример, следниот код ќе ги зголеми сите елементи за 1.
for (int &x: numbers){
x++;
}
Автоматско одредување на податочниот тип
Во претходната програма, сигурно ви делува непотребно да запишеме дека value има податочен тип pair<int, string>. Едноставно, очекуваме дека компјутерот би можел сам да открие дека тоа е потребниот податочен тип - имајќи предвид дека погоре, така е дефинирана мапата names. И, во право сте. Во поновите верзии на програмскиот јазик C++, воопшто нема потреба да го внесуваме точниот податочен тип, доколку постои начин самиот компјутер тоа да го открие. Во конкретниот пример, можеме да го замениме редот:
for(pair<int, string> value : names)
со
for(auto value : names)
Програмата повторно ќе работи. Во продолжение на овие предавања, секогаш каде нема потреба експлицитно да го дефинираме податочниот тип, ќе користиме auto. Сепак, забележете дека auto има ограничена употреба, и истото не може да се користи при дефинирањето на самите податочни структури, како vector<auto> v. Едноставно, програмскиот јазик, во тој дел од програмата, нема информации какви податоци сакате да чувате.
Итератори
Овој дел од предавањето ќе биде малку посложен, но е важен за вистинско разбирање на можностите кои ги нуди Стандардната библиотека на шаблони. Во претходното предавање, споменавме неколку алгоритми и како тие се користат. Еден од нив беше, на пример, алгоритамот за подредување на елементи. Притоа, забележавте дека при повикувањето на тој алгоритам, ги искористивме функциите begin() и end(). На пример, за подредување на елементите во низата со динамичка големина numbers, ја напишавме следната наредба:
sort(numbers.begin(), numbers.end());
Во Стандардната библиотека на шаблони, овие две функции begin() и end() може да се применуваат врз разни податоци (множества, мапи, листи, итн) и тие секогаш враќаат соодветни покажувачи кои ги означуваат почетокот и крајот на податочната структура. Притоа, begin() покажува на првиот елемент, додека end() покажува веднаш по последниот елемент (т.е. end() - 1 покажува на последниот елемент). Така, всушност, ние при повикувањето на алгоритамот за подредување, му кажуваме дека сакаме тој да ги подреди сите елементи во низата со динамичка големина. Забележете дека begin() и end() се покажувачи (а не вредности), па за да ја добиеме точната вредност, треба да го искористиме операторот *, на пример *numbers.begin(). Конкретно, бидејќи овие функции важат кај повеќе податочни структури, со наредбите дадени во продолжение можеме да го испечатиме првиот и последниот елемент во една низа со динамичка големина, листа или множество:
auto first = numbers.begin();
auto last = --numbers.end();
cout << *first << endl;
cout << *last << endl;
Бидејќи, кај set<>, се користи бинарно дрво за чување на елементите, begin() покажува на најмалиот елемент, додека end() - 1 на најголемиот.
Тука, време е да ја споменеме и точната терминологија која се користи кај Стандардната библиотека на шаблони. Имено, за самите структури во кои чуваме вредности се користи терминот контејнери (vector, list, set, map, итн), додека за покажувачите кои ги разгледавме погоре се користи терминот итератори. Значи, кај Стандардната библиотека на шаблони, зборуваме за контејнери и итератори.
Запознавањето со итераторите ни дава можност да споменеме уште две функции кои се важни за контејнерите кои се базираат на бинарни дрва (на пример, set<> и map<>). Имено, понекогаш сакаме да најдеме кој е првиот елемент поголем од некој број. Кај бинарните дрва, оваа операција има логаритамска временска сложеност O(logN), значи истата се прави исклучително ефикасно. Функциите кои ни го овозможуваат ова се lower_bound(K) за покажувач до првиот елемент поголем или еднаков на K, или upper_bound(K) за првиот елемент поголем од K (ако не не интересираат еднаквите елементи). Ова е прикажано со следната програма. Притоа, забележете како одредени проблеми кои ги решаваме со помош на компјутер, се решаваат со директно користење на вакви моќни податочни структури.
Програма 5.2
//koristi C++11 - http://mendo.mk/Lecture.do?id=26
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<char> letters = {'A', 'B', 'C', 'D', 'E'};
auto bigger_or_equal = letters.lower_bound('C');
cout << *bigger_or_equal << endl; //'C'
auto strictly_bigger = letters.upper_bound('C');
cout << *strictly_bigger << endl; //'D'
return 0;
}
Бинарните дрва се исклучително моќни, и истите решаваат различни проблеми. Познавањето на нивните можности, и кога тие може да се применат, ќе ве направи многу подобар програмер.
Хеш табели
Почнувајќи со C++11, Стандардната библиотека на шаблони нуди можност за директно користење на хеш табели. Притоа, самите контејнери (чиј термин го објаснивме погоре) имаат многу слични имиња како и оние кои ги споменавме кај множествата и мапите кои користат бинарни дрва за чување на податоците. Имено, за да користиме хеш табела за чување на вредности во множество ќе користиме unordered_set<>, додека за да користиме хеш табела за чување на вредности во мапа ќе користиме unordered_map<>. Притоа, именувањето на функциите е исто како и претходно. За unordered_set<>, можеме да го најдеме бројот на елементи со size(), да додадеме нов елемент со insert(), да избришеме елемент со erase(), и да провериме дали некој елемент постои со count(). Сите овие операции се со константна сложеност O(1). Поради различната организација на елементи, кај хеш табелите не можеме ефикасно да пронајдеме најмал или најголем елемент или да користиме функции како lower_bound() - па, во тие случаи, може да се искористи set<>, кој е базиран на бинарно дрво. Во ситуациите каде само додаваме и бришеме елементи, или проверуваме дали еден елемент е веќе во множеството, хеш табелите би требало да се поефикасни, па во понатамошните предавања, често ќе ги користиме и нив.
Како и кај map<>, каде вредностите се чуваат во бинарно дрво, и кај unordered_map<> можеме да го користиме операторот [] за додавање, менување или читање на вредности. Притоа, временската сложеност тука ќе биде O(1).
Програма 5.3
//koristi C++11 - http://mendo.mk/Lecture.do?id=26
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
int main()
{
vector<int> numbers = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
unordered_set<int> different;
unordered_map<int, int> occurrences;
for(auto number : numbers)
{
different.insert(number);
occurrences[number]++;
}
//different = [1, 2, 3, 4, 5]
cout << different.size() << endl; //5
//occurrences[1] = 2, occurrences[2] = 2, ...
cout << occurrences[1] << endl; //2
return 0;
}
Забележете како, на почетокот на програмата, користиме #include <unordered_set> и #include <unordered_map>. Без тие наредби, не можеме да ги користиме овие контејнери - кои, како што споменавме, во позадина користат хеш табели за чување и ажурирање на вредности.
За време на натпревари (доколку учествувате на нив), подобро е да користите set<> и map<>, бидејќи операциите кај нив (гарантирано) имаат логаритамска временска сложеност O(logN). Кај хеш табелите, иако во просек имаме константна сложеност O(1), сепак, поради начинот на кој се организирани елементите во структурата, можно е да се состават податоци каде што сложеноста ќе биде O(N), што е неприфатливо. Имено, составувачите на задачи за време на натпревари (може да) знаат како да направат точно вакви тест податоци. Затоа, доколку вашето решение би функционирало доволно ефикасно со set<> или map<>, користете ги тие контејнери.
Подредување на елементи по друг критериум
Во едно од претходните предавања за програмскиот јазик C++, се запознавме со неколку алгоритми кои може да се применуваат на разни податочни структури. Еден од нив беше алгоритамот кој ни овозможува да ги подредиме елементите кај една низа со динамичка големина sort.
Притоа, елементите се подредуваат од најмал до најголем (доколку се работи за реални или цели броеви), или алфабетски (за стрингови). Под алфабетски, подразбираме подредување какво што се наоѓа во телефонски именик, или кај речник – каде што зборовите кои почнуваат на A се среќаваат први, итн. Притоа, за подредување на стрингови, треба да знаеме дека сите зборови кои почнуваат на голема буква ќе дојдат пред сите зборови кои почнуваат со мала буква. Едноставно, ова е принципот по кој ќе се подредат елементите. Така, ако ја имаме следната низа со динамичка големина:
vector<string> names = { "beta", "alpha", "Delta", "Sigma" }
по подредувањето, ќе го добиеме следниот распоред: {“Delta”, “Sigma”, “alpha”, “beta”}, каде сите зборови со голема буква се точно подредени меѓусебно (“Delta” доаѓа пред “Sigma”), и сите зборови со мала буква се точно подредени. Сепак, поради фактот што сите големи букви се поставени пред сите мали букви, подредувањето можеби не е онакво какво што очекуваме.
Но, во C++, постои начин да дефинираме како сакаме елементите да бидат подредени. До C++11, тоа наједноставно се правеше со креирање на нова функција, на следниот начин. Притоа, тука го користиме фактот дека, кај string, слично како и кај vector<>, можеме директно (со помош на for) да ги менуваме вредностите на елементите (кои во случајот се знаци).
Програма 5.4
//koristi C++11 - http://mendo.mk/Lecture.do?id=26
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int compare_lowercase(string a, string b)
{
string lowercase_a = a;
for(char &ch : lowercase_a)
ch = tolower(ch);
string lowercase_b = b;
for(char &ch : lowercase_b)
ch = tolower(ch);
return (lowercase_a < lowercase_b);
}
int main()
{
vector<string> names = { "beta", "alpha", "Delta", "Sigma" };
sort(names.begin(), names.end(), compare_lowercase);
for (auto name : names)
{
cout << name << endl;
}
return 0;
}
Притоа, во програмата дадена погоре, имаме функција compare_lowercase, која прави копии од стринговите кои и доаѓаат како аргументи (за полесно читање на кодот). Поради тоа, во lowercase_a се чува копија од a, но составена само од мали букви. Слично правиме и со lowercase_b. За sort да функционира како што треба, нашата функција compare_lowercase треба да ги спореди двата аргументи и да врати вредност која означува дали елементите се во точен редослед. Со други зборови, нашата функција враќа true, доколку a треба да дојде пред b, што проверуваме преку споредба на нивните верзии составени од мали букви (lowercase_a < lowercase_b).
За крај, да видиме како ќе изгледа оваа програма, доколку сакаме истата да ја напишеме во C++11. Имено, тука, нема потреба да правиме нова функција, туку самата споредба можеме да ја направиме директно каде што го повикуваме алгоритамот за подредување sort, со т.н. ламбда изрази. Тоа ќе изгледа вака:
Извадок 5.1
//koristi C++11 - http://mendo.mk/Lecture.do?id=26
vector<string> names = { "beta", "alpha", "Delta", "Sigma" };
sort(names.begin(), names.end(), [&] (string a, string b) -> bool
{
string lowercase_a = a;
for(char &ch : lowercase_a)
ch = tolower(ch);
string lowercase_b = b;
for(char &ch : lowercase_b)
ch = tolower(ch);
return (lowercase_a < lowercase_b);
});
По мое убедување, ова сеуште не изгледа премногу едноставно и убаво во C++, особено кога имаме сложени функции за споредба. Поради тоа, во овие предавања, многу ретко ќе ги користиме ламбда изразите. Во иднина, верувам дека во некоја од поновите верзии на C++, ова ќе делува многу поедноставно. Сепак, ламбда изразите водат до пократок код. Засега, секој од вас може да одлучи дали повеќе му се допаѓа да дефинира сопствена функција погоре, или да користи ваков израз за дефинирање на самата споредба веднаш во делот каде што ќе ги повикува алгоритмите како sort. Некои програмери ги користат ламбда изразите често, а некои ги избегнуваат.
За крај на овој дел, забележете дека, најчесто, ќе пишувате многу поедноставни функции за споредба - во една или две линии. Во ова предавање, сакав да искористам конкретна задача каде што се бара подредување на стрингови кои можат да содржат и големи и мали букви, бидејќи е тоа интересен и предизвикувачки проблем сам по себе. За споредба, ова е се што треба да запишете за да подредите броеви во опаѓачки редослед (од најголем кон најмал):
Извадок 5.2
vector<int> numbers = {1, 5, 7, 2, 6};
sort(numbers.begin(), numbers.end(), [&] (int a, int b) -> bool
{
return (a > b);
});
По извршување на овој дел, numbers ќе изгледа вака: {7, 6, 5, 2, 1}. Како уште еден пример, ова е се што треба да направите за да подредите низа од стрингови по нивната должина (така што стринговите кои имаат најмалку знаци ќе бидат први):
Извадок 5.3
vector<string> names = {"marko", "ema", "igor"};
sort(names.begin(), names.end(), [&] (string a, string b) -> bool
{
return (a.size() < b.size());
});
По подредувањето на елементите, ќе добиеме {“ema”, “igor”, “marko”}, бидејќи “ema” е составена од 3 знаци, “igor” од 4 знаци, додека “marko” од 5 знаци.
Заменување на повеќе #include директиви
Во сите програми кои ги напишавме погоре, моравме да додадеме повеќе #include <...> директиви за да може да користиме разни податочни структури, алгоритми и слично. Интересно, сите овие програми ќе функционираат и доколку ги замениме сите #include <...> директиви со само една: #include <bits/stdc++.h>. На пример, ова е валидна C++ програма:
Програма 5.5
//koristi C++11 - http://mendo.mk/Lecture.do?id=26
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> v = {10, 5, 7};
sort(v.begin(), v.end());
for(auto number : v)
{
cout << number << endl;
}
return 0;
}
Сепак, бидејќи #include <bits/stdc++.h> не е дел од C++ стандардот, постои можност за добивање на грешки при преведување на програмите - особено доколку користиме различна развојна околина или компајлер. Поради ова, во наредните предавања, ретко ќе го користиме овој “трик”. Сепак, истиот го споменуваме бидејќи е корисен при пишување на едноставни програми кои сакате да ги извршувате на вашиот компјутер, како и за време на натпревар (каде времето ни е ограничено). Изборот е на вас.