INF205: Glossary
abstract class, interface
argument passing by reference
Elucidation: "Passing by reference" can refer to any mode of passing an argument to a function that permits the called function to access the original data item, at the same address in memory, rather than receiving only a copy.
argument passing by value
Elucidation: When an argument is passed by value to a function, a copy of the argument values is created in memory (on the stack, in the stack frame of the called function). The function works with its own copy; it cannot access the original variable.
call stack, program stack, stack
class
Elucidation: "A class defines a datatype and describes content and properties of objects of that datatype. The data fields of the class are storage unites for the object's values, and the methods of the class describe the operations that can be done on or by the objects" (from the SNL entry on object orientation by E. H. Vihovde).
- "Klasse", "konsept" og "omgrep" kan brukast synonymt - dei sistnemnde helst i samanheng med ontologiar og kunnskapsgrafar.
collective operation
command-line argument
compilation
Definition: process of transforming a human-readable source code into a lower-level machine code, using a compiler
- In C/C++, the compiler is run on the source files; in C++, these files usually have the file ending *.cpp. The compiler is not run on the header files (usually with a *.h file ending).
- The machine code created by compiling a source file with a C/C++ compiler is called object code; it is stored as an object file, which usually has a *.o file ending.
- The object files produced by compiling are not executable by themselves: They need to be linked into one stand-alone executable file.
constructor
Definition: method called in order to allocate an object
- Important special constructors discussed in the lecture are the copy constructor ("rule of three:" define it jointly with an overloaded copy assignment operator) and the move constructor ("rule of five:" define it jointly with an overloaded copy assignment operator).
container
Definition: "class with the main purpose of holding objects" (Stroustrup)
- Container objects take ownership of any contained data. The programmer needs to take care of this whenever there are data subject to manual memory management (new and delete) in a self-designed container.
- Examples include the standard template library (STL) containers (list, map, set, vector, etc.). Other than for educational purposes as an exercise, it does not make sense to reimplement these standard data structures by hand.
- Many problems require special, tailored container data structures in order to be solved efficiently. It is then part of the development work to both design and implement the required data structure.
destructor
Definition: method called upon deallocating an object
dynamic library
Definition: library of compiled program code, separate from the executable file of the program, that can be accessed by the latter at runtime
entity-relationship diagram (ER diagram)
global variable
Definition: variable that can be accessed through a name with an unrestricted scope - it has a name that resolves everywhere in the code
- The term local variable can sometimes refer to any variable that is not global (i.e., any variable with a restricted scope). But it is more common to just call those variables "local" that are declared within a function.
- Some say that it is generally bad style to use any global variables. The main reason is that it is hard to debug or verify what a code does if it relies on write access to global variables.
- Despite this, it is common practice to use global variables in script languages.
graph
Definition: "collection of nodes (points) and edges (lines) that connect some or all of the edges" (T. Aambø in SNL on graph theory)
- A graph can be specified as a pair G = (V, E) of a set of nodes V and a set of edges E ⊆ V × V.
- The nodes can also be called vertices.
heap [memory management]
Definition: memory region where data are allocated dynamically, without being directly tied to the program's call stack
knowledge graph, ABox
linked list
load balancing
moving
namespace
Definition: globally accessible collection of names, i.e., rigid designators for functions, variables, classes, etc.
- To access name Y defined in namespace X, we write X::Y.
- With using namespace X; all the names from X can be accessed without a prefix.
object
Definition: "basic building block […] in object-oriented software systems; […] module consisting of data and processing rules" (E. H. Vihovde in SNL)
- "Central concepts in object-based systems are encapsulation, inheritance, and polymorphism" ibid.).
- "Encapsulation means delimiting what datatypes and processing rules are to apply to a certain class of objects" ibid.).
- "Classes are formed hierarchically, such that derived classes inherit properties of the base classes. In a database, e.g, the subclass 'secretary' can inherit the properties of the superclass 'employee'." (ibid.).
- "Polymorphism means that procedures can be realized for objects the exact for or type of which can vary" (ibid.).
- Objects are also referred to as individuals. In general, an object is said to instantiate a class, while an individual instantiates a concept. However, object and individual, and class and concept, respectively, mean the same.
object-oriented programming
overloading
Definition: use of multiple functions with the same function name and different parameter types
ownership
Elucidation: In the context of manual memory management, one object x taking ownership of another object y means that the memory use of y is managed through x. It usually implies that x acts as a container for y.
pointer
Definition: variable that has a memory address as its value
queue
Definition: sequential (list-like) dynamic data structure that functions by the principle first in, first out (FIFO)
- A queue class must provide a method for appending an element, usually called push and
done on one end of the queue (e.g., enqueue or push_back), and a method for detaching an element,
usually called pop and done at the other end of the queue (e.g., dequeue or pop_front).
- Singly and doubly linked lists are well suitable for
implementing a queue, since both push and pop
can be realized in constant time. However, a singly linked
list should only be used if the data structure includes an explicit
reference to the tail node; otherwise, the whole list needs to
be traversed just to reach the tail, taking O(n) time.
- Dynamic arrays are less suitable for this purpose, requiring
O(n) time for the push and pop
operations in the long run (as their capacity gets exhausted).
rank [parallel programming]
relationship
relationship type, relation
Elucidation: A relation specifies how objects from given classes can be connected to each other.
- Example from the lecture: For a city, we can say that it is in a country. For a country, we can say that it contains cities. Therefore there is an N-to-1 relation between cities and countries. It could be called "is in" from the perspective of the city and "contains" from the perspective of the country.
- Entity-relationship (E-R) diagrams can be used as a design tool and to visualize the relations.
- A concrete instance of the relation (e.g., the fact that Oslo is in Norway) is called a relationship.
- Note that the term "entity-relationship diagram" is strictly speaking a misnomer: The most common type of E-R diagrams do not show entites (i.e., objects), but classes (i.e., entity types). They do not show relationships, but relations (i.e., relationship types).
rule of five
rule of three
stack
Definition: sequential (list-like) dynamic data structure that functions by the principle last in, first out (LIFO)
- A stack needs a method for appending an element, usually called push and
done at the head of the stack, and a method for detaching an element,
usually called pop and also done at the head of the stack.
- Linked lists can be used straightforwardly as a stack,
such that all the push and pop are applied to
the head of the list in constant time.
- Dynamic arrays are well suitable for implementing a stack;
in this case push and pop need to be done
at the end of the array, not at the front, since it is only
insertion/deletion at the end or close to the end
that takes O(1) time for a dynamic array. In the case of insertion,
for the push operation, O(1) time is only reached in the
(frequent) best case, when there is free capacity.
In the worst case, this still requires O(n), since
the whole list needs to be copied into a new region in memory where
there is more free space.
static array
Elucidation: An array is a variable referring to a contiguous region in memory that can hold the content of multiple elementary variables or objects. A static array is just that, without any special additional functionality, as opposed to a dynamic array which provides the additional functionality that it can be resized.
- An array containing elements of type X is itself of the type X*, i.e., pointer to X, containing the memory address of the first (index-0) element of the array.
- If an array has been allocated on the heap manually, using new, it has to be deallocated using delete[], not delete; using delete would only deallocate the first (index-0) element.
strong scaling
template
tree
Definition: hierarchical linked data structure given as a graph in which there is a unique path between each pair of nodes
typing
Definition: mechanism by which a data type is assigned to data items
- Static typing assigns types at compile time, whereas dynamic typing assigns them at runtime. C/C++ uses static typing.
- Explicit typing requires the programmer to specify the data type upon introducing (declaring) a variable; implicit typing does not require this. C/C++ uses explicit typing; however, in modern C++, the keyword auto can be used in certain cases in the place of an explicit data type. Then, the compiler determines the data type.
weak scaling
wild pointer
Definition: pointer that unintentionally holds an invalid memory address as its value
- Most commonly, that invalid value is nullptr, i.e., the memory address 0x0000000000000000. This value is often assigned on purpose, to mark that the pointer does not point at a data item, but in such cases it should never be dereferenced while holding the value nullptr; e.g., it should be protected by an if clause like if(p != nullptr) { … }. Note that if handled correctly, avoiding any dereferencing, a null pointer is not considered a wild pointer.
- Faulty pointer arithmetics can be another cause, e.g., upon dereferencing an array index that is out of bounds.
Index