Constrained Non Type Template Parameter
NTTP (C++98): Allows templates to accept non-type parameters like integers or pointers, enhancing flexibility and efficiency. CNTTP (C++20): Extends NTTP by using concepts to constrain non-type parameters, improving type safety and expressiveness. Code Example #include <concepts> #include <cstddef> // Function using NTTP template<size_t i> // size_t is unsigned, so negative values will cause an error auto get_value_nttp() { return i; } // Function using CNTTP template<std::integral auto I> // constrained to integral types auto get_value_cnttp() { return I; } int main() { // NTTP example auto x = get_value_nttp<10>(); // correct, 10 is a valid size_t // auto y = get_value_nttp<-10>(); // error, -10 is not a valid size_t (uncomment to see the error) // CNTTP example auto w = get_value_cnttp<10>(); // correct, 10 is an integral type auto z = get_value_cnttp<-10>(); // correct, -10 is an integral type return 0; }
Class Template Argument Deduction
Class Template Argument Deduction (CTAD) is a feature introduced in C++17 that allows the compiler to deduce the template arguments for class templates from the constructor arguments. This makes code more concise and avoids the need for explicit template arguments. Example without CTAD: #include <vector> #include <iostream> int main() { std::vector<int> vec = {1, 2, 3, 4, 5}; // Explicit template argument for (const auto& elem : vec) { std::cout << elem << " "; } return 0; } Example with CTAD: #include <vector> #include <iostream> int main() { std::vector vec1 = {1, 2, 3, 4, 5}; // CTAD deduces std::vector<int> std::vector vec2 = {1....
Approximate Densest Subgraph
Note The Approximate Densest Subgraph problem involves finding a subgraph of a given graph that has the highest density, where density is typically defined as the number of edges divided by the number of vertices in the subgraph. Finding the exact densest subgraph is computationally expensive, so approximate solutions are often sought. Here’s a high-level outline of how an approximate algorithm for this problem might be implemented: Initialization: Start with all vertices of the graph and no edges....
Non-Virtual Polymorphism
Modern Features in C++17 Non-virtual runtime polymorphism can be achieved with modern C++ (e.g., C++17) features std::any and std::variant as described in the table below. Notice std::tuple is not used for polymorphism; it offers a structured way to manage multiple values of different types simultaneously, such as in function return types, or parameter packs. It is put here because of its usage is a bit similar to std::any and std::variant....
Tensor Core Register Layout
Layout 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 16 17 18 19 20 21 22 23 0 0 0 0 0 0 0 0 24 25 26 27 28 29 30 31 0 0 0 0 0 0 0 0 32 33 34 35 36 37 38 39 0 0 0 0 0 0 0 0 40 41 42 43 44 45 46 47 0 0 0 0 0 0 0 0 48 49 50 51 52 53 54 55 0 0 0 0 0 0 0 0 56 57 58 59 60 61 62 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 16 24 32 40 48 56 0 0 0 0 0 0 0 0 1 9 17 25 33 41 49 57 0 0 0 0 0 0 0 0 2 10 18 26 34 42 50 58 0 0 0 0 0 0 0 0 3 11 19 27 35 43 51 59 0 0 0 0 0 0 0 0 4 12 20 28 36 44 52 60 0 0 0 0 0 0 0 0 5 13 21 29 37 45 53 61 0 0 0 0 0 0 0 0 6 14 22 30 38 46 54 62 0 0 0 0 0 0 0 0 7 15 23 31 39 47 55 63 Code on V100 int half_elements = a_frag....
Maximal Independent Set
Note An independent set in a graph is a set of vertices, no two of which are adjacent. A maximal independent set is an independent set that is not a subset of any other independent set in the graph. Here’s a basic approach to find a Maximal Independent Set: Start with an empty set S. Iterate over all vertices of the graph. For each vertex: If the vertex and its neighbors are not in S, add the vertex to S....
Maximal Matching
Note The Matching algorithm is a graph algorithm that finds a matching in a graph, where a matching is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. A Maximal matching is a matching that cannot have any more edges added to it without violating the matching property. A maximum matching is a matching that contains the largest possible number of edges....
Observable Behaviors
What is Observable Behavior & Related Issues The term observable behavior, according to the standard, means the following: — Accesses (reads and writes) to volatile objects occur strictly according to the semantics of the expressions in which they occur. In particular, they are not reordered with respect to other volatile accesses on the same thread. — At program termination, all data written into files shall be identical to one of the possible results that execution of the program according to the abstract semantics would have produced....
Graph Coloring
Note Graph coloring is a way of assigning colors to the vertices of a graph so that no two adjacent vertices share the same color. This is a classical problem in the field of graph theory and has applications in various domains like scheduling, map coloring, and solving Sudoku puzzles. The simplest form of graph coloring is vertex coloring, where the aim is to minimize the number of colors used. This problem is NP-hard, meaning there is no known algorithm that can solve all instances of the problem efficiently (in polynomial time)....
Biconnected Components
Note Biconnectivity in graphs is an important concept used to identify biconnected components (BCCs). A graph is biconnected if it is connected and does not have any articulation points, meaning removing any single vertex will not disconnect the graph. The biconnected components of a graph are maximal biconnected subgraphs. Strict Definition: A BCC should contain at least three vertices in a cycle, ensuring that the removal of any single vertex does not disconnect the component....