Misplaced Pages

#328671

73-520: Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type . Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, relational databases commonly use B-tree indexes for data retrieval, while compiler implementations usually use hash tables to look up identifiers . Data structures provide

146-567: A Boolean "in" or "not in". ADTs are a theoretical concept, used in formal semantics and program verification and, less strictly, in the design and analysis of algorithms , data structures , and software systems . Most mainstream computer languages do not directly support formally specifying ADTs. However, various language features correspond to certain aspects of implementing ADTs, and are easily confused with ADTs proper; these include abstract types , opaque data types , protocols , and design by contract . For example, in modular programming ,

219-435: A certain result, or left unspecified. There are some algorithms whose efficiency depends on the assumption that such a fetch is legal, and returns some arbitrary value in the variable's range. An abstract stack is a last-in-first-out structure, It is generally defined by three key operations: push , that inserts a data item onto the stack; pop , that removes a data item from it; and peek or top , that accesses

292-458: A computer, integers are most commonly represented as fixed-width 32-bit or 64-bit binary numbers . Users must be aware of issues with this representation, such as arithmetic overflow , where the ADT specifies a valid result but the representation is unable to accommodate this value. Nonetheless, for many purposes, the user can ignore these infidelities and simply use the implementation as if it were

365-409: A data item on top of the stack without removal. A complete abstract stack definition includes also a Boolean -valued function empty ( S ) and a create () operation that returns an initial stack instance. In the axiomatic semantics, letting S {\displaystyle S} be the type of stack states and X {\displaystyle X} be the type of values contained in

438-621: A data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analyzed separately from those operations. This observation motivates the theoretical concept of an abstract data type , a data structure that is defined indirectly by the operations that may be performed on it, and the mathematical properties of those operations (including their space and time cost). There are numerous types of data structures, generally built upon simpler primitive data types . Well known examples are: A trie , or prefix tree,

511-474: A different state) or circular stacks (that return to the same state after a finite number of pop s). In particular, they do not exclude states s such that pop ( s ) = s or push ( s , x ) = s for some x . However, since one cannot obtain such stack states from the initial stack state with the given operations, they are assumed "not to exist". In the operational definition of an abstract stack, push ( S , x ) returns nothing and pop ( S ) yields

584-558: A hidden representation. In this model, an ADT is typically implemented as a class , and each instance of the ADT is usually an object of that class. The module's interface typically declares the constructors as ordinary procedures, and most of the other ADT operations as methods of that class. Many modern programming languages, such as C++ and Java, come with standard libraries that implement numerous ADTs in this style. However, such an approach does not easily encapsulate multiple representational variants found in an ADT. It also can undermine

657-530: A means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms . Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design. Data structures can be used to organize the storage and retrieval of information stored in both main memory and secondary memory . Data structures can be implemented using

730-471: 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,

803-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

SECTION 10

#1732782816329

876-514: A single concrete instance of a data structure simultaneously. Abstract data type In computer science , an abstract data type ( ADT ) is a mathematical model for data types , defined by its behavior ( semantics ) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures , which are concrete representations of data, and are

949-462: A variety of programming languages and techniques, but they all share the common goal of efficiently organizing and storing data. Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer —a bit string , representing a memory address , that can be itself stored in memory and manipulated by the program. Thus, the array and record data structures are based on computing

1022-465: 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

1095-433: Is a separate entity or value. In this view, each operation is modelled as a mathematical function with no side effects . Operations that modify the ADT are modeled as functions that take the old state as an argument and returns the new state as part of the result. The order in which operations are evaluated is immaterial, and the same operation applied to the same arguments (including the same input states) will always return

1168-532: Is a special type of tree used to efficiently retrieve strings. In a trie, each node represents a character of a string, and the edges between nodes represent the characters that connect them. This structure is especially useful for tasks like autocomplete, spell-checking, and creating dictionaries. Tries allow for quick searches and operations based on string prefixes. Most assembly languages and some low-level languages , such as BCPL (Basic Combined Programming Language), lack built-in support for data structures. On

1241-452: Is an implementation of the abstract stack above in the C programming language . An imperative-style interface might be: This interface could be used in the following manner: This interface can be implemented in many ways. The implementation may be arbitrarily inefficient, since the formal definition of the ADT, above, does not specify how much space the stack may use, nor how long each operation should take. It also does not specify whether

1314-413: Is customary to assume also that the stack states are only those whose existence can be proved from the axioms in a finite number of steps. In this case, it means that every stack is a finite sequence of values, that becomes the empty stack (Λ) after a finite number of pop s. By themselves, the axioms above do not exclude the existence of infinite stacks (that can be pop ped forever, each time yielding

1387-557: Is empty), empty ( push ( S , x )) = F (pushing something into a stack makes it non-empty). These axioms do not define the effect of top ( s ) or pop ( s ), unless s is a stack state returned by a push . Since push leaves the stack non-empty, those two operations can be defined to be invalid when s = Λ. From these axioms (and the lack of side effects), it can be deduced that push (Λ, x ) ≠ Λ. Also, push ( s , x ) = push ( t , y ) if and only if x = y and s = t . As in some other branches of mathematics, it

1460-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

1533-447: Is implicitly assumed that names are always distinct: storing a value into a variable U has no effect on the state of a distinct variable V . To make this assumption explicit, one could add the constraint that: This definition does not say anything about the result of evaluating fetch ( V ) when V is un-initialized , that is, before performing any store operation on V . Fetching before storing can be disallowed, defined to have

SECTION 20

#1732782816329

1606-430: Is not normally relevant or meaningful, since ADTs are theoretical entities that do not "use memory". However, it may be necessary when one needs to analyze the storage used by an algorithm that uses the ADT. In that case, one needs additional axioms that specify how much memory each ADT instance uses, as a function of its state, and how much of it is returned to the pool by free . The definition of an ADT often restricts

1679-516: Is often defined implicitly, for example the free object over the set of ADT operations. The interface of the ADT typically refers only to the domain and operations, and perhaps some of the constraints on the operations, such as pre-conditions and post-conditions; but not to other constraints, such as relations between the operations, which are considered behavior. There are two main styles of formal specifications for behavior, axiomatic semantics and operational semantics . Despite not being part of

1752-411: The push ( S , x ). From this condition and from the properties of abstract variables, it follows, for example, that the sequence: where x , y , and z are any values, and U , V , W are pairwise distinct variables, is equivalent to: Unlike the axiomatic semantics, the operational semantics can suffer from aliasing. Here it is implicitly assumed that operations on a stack instance do not modify

1825-509: 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

1898-515: 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

1971-469: The type systems of programming languages. However, an ADT may be implemented . This means each ADT instance or state is represented by some concrete data type or data structure , and for each abstract operation there is a corresponding procedure or function , and these implemented procedures satisfy the ADT's specifications and axioms up to some standard. In practice, the implementation is not perfect, and users must be aware of issues due to limitations of

2044-448: The ADT. This provides a form of abstraction or encapsulation, and gives a great deal of flexibility when using ADT objects in different situations. For example, different implementations of the ADT may be more efficient in different situations; it is possible to use each in the situation where they are preferable, thus increasing overall efficiency. Code that uses an ADT implementation according to its interface will continue working even if

2117-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,

2190-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

2263-409: The abstract data type. Usually, there are many ways to implement the same ADT, using several different concrete data structures. Thus, for example, an abstract stack can be implemented by a linked list or by an array . Different implementations of the ADT, having all the same properties and abilities, can be considered semantically equivalent and may be used somewhat interchangeably in code that uses

Data structure - Misplaced Pages Continue

2336-486: The addresses of data items with arithmetic operations , while the linked data structures are based on storing addresses of data items within the structure itself. This approach to data structuring has profound implications for the efficiency and scalability of algorithms. For instance, the contiguous memory allocation in arrays facilitates rapid access and modification operations, leading to optimized performance in sequential data processing scenarios. The implementation of

2409-491: The array size). Functional-style ADT definitions are more appropriate for functional programming languages, and vice versa. However, one can provide a functional-style interface even in an imperative language like C. For example: Standard Template Library The Standard Template Library ( STL ) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of

2482-591: The arrays in many scripting languages, such as Awk , Lua , and Perl , which can be regarded as an implementation of the abstract list. In a formal specification language , ADTs may be defined axiomatically, and the language then allows manipulating values of these ADTs, thus providing a straightforward and immediate implementation. The OBJ family of programming languages for instance allows defining equations for specification and rewriting to run them. Such automatic implementations are usually not as efficient as dedicated implementations, however. As an example, here

2555-550: The axiomatic semantics, creating the initial stack is a "trivial" operation, and always returns the same distinguished state. Therefore, it is often designated by a special symbol like Λ or "()". The empty operation predicate can then be written simply as s = Λ {\displaystyle s=\Lambda } or s ≠ Λ {\displaystyle s\neq \Lambda } . The constraints are then pop(push(S,v))=(S,v) , top(push(S,v))=v , empty ( create ) = T (a newly created stack

2628-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

2701-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,

2774-422: The concrete data structure used—can then be hidden from most clients of the module. This makes it possible to change the implementation without affecting the clients. If the implementation is exposed, it is known instead as a transparent data type. Modern object-oriented languages, such as C++ and Java , support a form of abstract data types. When a class is used as a type, it is an abstract type that refers to

2847-574: The definition of an abstract variable to include abstract records , operations upon a field F of a record variable R , clearly involve F , which is distinct from, but also a part of, R . A partial aliasing axiom would state that changing a field of one record variable does not affect any other records. Some authors also include the computational complexity ("cost") of each operation, both in terms of time (for computing operations) and space (for representing values), to aid in analysis of algorithms . For example, one may specify that each operation takes

2920-529: The development of the CLU language. Algebraic specification was an important subject of research in CS around 1980 and almost a synonym for abstract data types at that time. It has a mathematical foundation in universal algebra . Formally, an ADT is analogous to an algebraic structure in mathematics, consisting of a domain, a collection of operations, and a set of constraints the operations must satisfy. The domain

2993-433: The difference in operation costs, and that an ADT specification should be independent of implementation. An abstract variable may be regarded as the simplest non-trivial ADT, with the semantics of an imperative variable. It admits two operations, fetch and store . Operational definitions are often written in terms of abstract variables. In the axiomatic semantics, letting V {\displaystyle V} be

Data structure - Misplaced Pages Continue

3066-465: The extensibility of object-oriented programs. In a pure object-oriented program that uses interfaces as types, types refer to behaviours, not representations. The specification of some programming languages is intentionally vague about the representation of certain built-in data types, defining only the operations that can be done on them. Therefore, those types can be viewed as "built-in ADTs". Examples are

3139-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

3212-442: The four data types can then be given by successively adding the following rules over these operations: Access to the data can be specified by pattern-matching over the three operations, e.g. a member function for these containers by: Care must be taken to ensure that the function is invariant under the relevant rules for the data type. Within each of the equivalence classes implied by the chosen subset of equations, it has to yield

3285-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

3358-419: The imperative style often used when describing abstract algorithms. The constraints are typically specified in prose. Presentations of ADTs are often limited in scope to only key operations. More thorough presentations often specify auxiliary operations on ADTs, such as: These names are illustrative and may vary between authors. In imperative-style ADT definitions, one often finds also: The free operation

3431-399: The implementation of the ADT is changed. In order to prevent clients from depending on the implementation, an ADT is often packaged as an opaque data type or handle of some sort, in one or more modules , whose interface contains only the signature (number and types of the parameters and results) of the operations. The implementation of the module—namely, the bodies of the procedures and

3504-493: The implementation. An extension of ADT for computer graphics was proposed in 1979: an abstract graphical data type (AGDT). It was introduced by Nadia Magnenat Thalmann , and Daniel Thalmann . AGDTs provide the advantages of ADTs with facilities to build graphical objects in a structured way. Abstract data types are theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe

3577-459: The interface, the constraints are still important to the definition of the ADT; for example a stack and a queue have similar add element/remove element interfaces, but it is the constraints that distinguish last-in-first-out from first-in-first-out behavior. The constraints do not consist only of equations such as fetch(store(S,v))=v but also logical formulas . In the spirit of functional programming , each state of an abstract data structure

3650-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

3723-463: The location V . The constraints are described informally as that reads are consistent with writes. As in many programming languages, the operation store ( V , x ) is often written V ← x (or some similar notation), and fetch ( V ) is implied whenever a variable V is used in a context where a value is required. Thus, for example, V ← V + 1 is commonly understood to be a shorthand for store ( V , fetch ( V ) + 1). In this definition, it

SECTION 50

#1732782816329

3796-581: The module declares procedures that correspond to the ADT operations, often with comments that describe the constraints. This information hiding strategy allows the implementation of the module to be changed without disturbing the client programs, but the module only informally defines an ADT. The notion of abstract data types is related to the concept of data abstraction , important in object-oriented programming and design by contract methodologies for software engineering . ADTs were first proposed by Barbara Liskov and Stephen N. Zilles in 1974, as part of

3869-834: The most common data structures. Examples are the C++ Standard Template Library , the Java Collections Framework , and the Microsoft .NET Framework . Modern languages also generally support modular programming , the separation between the interface of a library module and its implementation. Some provide opaque data types that allow clients to hide implementation details. Object-oriented programming languages , such as C++ , Java , and Smalltalk , typically use classes for this purpose. Many known data structures have concurrent versions which allow multiple computing threads to access

3942-405: The most recent store operation on the same variable V , i.e. fetch(store(V,x)) = x . We may also require that store overwrites the value fully, store(store(V,x1),x2) = store(V,x2) . In the operational semantics, fetch ( V ) is a procedure that returns the current value in the location V , and store ( V , x ) is a procedure with void return type that stores the value x in

4015-405: The operations as if only one instance exists during the execution of the algorithm, and all operations are applied to that instance. For example, a stack may have operations push ( x ) and pop (), that operate on the only existing stack. ADT definitions in this style can be easily rewritten to admit multiple coexisting instances of the ADT, by adding an explicit instance parameter (like S in

4088-403: The order in which operations are evaluated is important, and the same operation on the same entities may have different effects if executed at different times. This is analogous to the instructions of a computer or the commands and procedures of an imperative language. To underscore this view, it is customary to say that the operations are executed or applied , rather than evaluated , similar to

4161-633: The other hand, many high-level programming languages and some higher-level assembly languages, such as MASM , have special syntax or other built-in support for certain data structures, such as records and arrays. For example, the C (a direct descendant of BCPL) and Pascal languages support structs and records, respectively, in addition to vectors (one-dimensional arrays ) and multi-dimensional arrays. Most programming languages feature some sort of library mechanism that allows data structure implementations to be reused by different programs. Modern languages usually come with standard libraries that implement

4234-402: The point of view of an implementer, not a user. For example, a stack has push/pop operations that follow a Last-In-First-Out rule, and can be concretely implemented using either a list or an array. Another example is a set which stores values, without any particular order , and no repeated values. Values themselves are not retrieved from sets; rather, one tests a value for membership to obtain

4307-399: The representation and implemented procedures. For example, integers may be specified as an ADT, defined by the distinguished values 0 and 1, the operations of addition, subtraction, multiplication, division (with care for division by zero), comparison, etc., behaving according to the familiar mathematical axioms in abstract algebra such as associativity, commutativity, and so on. However, in

4380-578: The result of create () is distinct from any instance already in use by the algorithm. Implementations of ADTs may still reuse memory and allow implementations of create () to yield a previously created instance; however, defining that such an instance even is "reused" is difficult in the ADT formalism. More generally, this axiom may be strengthened to exclude also partial aliasing with other instances, so that composite ADTs (such as trees or records) and reference-style ADTs (such as pointers) may be assumed to be completely disjoint. For example, when extending

4453-409: The same functional behavior but with different complexity tradeoffs, the user of this code will be unpleasantly surprised. I could tell him anything I like about data abstraction, and he still would not want to use the code. Complexity assertions have to be part of the interface. Other authors disagree, arguing that a stack ADT is the same whether it is implemented with a linked list or an array, despite

SECTION 60

#1732782816329

4526-420: The same result for all of its members. Some common ADTs, which have proved useful in a great variety of applications, are Each of these ADTs may be defined in many ways and variants, not necessarily equivalent. For example, an abstract stack may or may not have a count operation that tells how many items have been pushed and not yet popped. This choice makes a difference not only for its clients but also for

4599-415: The same results (and output states). The constraints are specified as axioms or algebraic laws that the operations must satisfy. In the spirit of imperative programming , an abstract data structure is conceived as an entity that is mutable —meaning that there is a notion of time and the ADT may be in different states at different times. Operations then change the state of the ADT over time; therefore,

4672-669: The same time and each value takes the same space regardless of the state of the ADT, or that there is a "size" of the ADT and the operations are linear, quadratic, etc. in the size of the ADT. Alexander Stepanov , designer of the C++ Standard Template Library , included complexity guarantees in the STL specification, arguing: The reason for introducing the notion of abstract data types was to allow interchangeable software modules. You cannot have interchangeable modules unless these modules share similar complexity behavior. If I replace one module with another module with

4745-422: The stack example below) to every operation that uses or modifies the implicit instance. Some ADTs cannot be meaningfully defined without allowing multiple instances, for example when a single operation takes two distinct instances of the ADT as parameters, such as a union operation on sets or a compare operation on lists. The multiple instance style is sometimes combined with an aliasing axiom, namely that

4818-492: The stack state s continues to exist after a call x ← pop ( s ). In practice the formal definition should specify that the space is proportional to the number of items pushed and not yet popped; and that every one of the operations above must finish in a constant amount of time, independently of that number. To comply with these additional specifications, the implementation could use a linked list, or an array (with dynamic resizing) together with two integers (an item count and

4891-589: The stack, these could have the types p u s h : S → X → S {\displaystyle push:S\to X\to S} , p o p : S → ( S , X ) {\displaystyle pop:S\to (S,X)} , t o p : S → X {\displaystyle top:S\to X} , c r e a t e : S {\displaystyle create:S} , and e m p t y : S → B {\displaystyle empty:S\to \mathbb {B} } . In

4964-494: The state of any other ADT instance, including other stacks; that is: A more involved example is the Boom hierarchy of the binary tree , list , bag and set abstract data types. All these data types can be declared by three operations: null , which constructs the empty container, single , which constructs a container from a single element and append , which combines two containers of the same type. The complete specification for

5037-493: The stored value(s) for its instances, to members of a specific set X called the range of those variables. For example, an abstract variable may be constrained to only store integers. As in programming languages, such restrictions may simplify the description and analysis of algorithms , and improve its readability. In the operational style, it is often unclear how multiple instances are handled and if modifying one instance may affect others. A common style of defining ADTs writes

5110-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

5183-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

5256-410: The type of the abstract variable and X {\displaystyle X} be the type of its contents, fetch is a function V → X {\displaystyle V\to X} and store is a function of type V → X → V {\displaystyle V\to X\to V} . The main constraint is that fetch always returns the value x used in

5329-407: The value as the result but not the new state of the stack. There is then the constraint that, for any value x and any abstract variable V , the sequence of operations { push ( S , x ); V ← pop ( S ) } is equivalent to V ← x . Since the assignment V ← x , by definition, cannot change the state of S , this condition implies that V ← pop ( S ) restores S to the state it had before

#328671