C++ STL кітапханасы: Негізгі алгоритмдер мен құрылымдар
Standard Template Library
C++ STL кітапханасы: алгоритмдер, контейнерлер, функциялар мен итераторлар. Қолдану оңай, кез келген типпен жұмыс істейді. Бағдарламалауды жеңілдетіңіз!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
C++ бағдарламалау тілі үшін бағдарламалық кітапхана.
Software library for the C++ programming language
Стандартты үлгі кітапханасы (STL) – бастапқыда Александр Степанов C++ бағдарламалау тілі үшін жасаған бағдарламалық кітапхана, ол C++ стандартты кітапханасының көптеген бөліктеріне әсер етті. Ол алгоритмдер, контейнерлер, функциялар және итераторлар деп аталатын төрт компоненттен тұрады. STL C++ үшін контейнерлер мен ассоциативтік массивлер сияқты, кез келген кіріктірілген типпен және көшіру және тапсыру сияқты негізгі операцияларды қолдайтын кез келген пайдаланушы анықтаған типпен пайдалануға болатын жалпы кластар жиынтығын ұсынады. STL алгоритмдері контейнерлерден тәуелсіз, бұл кітапхананың күрделілігін едәуір төмендетеді. STL үлгілерді пайдалану арқылы нәтижелерге жетеді. Бұл тәсіл, әдетте, орындалу кезіндегі полиморфизмге қарағанда тиімдірек, компиляция кезіндегі полиморфизмді қамтамасыз етеді. Қазіргі заманғы C++ компиляторлары STL-ді кеңінен пайдаланудан туындайтын абстракция салдарынан туындаған шығындарды азайтуға бағытталған. STL C++ үшін жалпы алгоритмдер мен деректер құрылымдарының алғашқы кітапханасы ретінде құрылды, онда төрт негізгі идея болды: жалпы бағдарламалау, тиімділікті жоғалтпай абстракция, фон Нейманның есептеу моделі және мәндік семантика. STL және C++ стандартты кітапханасы – екі бөлек құрал.
The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators. The STL provides a set of common classes for C++, such as containers and associative arrays, that can be used with any built in type and with any user defined type that supports some elementary operations (such as copying and assignment). STL algorithms are independent of containers, which significantly reduces the complexity of the library. The STL achieves its results through the use of templates. This approach provides compile time polymorphism that is often more efficient than traditional run time polymorphism. Modern C++ compilers are tuned to minimize abstraction penalties arising from heavy use of the STL. The STL was created as the first library of generic algorithms and data structures for C++, with four ideas in mind: generic programming, abstractness without loss of efficiency, the Von Neumann computation model, and value semantics. The STL and the C++ Standard Library are two distinct entities.
Тарих
1993 жылдың қараша айында Александр Степанов C++ стандартына қатысты ANSI/ISO комитетіне жалпылама бағдарламалау негізіндегі кітапхананы ұсынды. Комитет бұл ұсынысқа өте жағымды жауап берді, содан кейін Эндрю Кениг 1994 жылдың наурыз айындағы жиналысқа дейін ресми ұсыныс беруді сұрады. Комитет өзгерістер мен кеңейтулер бойынша бірнеше сұраулар жіберді, сондай-ақ комитет мүшелері Степанов пен Мэн Лимен кездесіп, мәліметтерді нақтылады. Ең маңызды кеңейтудің (әрекеттес контейнерлер) талаптары толыққанды іске асырылған жағдайда ғана сәйкес келетінін көрсету қажет болды, бұл міндетті Степанов Дэвид Муссерге жүктеді. 1994 жылдың шілдесінде ANSI/ISO комитетінің отырысында ұсынысқа соңғы мақұлдау берілді. Содан кейін Степанов пен Лидің 17 нөміріндегі құжаты ANSI/ISO C++ стандартының жобасына (1-ден 27-ге дейінгі тараулардың 1-бөлігі) қосылды. STL-дің кеңінен таралу мүмкіндігі Hewlett Packard компаниясының 1994 жылдың тамызында оның іске асырылуын интернетте тегін қолжетімді ету туралы шешім қабылдауымен едәуір жақсарды. Бұл іске асырылу, стандарттау процесінде Степанов, Ли және Муссердің бірлесіп жасаған еңбегі, бүгінде көптеген компилятор және кітапхана жеткізушілері ұсынатын іске асырылулардың негізіне айналды.
In November 1993 Alexander Stepanov presented a library based on generic programming to the ANSI/ISO committee for C++ standardization. The committee's response was overwhelmingly favorable and led to a request from Andrew Koenig for a formal proposal in time for the March 1994 meeting. The committee had several requests for changes and extensions and the committee members met with Stepanov and Meng Lee to help work out the details. The requirements for the most significant extension (associative containers) had to be shown to be consistent by fully implementing them, a task Stepanov delegated to David Musser. A proposal received final approval at the July 1994 ANSI/ISO committee meeting. Subsequently, the Stepanov and Lee document 17 was incorporated into the ANSI/ISO C++ draft standard (1, parts of clauses 17 through 27). The prospects for early widespread dissemination of the STL were considerably improved with Hewlett Packard's decision to make its implementation freely available on the Internet in August 1994. This implementation, developed by Stepanov, Lee, and Musser during the standardization process, became the basis of many implementations offered by compiler and library vendors today.
Алгоритмдер
Іздеу және сұрыптау сияқты амалдарды орындау үшін STL-де көптеген алгоритмдер ұсынылады, олардың әрқайсысы белгілі бір деңгейдегі итераторды қажет етеді (сондықтан итераторлар арқылы интерфейс ұсынатын кез келген контейнермен жұмыс істейді). Екілік іздеуді пайдаланатын және ұқсас сұрыптау алгоритмдері сияқты іздеу алгоритмдері дерек түрінің салыстыру операторын немесе қолданушыға арналған салыстыру функциясын қажет етеді; мұндай салыстыру операторы немесе салыстыру функциясы қатаң әлсіз реттілікке кепілдік беруі керек. Бұлардан басқа, элементтер тізбегінен қалыпты үйінді жасау, элементтер тізбегінің лексикографиялық реттелген түрленімдерін жасау, сұрыпталған диапазонды біріктіру және сұрыпталған диапазонның біріктіру, қиылысу, айырмасын орындау үшін алгоритмдер ұсынылады.
A large number of algorithms to perform activities such as searching and sorting are provided in the STL, each implemented to require a certain level of iterator (and therefore will work on any container that provides an interface by iterators). Searching algorithms like and use binary search and like sorting algorithms require that the type of data must implement comparison operator or custom comparator function must be specified; such comparison operator or comparator function must guarantee strict weak ordering. Apart from these, algorithms are provided for making heap from a range of elements, generating lexicographically ordered permutations of a range of elements, merge sorted ranges and perform union, intersection, difference of sorted ranges.
Функторлар
STL функцияны шақыру операторын жүктемелі жасайтын кластарды қамтиды. Мұндай кластардың мысалдары функторлар немесе функциялық объектілер деп аталады. Функторлар байланысты функцияның әрекетін параметрлеуге мүмкіндік береді (мысалы, функтордың конструкторына берілген аргументтер арқылы) және функциямен бірге функторға қатысты күй туралы ақпаратты сақтауға қолданылады. Функторлар мен функциялық нұсқаулардың екеуі де функцияны шақыру синтаксисі арқылы шақырыла алатындықтан, тиісті параметр функция шақыру контекстінде ғана пайда болған жағдайда, оларды шаблон аргументтері ретінде алмастыруға болады. Функтордың ең көп тараған түрі – предикат. Мысалы, алгоритмдер тізбек элементтерімен жұмыс жасайтын унарлы предикатты қабылдайды. Сорттау, ішінара сұрыптау, n-інші элемент және барлық сұрыпталған контейнерлер сияқты алгоритмдер қатаң әлсіз реттілік қамтамасыз ететін екілік предикатты пайдаланады, яғни ол транзитивті, рефлексивті емес және асимметриялық екілік қатынаста мүшелік тестілеу сияқты жұмыс істеуі керек. Егер ештеңе берілмесе, бұл алгоритмдер мен контейнерлер әдепкі бойынша `less` операторын пайдаланады, ол өз кезегінде `<` операторын шақырады.
The STL includes classes that overload the function call operator Instances of such classes are called functors or function objects. Functors allow the behavior of the associated function to be parameterized (e. g. through arguments passed to the functor's constructor) and can be used to keep associated per functor state information along with the function. Since both functors and function pointers can be invoked using the syntax of a function call, they are interchangeable as arguments to templates when the corresponding parameter only appears in function call contexts. A particularly common type of functor is the predicate. For example, algorithms like take a unary predicate that operates on the elements of a sequence. Algorithms like sort, partial sort, nth element and all sorted containers use a binary predicate that must provide a strict weak ordering, that is, it must behave like a membership test on a transitive, non reflexive and asymmetric binary relation. If none is supplied, these algorithms and containers use less by default, which in turn calls the less than operator <.
Басқа мәселелер
STL контейнерлерін бастапқы кодтағы тұрақтылармен инициализациялау C-ден мұрагерлік алған дерек құрылымдары сияқты оңай емес (C++11 инициализатор тізімдерімен шешілді). STL контейнерлері базалық сыныптар ретінде қолдануға арналмаған (олардың деструкторлары қасақана виртуалды емес); контейнерден туындату – жиі кездесетін қателік. STL іске асырған итераторлар тұжырымын бастапқыда түсіну қиын болуы мүмкін: мысалы, егер итератор көрсеткен мән жойылса, итератордың өзі жарамсыз болады. Бұл қателердің кең таралған себебі. STL-дің көптеген іске асырылымдары баяурақ, бірақ осындай қателерді анықтай алатын жөндеу режимін ұсынады. Осындай мәселе басқа тілдерде де бар, мысалы Java. Итераторларға қарағанда қауіпсіз және икемді балама ретінде диапазондар ұсынылған. Кейбір итерация үлгілері, мысалы, кері шақыру санама API-лары, C++20-ға дейін C++ стандартынан тыс болған корутиналарды қолданбастан STL моделіне сәйкес келмейді. Компилятордың сәйкестігі контейнерлер үшін жад басқаруға қолданылатын Allocator объектілерінің күйге тәуелді әрекеттерімен жұмыс істейтініне кепілдік бермейді. Мысалы, портативті кітапхана әртүрлі жад қоймаларынан жадты алу үшін әртүрлі Allocator объектілерін пайдаланатын Allocator түрін анықтай алмайды. (Meyers, 50 б.) (C++11-де қарастырылған). Алгоритмдер жиынтығы толық емес: мысалы, алгоритм алынып тасталды, бірақ ол C++11-де қосылды.
Initialization of STL containers with constants within the source code is not as easy as data structures inherited from C (addressed in C++11 with initializer lists). STL containers are not intended to be used as base classes (their destructors are deliberately non virtual); deriving from a container is a common mistake. The concept of iterators as implemented by the STL can be difficult to understand at first: for example, if a value pointed to by the iterator is deleted, the iterator itself is then no longer valid. This is a common source of errors. Most implementations of the STL provide a debug mode that is slower, but can locate such errors if used. A similar problem exists in other languages, for example Java. Ranges have been proposed as a safer, more flexible alternative to iterators. Certain iteration patterns such as callback enumeration APIs cannot be made to fit the STL model without the use of coroutines, which were outside the C++ standard until C++20. Compiler compliance does not guarantee that Allocator objects, used for memory management for containers, will work with state dependent behavior. For example, a portable library can not define an allocator type that will pull memory from different pools using different allocator objects of that type. (Meyers, p. 50) (addressed in C++11). The set of algorithms is not complete: for example, the algorithm was left out, though it has been added in C++11.