Масиви з статичною та динамічною розмірністю. СТЛ Частина 1




Масиви з статичною та динамічною розмірністю, Контейнери C ++ STL , Стандартна бібліотека шаблонівперш, ніж приступати до огляду контейнерних типів бібліотеки STL, розумно освіжити в пам'яті інформацію про організацію масивів C і C ++. Тому що контейнери STL - це деякі альтернативні форми організації колекцій даних, вільні від обмежень масивів.

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

  1. Кожен елемент масиву потрібно вказати номером його розташування в послідовності подібних елементів.

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

Масиви з статичною та динамічною розмірністю, Контейнери C ++ STL , Стандартна бібліотека шаблонів

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

Ще з часів найраніших мов програмування (FORTRAN і ін.), на масиви накладалося сильне обмеження: размер масиву повинен визначатися только целочисленной константою, значення якої повинно бути виразно на момент компіляції код. Те ж саме обмеження збереглося і в мові C, який став прабатьком C ++. Наприклад:

Масиви з статичною та динамічною розмірністю, Контейнери C ++ STL , Стандартна бібліотека шаблонів

В C (в класичному, крім стандартів останніх років!) це обмеження незначно ослаблений до того, що размер масиву може бути целочисленной константою, значення якої може обчислюватися на момент компіляції код. Наприклад, так:

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

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

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

Масиви з статичною та динамічною розмірністю, Контейнери C ++ STL , Стандартна бібліотека шаблонів

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

єдиним способом створити масив, в класичних C і C ++, розміром в N елементів, обчислюваним в момент створення масиву (на етапі виконання) - Це був спосіб динамічного розміщення масиву. Яке в C і C ++ робиться, соответственно:

Наприклад, так:

Масиви з статичною та динамічною розмірністю, Контейнери C ++ STL , Стандартна бібліотека шаблонів

Найбільш пізні стандарти (C99, C ++ 11) внесли розширення, які допускають створення локальних масивів у функціях з розмірами, обчислюваними при вході в функцію. При таких умовах масив буде виділено в стеці функції. Це вже має велике значення, коли ми не можемо знати наперед розмір оброблюваних даних. Як приклад подивимося завдання знаходження всіх простих чисел, що не перевищують N (решето Ератосфена), де N задається при запуску програми.

Цей код ми вже зобов'язані компілювати із зазначенням стандарту C ++ 2011 року (опціями або компілятора, або властивостями зібраного проекту):Масиви з статичною та динамічною розмірністю, Контейнери C ++ STL , Стандартна бібліотека шаблонів

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

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

  • За правилами C / C ++ при виклику функцій замість масиву як параметр замість масиву передається покажчик на його початок (адреса 1-го елемента). Це дозволяє сильно підвищити ефективність багатьох обчислювальних алгоритмів, але при цьому втрачається інформація про розмір масиву, і її необхідно передавати окремим параметром. Наприклад, якби ми хотіли формувати решето Ератосфена не в функції main(), а в окремій функції, то ми повинні були б формувати її виклик як erastof ( a, n ).

  • Багато інтуїтивно найпростіші операції над масивами викликають складності. Наприклад: в 15-ти елементному масиві елемент під номером 10 надо вставити між елементами 2 і 3. При цьому а). всі елементи з 3 по 9 потрібно копіювати на одну позицію вправо, б). робити це можна тільки в низхідному порядку від 9 до 3 і в). за всіма індексами цих операцій необхідно стежити в ручному режимі.

Потреби практики вимагали більшої, що і породило контейнери STL (Standard Template Library).

Нові уроки з програмування:

дата
сторінка
Масиви з статичною та динамічною розмірністю. СТЛ Частина 1
рейтинг
51зірка1зірка1зірка1зірка1зірка
Olej

Про Olej

Стаж практичних програмних розробок близько 40 лет. Викладач міжнародної софтверної компанії Global Logic. Постійний автор публікацій IBM Developer Works. Науковий редактор книжкового видавництва комп'ютерної літератури "Символ-Плюс", Санкт-Петербург.

2 думки про "Масиви з статичною та динамічною розмірністю. СТЛ Частина 1

  1. В C і C ++ існує правило: замість масивів при виклику функцій передається указатель на початок масиву (це склалося років 40-50 тому з міркувань ефективності тих комп'ютерів). Тому при передачі масиву в функцію інформація про його розмір втрачається.
    Традиційно масиви передаються в функцію як 2 параметра: покажчик початку масиву + число його елементів. Наприклад: анулюються FUNC( подвійний обр[], int size ) або недійсними функції( подвійний * обр, int size ).

залишити коментар

Код розміщуйте в тегах: <pre class="lang:C ++ декодуванням:true ">ВАШ КОД</заздалегідь>