In computer science , a heap is a tree -based data structure that satisfies the heap property : In a max heap , for any given node C, if P is the parent node of C, then the key (the value ) of P is greater than or equal to the key of C. In a min heap , the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.
55-727: 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 or user-defined type that supports some elementary operations (such as copying and assignment). STL algorithms are independent of containers, which significantly reduces
110-595: 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 <. The Quality of Implementation (QoI) of the C++ compiler has a large impact on usability of the STL (and templated code in general): Library (computer science) In computer science ,
165-472: A binary heap , in the array, the first index contains the root element. The next two indices of the array contain the root's children. The next four indices contain the four children of the root's two child nodes, and so on. Therefore, given a node at index i , its children are at indices 2 i + 1 {\displaystyle 2i+1} and 2 i + 2 {\displaystyle 2i+2} , and its parent
220-415: A branches for each node always has log a N height. Note that, as shown in the graphic, there is no implied ordering between siblings or cousins and no implied sequence for an in-order traversal (as there would be in, e.g., a binary search tree ). The heap relation mentioned above applies only between nodes and their parents, grandparents. The maximum number of children each node can have depends on
275-414: A library is a collection of resources that is leveraged during software development to implement a computer program . Historically, a library consisted of subroutines (generally called functions today). The concept now includes other forms of executable code including classes and non-executable data including images and text . It can also refer to a collection of source code . For example,
330-402: A modular fashion. When writing code that uses a library, a programmer only needs to know high-level information such as what items it contains at and how to use the items – not all of the internal details of the library. Libraries can use other libraries resulting in a hierarchy of libraries in a program. A library of executable code has a well-defined interface by which the functionality
385-468: A Communication Pool (COMPOOL), roughly a library of header files. Another major contributor to the modern library concept came in the form of the subprogram innovation of FORTRAN . FORTRAN subprograms can be compiled independently of each other, but the compiler lacked a linker . So prior to the introduction of modules in Fortran-90, type checking between FORTRAN subprograms was impossible. By
440-407: A binary heap), where s 2 ( N ) is the sum of all digits of the binary representation of N and e 2 ( N ) is the exponent of 2 in the prime factorization of N . This is faster than a sequence of consecutive insertions into an originally empty heap, which is log-linear. Here are time complexities of various heap data structures. The abbreviation am. indicates that the given complexity
495-559: A feature called smart linking whereby the linker is aware of or integrated with the compiler, such that the linker knows how external references are used, and code in a library that is never actually used , even though internally referenced, can be discarded from the compiled application. For example, a program that only uses integers for arithmetic, or does no arithmetic operations at all, can exclude floating-point library routines. This smart-linking feature can lead to smaller application file sizes and reduced memory usage. Some references in
550-464: A heap, the heap property may be violated, and the heap must be re-balanced by swapping elements within the array. Although different types of heaps implement the operations differently, the most common way is as follows: Construction of a binary (or d -ary) heap out of a given array of elements may be performed in linear time using the classic Floyd algorithm , with the worst-case number of comparisons equal to 2 N − 2 s 2 ( N ) − e 2 ( N ) (for
605-405: A heap, the highest (or lowest) priority element is always stored at the root. However, a heap is not a sorted structure; it can be regarded as being partially ordered. A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority, or when insertions need to be interspersed with removals of the root node. A common implementation of a heap
SECTION 10
#1732782983530660-470: A pair of iterators that designate the beginning and end of the computation, and most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. It is possible to have bidirectional iterators act like random-access iterators, so moving forward ten steps could be done by simply moving forward a step at a time a total of ten times. However, having distinct random-access iterators offers efficiency advantages. For example,
715-436: A program are loaded from individual shared objects into memory at load time or runtime , rather than being copied by a linker when it creates a single monolithic executable file for the program. Shared libraries can be statically linked during compile-time, meaning that references to the library modules are resolved and the modules are allocated memory when the executable file is created. But often linking of shared libraries
770-466: A program could use a library to indirectly make system calls instead of making those system calls directly in the program. A library can be used by multiple, independent consumers (programs and other libraries). This differs from resources defined in a program which can usually only be used by that program. When a consumer uses a library resource, it gains the value of the library without having to implement it itself. Libraries encourage code reuse in
825-589: A program or library module are stored in a relative or symbolic form which cannot be resolved until all code and libraries are assigned final static addresses. Relocation is the process of adjusting these references, and is done either by the linker or the loader . In general, relocation cannot be done to individual libraries themselves because the addresses in memory may vary depending on the program using them and other libraries they are combined with. Position-independent code avoids references to absolute addresses and therefore does not require relocation. When linking
880-400: A sequence of values), output iterators (that can only be used to write a sequence of values), forward iterators (that can be read, written to, and move forward), bidirectional iterators (that are like forward iterators, but can also move backwards) and random-access iterator s (that can move freely any number of steps in one operation). A fundamental STL concept is a range which is
935-407: A suffix of .a ( archive , static library) or of .so (shared object, dynamically linked library). Some systems might have multiple names for a dynamically linked library. These names typically share the same prefix and have different suffixes indicating the version number. Most of the names are names for symbolic links to the latest version. For example, on some systems libfoo.so.2 would be
990-416: A vector would have a random-access iterator, but a list only a bidirectional iterator. Iterators are the major feature that allow the generality of the STL. For example, an algorithm to reverse a sequence can be implemented using bidirectional iterators, and then the same implementation can be used on lists, vectors and deques . User-created containers only have to provide an iterator that implements one of
1045-412: Is at index ⌊( i −1)/2⌋ . This simple indexing scheme makes it efficient to move "up" or "down" the tree. Balancing a heap is done by sift-up or sift-down operations (swapping elements which are out of order). As we can build a heap from an array without requiring extra memory (for the nodes, for example), heapsort can be used to sort an array in-place. After an element is inserted into or deleted from
1100-440: Is created (static linking), or whenever the program is used at runtime (dynamic linking). The references being resolved may be addresses for jumps and other routine calls. They may be in the main program, or in one module depending upon another. They are resolved into fixed or relocatable addresses (from a common base) by allocating runtime memory for the memory segments of each module referenced. Some programming languages use
1155-450: Is implemented using a heap . Elements should additionally support comparison (to determine which element has a higher priority and should be popped first). Any sequence supporting operations back () , push_back () , and pop_back () can be used to instantiate stack (e.g. vector , list , and deque ). The STL implements five different types of iterators . These are input iterators (that can only be used to read
SECTION 20
#17327829835301210-413: Is invoked. For example, in C , a library function is invoked via C's normal function call capability. The linker generates code to call a function via the library mechanism if the function is available from a library instead of from the program itself. The functions of a library can be connected to the invoking program at different program lifecycle phases . If the code of the library is accessed during
1265-430: Is performed during the creation of an executable or another object file, it is known as static linking or early binding . In this case, the linking is usually done by a linker , but may also be done by the compiler . A static library , also known as an archive , is one intended to be statically linked. Originally, only static libraries existed. Static linking must be performed when any modules are recompiled. All of
1320-500: Is postponed until they are loaded. Although originally pioneered in the 1960s, dynamic linking did not reach the most commonly-used operating systems until the late 1980s. It was generally available in some form in most operating systems by the early 1990s. During this same period, object-oriented programming (OOP) was becoming a significant part of the programming landscape. OOP with runtime binding requires additional information that traditional libraries do not supply. In addition to
1375-439: Is the binary heap , in which the tree is a complete binary tree (see figure). The heap data structure, specifically the binary heap, was introduced by J. W. J. Williams in 1964, as a data structure for the heapsort sorting algorithm. Heaps are also crucial in several efficient graph algorithms such as Dijkstra's algorithm . When a heap is a complete binary tree, it has the smallest possible height—a heap with N nodes and
1430-594: The UNIX world, which uses different file extensions, when linking against .LIB file in Windows one must first know if it is a regular static library or an import library. In the latter case, a .DLL file must be present at runtime. Heap (data structure) The heap is one maximally efficient implementation of an abstract data type called a priority queue , and in fact, priority queues are often referred to as "heaps", regardless of how they may be implemented. In
1485-513: The Von Neumann computation model , and value semantics . The STL and the C++ Standard Library are two distinct entities. 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
1540-557: 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,
1595-648: 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
1650-1084: The basis of many implementations offered by compiler and library vendors today. The STL contains sequence containers and associative containers. The containers are objects that store data. The standard sequence containers include vector , deque , and list . The standard associative containers are set , multiset , map , multimap , hash_set , hash_map , hash_multiset and hash_multimap . There are also container adaptors queue , priority_queue , and stack , that are containers with specific interface, using other containers as implementation. A specialization for type bool exists, which optimizes for space by storing bool values as bits. Any sequence supporting operations front () , back () , push_back () , and pop_front () can be used to instantiate queue (e.g. list and deque ). Any random-access sequence supporting operations front () , push_back () , and pop_back () can be used to instantiate priority_queue (e.g. vector and deque ). It
1705-514: The build of the invoking program, then the library is called a static library . An alternative is to build the program executable to be separate from the library file. The library functions are connected after the executable is started, either at load-time or runtime . In this case, the library is called a dynamic library . Most compiled languages have a standard library , although programmers can also create their own custom libraries. Most modern software systems provide libraries that implement
Standard Template Library - Misplaced Pages Continue
1760-502: 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,
1815-556: The dependencies to external libraries in build configuration files (such as a Maven Pom in Java). Another library technique uses completely separate executables (often in some lightweight form) and calls them using a remote procedure call (RPC) over a network to another computer. This maximizes operating system re-use: the code needed to support the library is the same code being used to provide application support and security for every other program. Additionally, such systems do not require
1870-532: The engine would have a library of its own." In 1947 Goldstine and von Neumann speculated that it would be useful to create a "library" of subroutines for their work on the IAS machine , an early computer that was not yet operational at that time. They envisioned a physical library of magnetic wire recordings , with each wire storing reusable computer code. Inspired by von Neumann, Wilkes and his team constructed EDSAC . A filing cabinet of punched tape held
1925-536: The filename for the second major interface revision of the dynamically linked library libfoo . The .la files sometimes found in the library directories are libtool archives, not usable by the system as such. The system inherits static library conventions from BSD , with the library stored in a .a file, and can use .so -style dynamically linked libraries (with the .dylib suffix instead). Most libraries in macOS, however, consist of "frameworks", placed inside special directories called " bundles " which wrap
1980-432: The five standard iterator interfaces, and all the algorithms provided in the STL can be used on the container. 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
2035-407: The function call operator ( 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
2090-439: The instantiated objects residing only in memory (although potentially able to be made persistent in separate files). In others, like Smalltalk , the class libraries are merely the starting point for a system image that includes the entire state of the environment, classes and all instantiated objects. Today most class libraries are stored in a package repository (such as Maven Central for Java). Client code explicitly declare
2145-445: The internal structure, which is opaque to algorithms using iterators. 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 binary_search and lower_bound use binary search and like sorting algorithms require that
2200-958: The library to exist on the same machine, but can forward the requests over the network. However, such an approach means that every library call requires a considerable amount of overhead. RPC calls are much more expensive than calling a shared library that has already been loaded on the same machine. This approach is commonly used in a distributed architecture that makes heavy use of such remote calls, notably client-server systems and application servers such as Enterprise JavaBeans . Code generation libraries are high-level APIs that can generate or transform byte code for Java . They are used by aspect-oriented programming , some data access frameworks, and for testing to generate dynamic proxy objects. They also are used to intercept field access. The system stores libfoo.a and libfoo.so files in directories such as /lib , /usr/lib or /usr/local/lib . The filenames always start with lib , and end with
2255-463: The library's required files and metadata. For example, a framework called MyFramework would be implemented in a bundle called MyFramework.framework , with MyFramework.framework/MyFramework being either the dynamically linked library file or being a symlink to the dynamically linked library file in MyFramework.framework/Versions/Current/MyFramework . Dynamic-link libraries usually have
Standard Template Library - Misplaced Pages Continue
2310-501: The majority of the system services. Such libraries have organized the services which a modern application requires. As such, most code used by modern applications is provided in these system libraries. The idea of a computer library dates back to the first computers created by Charles Babbage . An 1888 paper on his Analytical Engine suggested that computer operations could be punched on separate cards from numerical input. If these operation punch cards were saved for reuse then "by degrees
2365-528: The mid 1960s, copy and macro libraries for assemblers were common. Starting with the popularity of the IBM System/360 , libraries containing other types of text elements, e.g., system parameters, also became common. In IBM's OS/360 and its successors this is called a partitioned data set . The first object-oriented programming language, Simula , developed in 1965, supported adding classes to libraries via its compiler. Libraries are important in
2420-488: The modules required by a program are sometimes statically linked and copied into the executable file. This process, and the resulting stand-alone file, is known as a static build of the program. A static build may not need any further relocation if virtual memory is used and no address space layout randomization is desired. A shared library or shared object is a file that is intended to be shared by executable files and further shared object files . Modules used by
2475-472: The names and entry points of the code located within, they also require a list of the objects they depend on. This is a side-effect of one of OOP's core concepts, inheritance, which means that parts of the complete definition of any method may be in different places. This is more than simply listing that one library requires the services of another: in a true OOP system, the libraries themselves may not be known at compile time , and vary from system to system. At
2530-430: The program linking or binding process, which resolves references known as links or symbols to library modules. The linking process is usually automatically done by a linker or binder program that searches a set of libraries and other modules in a given order. Usually it is not considered an error if a link target can be found multiple times in a given set of libraries. Linking may be done when an executable file
2585-424: The rough OOP equivalent of older types of code libraries. They contain classes , which describe characteristics and define actions ( methods ) that involve objects. Class libraries are used to create instances , or objects with their characteristics set to specific values. In some OOP languages, like Java , the distinction is clear, with the classes often contained in library files (like Java's JAR file format ) and
2640-424: The same time many developers worked on the idea of multi-tier programs, in which a "display" running on a desktop computer would use the services of a mainframe or minicomputer for data storage or processing. For instance, a program on a GUI-based computer would send messages to a minicomputer to return small samples of a huge dataset for display. Remote procedure calls (RPC) already handled these tasks, but there
2695-528: The status of the "next big thing" in the programming world. There were a number of efforts to create systems that would run across platforms, and companies competed to try to get developers locked into their own system. Examples include IBM 's System Object Model (SOM/DSOM), Sun Microsystems ' Distributed Objects Everywhere (DOE), NeXT 's Portable Distributed Objects (PDO), Digital 's ObjectBroker , Microsoft's Component Object Model (COM/DCOM), and any number of CORBA -based systems. Class libraries are
2750-521: The subroutine library for this computer. Programs for EDSAC consisted of a main program and a sequence of subroutines copied from the subroutine library. In 1951 the team published the first textbook on programming, The Preparation of Programs for an Electronic Digital Computer , which detailed the creation and the purpose of the library. COBOL included "primitive capabilities for a library system" in 1959, but Jean Sammet described them as "inadequate library facilities" in retrospect. JOVIAL has
2805-475: The suffix *.DLL , although other file name extensions may identify specific-purpose dynamically linked libraries, e.g. *.OCX for OLE libraries. The interface revisions are either encoded in the file names, or abstracted away using COM-object interfaces. Depending on how they are compiled, *.LIB files can be either static libraries or representations of dynamically linkable libraries needed only during compilation, known as " import libraries ". Unlike in
SECTION 50
#17327829835302860-406: 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 find_if take a unary predicate that operates on the elements of a sequence. Algorithms like sort, partial_sort, nth_element and all sorted containers use
2915-485: 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. The STL includes classes that overload
2970-508: The type of heap. Heaps are typically constructed in-place in the same array where the elements are stored, with their structure being implicit in the access pattern of the operations. Heaps differ in this way from other data structures with similar or in some cases better theoretic bounds such as Radix trees in that they require no additional memory beyond that used for storing the keys. The common operations involving heaps are: Heaps are usually implemented with an array , as follows: For
3025-467: Was no standard RPC system. Soon the majority of the minicomputer and mainframe vendors instigated projects to combine the two, producing an OOP library format that could be used anywhere. Such systems were known as object libraries , or distributed objects , if they supported remote access (not all did). Microsoft's COM is an example of such a system for local use. DCOM, a modified version of COM, supports remote access. For some time object libraries held
#529470