STL

STL (съкр. от Standard Template Library – Стандартна библиотека с шаблони)
е софтуерна библиотека, отчасти включена в стандартната библиотека на езика С++.
STL предоставя удобен начин за работа с контейнери, итератори, алгоритми и функтори. STL съдържа готови класове за работа с основни структури от данни
(стек, опашка, дек, списък, граф и др.)

Съдържание

[редактиране | редактиране на кода]

Контейнери:

Контейнер Описание
Масиви / Индексирани списъци – подредени множества
vector Динамичен масив, като масивите на C (т.е. с възможност за свободен достъп), способен да расте и намалява по време на изпълнение – когато се поставя или премахва обект. Поставянето и премахването на обект в края на вектора отнема константно време, а в средата – линейно.
list Двойносвързан списък; елементите не се запомнят в последователни клетки от паметта. Алтернатива на vector. Търсенето и достъпът до елемент по даден индекс са бавни (изискват линейно време), но щом позицията бъде намерена, включването и изключването отнемат константно време.
deque Опашка с два края, т.е. елементи може да се поставят и извличат и от началото, и от края за амортизирано константно време. Няма гаранция за валидността на итератор след промяна на дека.
Асоциативен масив/Асоциативни контейнери – неподредени множества
set Сортирано множество. Поставянето и премахването на елементи в множеството използват принципа на черно-бяло дърво, за да поддържат логаритмична времева сложност.
multiset Мултимножество. Подобно е на обикновеното множество (set), обаче позволява дублирането на елементи.
map Сортиран асоциативен масив. Запаметява наредени двойки (ключ, стойност). Типът на ключа трябва да притежава оператор за сравнение < или дефинирана от програмиста функция за сравняване. Сортираният асоциативен масив е реализиран с помощта на балансирано подреждащо двоично дърво.
multimap Същото като map, само че е позволено дублирането на ключове.
hash_set

hash_multiset
hash_map
hash_multimap

Тези са подобни на set, multiset, map и multimap,
обаче са реализирани с помощта на хеш-таблица.
Ключовете не са сортирани; вместо това
трябва да съществува хеш-функция за типа на ключовете.
Тези контейнери не са част от C++ Standard Library,
но са включени в разширенията на SGI's STL
и в популярни библиотеки като GNU C++ Library
(в пространството от имена __gnu_cxx).
Запланувано е добавянето им към стандарта на C++
като част от TR1, само че с леко променени имена:
unordered_set, unordered_multiset, unordered_map и unordered_multimap.
Други видове контейнери
bitset Пази редица от битове подобно на vector със зададена големина от тип bool.
valarray Подобен на vector и на масивите в езика C, но пригоден
специално за бързо смятане. За сметка на това
е по-труден за използване и с по-тясна област на приложение.
Идеален при работа с векторни процесори в традиционните векторни суперкомтри и SIMD устройствата в скаларните процесори от потребителско ниво. Улеснява смятането с математически вектори даже при работа със скаларни компютри.

Итератори:

Итераторите са подобни на указателите.

Има пет типа итератори:

  • Входни (input) – могат да бъдат използвани само за четене на последователност от стойности.
  • Изходни (output) – могат да бъдат използвани само за писане на последователност от стойности.
  • Еднопосочни (forward) – могат да бъдат използвани за четене и писане; движението е само напред.
  • Двупосочни (bidirectional) – могат да бъдат използвани за четене и писане; разрешават движение и напред, и назад.
  • Итератори със свободен достъп (random access) – разрешават достъп до произволен елемент.

Двупосочните итератори имат същите възможности като итераторите със свободен достъп. Например преместването десет стъпки напред може да бъде представено като десет премествания с една стъпка напред. В общия случай обаче итераторите със свободен достъп работят по-бързо от двупосочните. Например един vector може да има итератор със свободен достъп, но един списък (list) може да има само двупосочен итератор.

Итераторите са главното средство на библиотеката STL да бъде всеобхватна. Например един алгоритъм за обръщане на редица може да бъде програмиран с помощта на двупосочни итератори и след това да бъде използван за контейнерите list, vector и deque. Създаден от потребителя контейнер трябва само да предостави итератор (един от петте вида) и всички алгоритми в STL ще могат да бъдат използвани за този контейнер.

Тази универсалност си има своята цена. Например търсенето в асоциативен контейнер, като map или set, може да бъде много по-бавно, ако се използват итератори, отколкото ако се викат методите на самия контейнер. Методите на контейнера познават вътрешната структура на контейнера и могат да се възползват от това. Тази информация е недостъпна за алгоритмите, използващи итератори.

Алгоритми:

Функтори:

Примери

[редактиране | редактиране на кода]

Сортиране на елементите на вектор: 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
  vector<int>v(5);
  for(int i=0;i<v.size();i++)
    v.push_back(i+1);

  cout<<"Големината на вектора е: "<<v.size()<<endl;
  cout<<"Елементите на вектора в обратен ред: ";

  while(!v.empty()) {
    cout<<v.back()<<" ";
    v.pop_back();
  }

  v.push_back(3);
  v.push_back(2);
  v.push_back(7);
  v.push_back(5);
  v.push_back(9);

  sort(v.begin(),v.end());
  cout<<"Елементите в нарастващ ред:"<<endl;

  while(!v.empty()) {
    cout<<v.front()<<" ";
    v.erase(v.begin());
  }

  system("pause");
  return 0;
}

Още за STL

[редактиране | редактиране на кода]