Снова про STL29.02.2016 10:33

Эта подборка коротких заметок относительно контейнеров 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  
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  
#include  
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; 
} 


$ ./siz2 
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  
#include  
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  
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) как средстве расширения функциональности массивов.

© Habrahabr.ru