STL

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Съдържание[редактиране | edit source]

Контейнери:

Контейнер Описание
Масиви / Индексирани списъци - подредени множества
vector динамичен масив, като C масив (т.е., с възможност за свободен достъп) способен да расте и намалява динамично, когато се поставя или премахва обект. Поставянето и премахването на обект в края на вектора отнема константно време, а в средата линейно.
list двойно индексиран списък; елементите не се запомнят в последователни места памет. Противоположно на vector представяне. Бавно търсене и достъп (линейно време), но след като позицията е намерена включването и изключването отнемат константно време.
deque вектор с поставяне/извличане в началото или края за амортизирано константно време, няма гаранция за валидността на итератор след altering дека.
Асоциативен масив/Асоциативни контейнери - неподредени множества
set сортирано множество;поставянето/премахването на елементи в множеството, използва принципа на черно-бяло дърво да поддържа дълбочина от log2(n). set <int> a , като сортира по големина. Може да се променя чрез добавяне на фунция.
multiset същото като set, но се позволява дублирането на елементи.
map a sorted associative array; allows mapping from one data item (a key) to another (a value). Type of key must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree.
multimap същото като map, само че е позволено дублирането на ключове.
hash_set

hash_multiset
hash_map
hash_multimap

подобно на set, multiset, map, or multimap, but implemented using a hash table; keys are not sorted, but a hash function must exist for key type. These containers are not part of the C++ Standard Library, but are included in SGI's STL extensions, and are included in common libraries such as the GNU C++ Library in the __gnu_cxx namespace. These are scheduled to be added to the C++ standard as part of TR1, with the slightly different names of unordered_set, unordered_multiset, unordered_map and unordered_multimap.
Други видове контейнери
bitset съхранява серия битове подобно на vector със зададена големина от тип bool.
valarray another C-like array like vector, but is designed for high speed numerics at the expense of some programming ease and general purpose use. It has many features that make it ideally suited for use with vector processors in traditional vector supercomputers and SIMD units in consumer-level scalar processors, and also ease vector mathematics programming even in scalar computers.

Итератори:

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

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

  • Input (входни, могат да бъдат използвани само за четене на последователност от стойности)
  • Output (изходни, могат да бъдат ползвани само за извеждане на последователност от стойностти)
  • Forward (напред, могат да бъдат използвани за четене и извеждане, движението е само напред)
  • Bidirectional (двупосочни, като Forward, но е позволено движението назад)
  • Random Access итератори (със свободен достъп, могат да се движат свободно с произволен брой стъпки в една операция).

Възможно е bidirectional итератори да вършат същото като random access итератори. Например преместването десет стъпки напред може да бъде представено като десет премествания с една стъпка напред. Въпреки това random access итераторите имат по-голямо приложение. Например един vector може да има random access итератор, но един list само bidirectional итератор.

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

This generality also comes at a price at times. For example, performing a search on an associative container such as a map or set can be much slower using iterators than by calling member functions offered by the container itself. This is because an associative container's methods can take advantage of knowledge of the internal structure, which is opaque to algorithms using iterators.

Алгоритми:

Функтори:

Примери[редактиране | edit source]

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

 #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[редактиране | edit source]