29.02.2016 07:09
Olej 22 10400 Источник
Эта подборка коротких заметок относительно контейнеров 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; 
} 


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

Комментарии (22)


  1. OlegKozlov
    29.02.2016 10:53
    #8786867

    Серьёзный заход. Тут на выходе должна книжка не меньше мейерсовской должна получиться.


  1. snizovtsev
    29.02.2016 11:40
    #8786921
    +4

    Использование VLA считается не очень хорошей практикой, особенно в multithread приложениях. Помимо очевидного роста стека (который не рассчитан на то, чтобы хранить большие данные), мы лишаемся возможности хорошо обработать ошибку его переполнения, вероятность появления которой сильно возрастает.

    Так что пример с решетом Эратосфена на VLA я бы назвал антипаттерном. Если нужен большой массив, то время потраченное на malloc будет все равно мало по сравнению со временем, которое потребуется для его заполнения.

    Так что мой рецепт: используйте VLA только там, где он действительно дает ускорение, на этапе оптимизаций. Скорее всего это будут маленькие временные массивы для строк или передачи аргументов в другую функцию.


  1. gbg
    29.02.2016 12:12
    #8786955
    +12

    И немедленно сами себя успешно срезали:

    • засунув размер массива в int.
    • наделав кучу бредовых индексных переменных вне циклов
    • насовав в учебный материал сложносочиненные конструкции из присваиваний-с-одновременным использованием
    • проигнорировав даже элементарные проверки входных параметров
    • используя return 0; в main иногда. По собственному желанию, так сказать.
    • итерируя массив всякой ерундой вроде unsigned (хорошо еще не int), когда для этого есть size_t
    • используя в коде на C++ преобразования типов в стиле C.

    И лично от меня (вкусовщина чистейшая):

    • кодстайл "экономлю строки — не ставлю скобки на однооператорные блоки" — плодит таких же экономщиков. А потом они плодят идиотские баги.

    Я лучше Майерса почитаю.


    1. Olej
      01.03.2016 20:33
      #8788639
      -1

      Я лучше Майерса почитаю.

      Конечно лучше!
      Если вы это не сделаи 14 лет назад, то сейчас — самое время почитать.


      1. Chaos_Optima
        04.03.2016 11:48
        #8793695
        +2

        Майерс и про программирование с использованием С++11 тоже пишет, или вы только старое издание видели?


        1. Olej
          04.03.2016 17:40
          #8794303
          -3

          При чём здесь Майерс и его издания. Майерс — замечательная книжка…
          Но господин высказал свою сокровенную мечту почитать Майерса, чего он не сделал тогда 14 лет назад, когда он только был издан… а всякая мечта заслуживает поощрения и поддержки, чего я ему от всей души и пожелал.

          А если о Маерсе изволите, то — замечательная книжка, ещё раз, но для начального знакомства, понимания на качественном уровне, "на пальцах" — не годится.


          1. encyclopedist
            04.03.2016 21:23
            #8794561
            +3

            Вам намекают, что у Майерса не одна книжка. Новая книжка, которая затрагивает особенности C++11 вышла только в декабре 2014. Её прочитать 14 лет назад при всём желании было нельзя (и это не просто обновление старой книжки, а совершенно новый материал, не повторяющий старые книги).


    1. Olej
      07.03.2016 19:48
      #8796459
      -3

      И немедленно

      Комментарии к этому юношесткому… срачу и задору ;-) — я полнотью выписал в следующей части чтоб не повторяться.


  1. monah_tuk
    29.02.2016 12:43
    #8787001
    +3

    Самые поздние стандарты (C99, C++11)

    Да как бы и C11 уже есть. Причём некоторые вещи он, в отличии от C99 сделал опциональными. Например VLA.


    1. Olej
      09.03.2016 15:59
      #8799119
      -3

      Да как бы и C11 уже есть. Причём некоторые вещи он,

      Я говорю о практике применения. Вы говорите об академическом теоретизировании.
      У вас есть под рукой компилятор, полностью поддерживающий C11?
      Вы часто используете новинки C11, например, макросы для создания комплексных чисел?
      Или… вы, может, про такое и не слышали, а стандарт упомнили для красного словца?


    1. Olej
      09.03.2016 16:12
      #8799149
      -3

      Причём некоторые вещи он, в отличии от C99 сделал опциональными. Например VLA.

      Рассуждениями про "опциональность" в стандарте от души повеселили, спасибо…
      Это напоминает то, как дети начинают повторять за взрослыми слова и жесты, играют "в больничку" и тычут сломинкой в жопу...

      Опциональность в стандарте — это для разработчиков компилятора.
      Вы разрабатываете компилятор C?
      Вы в состоянии разрабатывать компилятор C?
      Вы знаете компилятор C для реальны проектов кроме GCC или Clang (ну, ещё для полноты картины: Sun компилятор из SolarisStudio и Portable C Compiler, использовавшийся в NetBSD и OpenBSD).
      Какая опциональность?


      1. encyclopedist
        09.03.2016 16:41
        #8799221
        +4

        Очевидно, с эмбеддед вы совершенно незнакомы. А там просто зоопарк компиляторов, с очень разным уровнем поддержки стандартов. И про Keil, IAR, не говоря уж про какой-нибудь TI Code Composer вы не слышали.


        1. Olej
          09.03.2016 17:10
          #8799257
          -4

          Я безумно рад, что наши доморощенные энциклопедисты обладают такой широтой эрудиии, что слышали и и готовы обсуждать обо всём… даже об embedded:

          Наш пострел — везде поспел.

          Но это очень и очень частные вещи, которые ну никак не вписываются в контекст обсуждений на Хабрахабр… для массовой гопоты.

          Так что реплика не в зачот — пробуй исчо! ;-)


  1. Hokum
    29.02.2016 13:31
    #8787063
    +3

    Задумка хорошая, но, мне кажется, Вы ушли в сторону от идеи сжатого обзора STL.

    Основные проблемы обычных массивов, как я их вижу:

    1. Если они создаются динамически, то нужно очищать память, а на стеке большой массив не выделишь.

    2. Неудобство передачи массивов в функции.
    приходится передавать дополнительным параметром размер массива:

    void foo(int *arr, size_t size)
{
//... здесь sizeof(arr) вернет размер указателя
}

    или писать шаблон принимающий массив по ссылке

    template<typename T, size_t N>
void foo(T (&arr)[N])
{
//... здесь  sizeof(arr) вернет размер памяти выделенной для массива
}

    И нельзя смешивать передачу массива по ссылке и передачу массива по указателю. Т.е. если передали массив по указателю, то передать его уже куда-нибудь как ссылку на массив не получится (поправте меня, если это можно сделать).


  1. encyclopedist
    29.02.2016 13:32
    #8787065
    +4

    В С++11 VLA отсутствуют. Это расширение GCC. Если скомпилировать с -Wall -Wextra -pedantic (к чему нужно с первых уроков приучать студентов), то GCC прямо в этом признаётся:

    /tmp/gcc-explorer-compiler116129-74-h99924/example.cpp: In function 'int main(int, char**)':
7 : warning: ISO C++ forbids variable length array 'a' [-Wvla]
bool a[ n = atoi( argv[ 1 ] ) + 1 ];
^


    1. Gorthauer87
      29.02.2016 14:13
      #8787125
      +2

      Для студентов я бы ещё -Werror добавил. Программки то маленькие, можно и переписать себе позволить всё.


      1. GamePad64
        29.02.2016 18:31
        #8787393
        +2

        Вообще, да. Чем строже язык, тем меньше шансов выстрелить себе в ногу. Ещё с детства нужно приучать к сборкам с -fsanitize=...


    1. Olej
      09.03.2016 15:44
      #8799077
      -5

      В С++11 VLA отсутствуют. Это расширение GCC.

      VLA — это никак не расширение GCC. VLA — это расширение введенное стандартом языка C99.
      6.19 Arrays of Variable Length

      Variable-length automatic arrays are allowed in ISO C99, and as an extension GCC accepts them in C90 mode and in C++.

      P.S. Всем, кто претендует на звание доморощенных энциклопедистов, хорошо бы научиться различать.

      Ну и далее… Answer

      This is variable length arrays or VLA which is a C99 feature but gcc and clang support it as an extension in C++ while Visual Studio does not.
      …
      Not to say that extensions are bad, the Linux kernel depends on many gcc extensions, so they can be useful in certain contexts.


      1. encyclopedist
        09.03.2016 16:02
        #8799131
        +4

        gcc and clang support it as an extension in C++
        То есть вы пытались опровергнуть мои слова, и сами же подтвердили их.

        Ещё раз, поскольку вы не поняли:

        — В языке C, VLA — это стандартная возможность, введённая в C99. Кстати, в C11 VLA сделаны опциональными, так что в C11 ваш код тоже может вполне легально отказаться работать.
        — В языке С++, никаких VLA нет. Согласно стандарту этот код не должен компилироваться. И то что они таки работают в GCC — это частная инициатива разработчиков GCC. Это расширение.

        PS Да, и вспомните что я вам писал в личку. Я изменил своё мнение о вас из-за вашего поведения в комментариях и поставил вам минус.


        1. Olej
          09.03.2016 17:22
          #8799279
          -4

          введённая в C99

          Так в C99, или в GCC, как в вашем предыдущем утверждении?
          Вы уж как-то определитесь.
          Что ж это вы так легко свои позиции сдаёте?

          Кстати, в C11 VLA сделаны опциональными, так что в C11 ваш код тоже может вполне легально отказаться работать.

          Ну как дети малые — повторяете глупости за своим коллегой: опциональным для разработчиков компилятора, а не для кода… и не для вас ;-)

          Это расширение.

          Да. Расширение. Но не только GCC, а всех нормальных существующих компиляторов (ну, VisualStudio мы ж туда относить не станем?).

          Да, и вспомните что я вам писал в личку. Я изменил своё мнение о вас

          Писали вы в личку из трусости — наговорили лишнего, а потом сами сдрейфили… "как бы чего не вышло".
          А на "мнения" ваши — мне искренне класть — как вы и видите.


  1. nickolaym
    01.03.2016 13:40
    #8788131
    +4

    Жёлтый заголовок! Обещали про STL, вместо этого налили кучу воды про голые массивы в сях и плюсах.


    1. Olej
      01.03.2016 15:18
      #8788237
      -3

      Будет вам и белка
      Будет и свисток

      Куда так торопитесь? ;-) Будет вам и STL… жизнь длинная...