Знову про STL

Ця добірка коротких заміток щодо контейнерів C++ з'явилася як результат прохання підготувати для початківців колег програмістів стиснене огляд STL. Навіщо це було потрібно, коли з цього предмета є оригінальна документація і багато цілих окремих книг, з яких як мінімум 5-6 чудової якості існують в перекладах і на російську мову?
Але сенс, однак, є і він ось у чому:

  • Всі книги видані в кінці 90-х — початку 2000-х. Більш пізні стандарти мови C++ (аж до C++11) вводять нові синтаксичні конструкції, які застосуванні з STL дають крос-ефект… з дуже цікавою інтерференцією. Це часто дозволяє використовувати конструкції STL з набагато більшою легкістю.
  • Книги зазвичай описують предмет надто деталізовано (це добре для студентів, але забагато для програмістів, нехай навіть рівня джуніорів, яким, після інших мов, наприклад, потрібно тільки базове ознайомлення). Оригінальна документація, навпаки, напхана формальними синтаксичними визначеннями (це чудово в якості довідника під рукою, але забагато для знайомства). Справжні замітки, повністю уникаючи формальних визначень, будуються навколо прикладів використання, в більшій частині зрозумілих програмісту навіть без яких-небудь додаткових пояснень.
  • Контингент, для якого спочатку готувалися тексти, крім іншого в значній мірі орієнтований на чисельні математичні методи, обробку даних в потоці, на що не розраховані наявні публікації. Мені теж ближче такий ухил, і такий акцент буде помітний у прикладах, на яких побудовано опис.
З-за вимог обов'язкової однотипності об'єктів в контейнерах, їх можна було б з уточненням називати регулярними контейнерами, це багато прояснює (не робиться таке уточнення тільки тому, що і так всім зрозуміло про що мова). Мова, звичайно, йде про контейнерах STL, але і традиційний масив C/C++ — це такий же регулярний контейнер, і вони будуть фігурувати в тексті і прикладах. (Структури, а ще більш загально, класи з полями даних теж є контейнерами, але їх ніяк не назвеш регулярними.)

Хотілося б сподіватися, що ці замітки виявляться корисними комусь із освоюють STL, спростять цей процес розуміння. А пропозиції і зауваження, коли вони будуть по суті, від тих читачів, хто вже профі в C++, дозволять покращити ці тексти на майбутнє, коли вони зможуть знадобитися ще комусь.

Масиви зі статичної та динамічної розмірністю
Але починати огляд контейнерів STL потрібно від традиційних масивів, оскільки перші є логічним розвитком останніх. Масиви — одна з найбільш використовуваних форм організацій даних, і історично одна з найперших форм структурування, що з'явилися в мовах програмування (кінця 50-х років), раніше появи в мовах структур і будь-яких інших способів агрегації. Масив — це подання набору послідовних однотипних елементів, і тим він органічний і для внутрішнього подання для машинних обчислень на рівні команд. Принципово важливим у такому визначенні є 2 моменти, які для масиву повинні обов'язково виконуватися:

  1. Кожен елемент масиву можна указати номер його розташування в послідовності подібних йому елементів.
  2. Всі елементи масиву повинні обов'язково бути однотипними. Усім знайомі і зрозумілі найпростіші визначення, наприклад, цілих масивів: int array[ 100 ]. Але це зовсім не означає, що в масиви можуть організовуватися тільки найпростіші вбудовані типи мови C++ — масив можуть організовуватися об'єкти-змінні будь-якого складеного типу (класу) і будь-якого ступеня складності.
Єдиним обмеженням є те, що елементи одного масиву повинні бути одного типу. Наприклад, ось так може описуватися студентська група в обліковій програмі деканату:
class student {
...
}
student group[ 30 ];

До цього вкрай важливого обставині — типи елементів масиву — ми ще повернемося в подальшому.

Ще з часів ранніх мов програмування (FORTRAN та ін), на масиви накладалося дуже сильне обмеження: розмір масиву повинен визначатися тільки цілочисельний константою, значення якої повинно бути визначена на момент компіляції коду. Те ж саме обмеження збереглося і в мові C, який став прабатьком C++. Наприклад:
#define size 100
double array[ size ];

В C++ (в класичному, крім стандартів останніх років!) це обмеження трохи ослаблено до того, що розмір масиву може бути ціла константою, значення якої може бути обчислено на момент компіляції коду. Наприклад, так:
#include < iostream> 
using namespace std; 

float array[ (int)( 10. * 10. ) + 2 ]; 

int main( void ) { 
cout << "array size = " 
<< sizeof( array ) / sizeof( array[ 0 ] ) 
<< endl; 
} 

$ ./siz1 
array size = 102 

У всіх таких випадках, після визначення масиву розмір його фіксується і ми не зможемо ніяким збільшити розмір (якщо, наприклад, в ході обчислень виявиться, що нам не вистачає цього розміру). Таким чином певні масиви називаються масивами статично оголошеним (в момент написання коду) розміром.

Примітка: З-за того, що всі елементи масиву розташовуються послідовно (1-е правило з названих вище), для обчислення розміру масиву (в області його видимості) можна використовувати показаний в прикладі трюк: розмір масиву дорівнює довжині всього масиву, поділеній на довжину будь-якого його елементу (оскільки всі вони однакові за типом).

Може здатися, що по-іншому визначаються масиви без зазначення розміру, але зі списком инициализирующих значень:
float array[] = { 1., 2., 3., 4., 5. };

Але це не так! Просто тут константне значення розміру объявляемого масиву витягується зі списку значень, і одно, у наведеному прикладі 5.

Основним способом створити масив, у класичних C і C++, c розміром N елементів, обчислюється в момент створити масиву (на етапі виконання) — це був спосіб динамічного розміщення масиву. Яке C і C++ робиться, відповідно:
double *array = (double*)calloc( N, sizeof( double ) ); // C
double *array = new double[ N ]; // а це C++

Наприклад, так:
#include < iostream> 
#include <cmath> 
using namespace std; 

int main( void ) { 
int size = (int)( sin( M_PI / 2 ) * pow( 2, 10 ) ); 
float *array = new float[ size ]; 
cout << "array size = " << size << endl; 
delete [] array; 
} 

$ ./iz2 
array size = 1024 

Примітка: Динамічне розміщення масиву є основним способом, хоча існують і деякі інші способи, такі як alloca() C API, або включення в розширювані структури масивів нульової довжини (розширення компілятора GCC) або які прийшли їм на зміну масивів зі змінними границями (розширення стандарту C99):
typedef struct vararr {
// int n, data[ 0 ]; // масив нульової довжини - розширення GCC
int n, data[]; // масив з змінними границями - розширення C99
} vararr_t;

Але всі ці способи, якщо судити по частоті їх використання — це тільки екзотика в порівнянні з динамічним розміщенням. А їх різноманіття в різних варіантах — тільки вказівка на те, що статичність розміру масиву це сильний обмежуючий фактор, і все це пошуки зняття цього обмеження.

Найпізніші стандарти (C99, C++11) внесли розширення, які допускають створення локальних масивів у функціях з розмірами, обчислюваними на етапі виконання при вході у функцію (при таких умовах масив буде виділено в стеку функції). Це вже досить суттєво, у випадках коли ми не можемо знати наперед розмір оброблюваних даних (стандарт C99 називає це: VLA — variable-length array). В якості прикладу подивимося задачу знаходження всіх простих чисел, не переважаючих N (решето Ератосфена), де N задається параметром командного рядку при запуску програми:
#include < iostream> 
#include < cstdlib> 
using namespace std; 

int main( int argc, char **argv ) { 
unsigned k, j, n; // верхня межа 
bool a[ n = atoi( argv[ 1 ] ) + 1 ]; 
a[ 0 ] = a[ 1 ] = false; 
for( k = 2; k < n; k++ ) 
a[ k ] = true; 
for( k = 2; k < n; k++ ) 
for( j = k + k; j < n; j += k ) // викреслювання всіх чисел кратних k 
a[ j ] = false; 
const int line = 10; 
for( k = 0, j = 0; k < n; k++ ) 
if( a[ k ] ) { 
cout << k << "\t"; 
if( 0 == ++j % line ) cout << endl; 
} 
if( j % line != 0 ) cout << endl; 
return 0; 
}

Цей код ми вже зобов'язані компілювати з зазначенням стандарту C++ 2011 року (опціями чи компілятора, або властивостями зібраного проекту):
$ g++ -Wall -std=c++11 -O3 erastof.cc -o erastof 
$ ./erastof 300 
2 3 5 7 11 13 17 19 23 29 
31 37 41 43 47 53 59 61 67 71 
73 79 83 89 97 101 103 107 109 113 
127 131 137 139 149 151 157 163 167 173 
179 181 191 193 197 199 211 223 227 229 
233 239 241 251 257 263 269 271 277 281 
283 293 

Але навіть після всіх розширень, найпростіший масив, як форма організації набору об'єктів, виявляється недостатньо гнучким, головні з обмежуючих факторів якого:

  • Як би не визначався розмір масиву (константою або обчисленням точці визначення) в подальшому збільшити цей розмір неможливо (якщо не вгадали заздалегідь потрібний розмір, або не заклали достатній запас).
  • За правилами C/C++ при виклику функцій замість масиву, як параметр функції передається вказівник на його початок (адреса 1-го елемента). Це дозволяє значно підвищити ефективність багатьох обчислювальних алгоритмів, але при цьому повністю втрачається інформація про розмір масив (її необхідно, як варіант) передавати окремим параметром. Наприклад, якщо б ми хотіли формувати решето Ератосфена не у функції main(), а в окремій функції, то ми повинні були формувати її як виклик erastof ( a, n ).
  • Багато інтуїтивно найпростіші операції над масивами викликають складності, такі, наприклад, як: в 15-ти елементному масиві елемент під номером 10 вставити між елементами 2 і 3. При цьому а). всі елементи з 3 по 9 потрібно копіювати на одну позицію вправо, б). робити це можна тільки в низхідному порядку від 9 до 3 і у). за всіма індексами цих операцій необхідно стежити в ручному режимі.
Для того, щоб легше сприймати механізми доступу в контейнерах STL, корисно попередньо згадати як це робиться до елементів масивів. Вибір (для читання або запису) довільного елемента масиву (назвемо його умовно arr[ ]) може вибиратися двома механізмами: а). операцією індексації — arr[ n ], або б). за вказівником, отсчитываемому від початку масиву — *( &arr[ 0 ] + n ). Процес переміщення курсору вздовж масиву, в ході доступу до його різних елементів, може бути названий ітерацією, а покажчик, що використовується в цій якості — ітератором. Таким чином, доступ до елементів будь-яких масивів може здійснюватися або за індексом, або за ітератора.

Стандарт C++11 доповнює операцію циклічного доступу до елементів масиву нової синтаксичною формою, на зразок того, як це робить алгоритм for_each() з STL, яка (з використанням виводимості типів з того ж C++11) може виглядати вельми незвично для традиційного синтаксису:
for( auto i : arr ) . . .
for( auto &i : arr ) . . . // або так

Наступний приклад показує всі ці можливості одночасно:
#include < iostream> 
using namespace std; 

double arr[] = { 1, 2, 3, 4, 5, 6, 8, 9 }; 
const unsigned n = sizeof( arr ) / sizeof( arr[ 0 ] ); 

int main( void ) { 
for( unsigned i = 0; i < n; i++ ) cout << arr[ i ] << " "; 
cout << endl; 
for( double* i = arr; i - arr < (int)n; i++ ) cout << i << " "; 
cout << endl; 
for( auto i : arr ) cout << i << " "; 
cout << endl; 
for( auto &i : arr ) i = i * i; 
for( double i : arr ) cout << i << " "; 
cout << endl; 
} 

Зверніть увагу на вираз for( auto &i: arr ), коли використовується посилання на елементи масиву, що представляє лівосторонній вираз, що дозволяє не тільки читати, але і записувати значення в елементи масиву:
$ g++ -Wall -std=c++11 -O3 siz3.cc -o siz3 
$ ./siz3 
1 2 3 4 5 6 8 9 
1 2 3 4 5 6 8 9 
1 2 3 4 5 6 8 9 
1 4 9 16 25 36 64 81 

Постскриптум: Природно, щоб те, про що розказано тут, а ще більше в наступних частинах, не тільки працювала, але хоча б навіть елементарно компилировалось:

  • При компіляції прикладів потрібно явно вказувати проходження стандарту C++11: або опцією командного рядка (GCC і Clang — як показано у тексті), або у властивостях компилируемого проекту (Code::Blocks). Неявно використання конструкцій C++11 ще не підтримуються.
  • Необхідно Щоб ваш компілятор елементарно знав і підтримував стандарт C++11, тобто компілятор (або IDE в складі якої він був пізніше… ну, скажімо, 2013 року.
Останньому умові повністю задовольняють всі знаходяться в побуті версії GCC або Clang в Linux. На прохання читачів, їх наводять приклади коду (тут і далі) були перевірені у віртуальній машині Windows 7, і в реалізаціях Visual Sudio 2013 і Code::Blocks 2013. При заявленій підтримки C++11 (з застереженнями на «неповноту») в Visual Sudio 2013, підтримка там, якщо і є, то дуже обмежена, і компілятор непридатний для експериментів з показаними прикладами. А ось Code::Blocks (з MinGW) виявився цілком придатним (хоча, на моє тверде переконання, вивчати мови C++, а особливо C, потрібно тільки в середовищі POSIX / Linux, після чого в будь-якому середовищі… але це суто особисте переконання, яке можна не брати до уваги).

З такого побіжного огляду масивів як контейнерів зрозуміло, що потреби практики часто вимагають більшого, що і створило потребу в контейнерах STL (Standard Template Library) як засіб розширення функціональності масивів.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.