Questions tagged [c++]

Programming questions are off-topic here. Do not ask questions about how to write code in C++. However, conceptual questions about computer science are more appropriate. See our help center for the scope of this site.

Filter by
Sorted by
Tagged with
5
votes
1answer
664 views

Where are C++ templates inside of the lambda cube?

C++ templates have type variables and can express lambdas, so they must have System F embedded. But is that exactly where they are located in the lambda cube? Can C++ templates produce new types or ...
5
votes
4answers
203 views

How do you find a hash function that respects a custom equality function?

I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of ...
4
votes
1answer
167 views

Why are struct and class essentially the same in C++?

struct and class in C++ are nearly identical (as covered for example here). But why is this so? What did happen when C++ was ...
4
votes
1answer
178 views

Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove

C++ and Java include native classes for linked lists, C++ std::list and Java LinkedList For C++ std::list, nodes can be "moved" within a list, or from list to list (if the lists are compatible), via ...
3
votes
1answer
413 views

What type of function is main()?

As the functions are of 2 type:1.Pre-defined/library functions,2.User defined functions. What type of function is main() function? This doubt comes in my mind while writing a program we define the ...
2
votes
4answers
88 views

How do compilers assure stability?

Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but ...
2
votes
1answer
2k views

To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient ...
2
votes
2answers
111 views

Efficient way to reduce a binomial coefficient as a fraction

Here is the full problem. You need to calculate Euler's totient function of a binomial coefficient $C_n^k$. Input The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$. ...
2
votes
1answer
184 views

numerically stable log1pexp calculation

What are good approximations for computing log1pexp for single precision and double precision floating point numbers? Note: ...
2
votes
1answer
46 views

Why is the address-of operator in C/C++ represented with the “&” symbol?

I've started learning C++, and I know a little bit of C. Something that always struck me as somewhat off was that the address-of operator is represented with the seemingly random ampersand (&) ...
2
votes
1answer
32 views

printf(“%d”,~5); prints out -6 why is that?

I was reading the book "Computer systems: A programmer's perspective" and saw that the operator, "~", is a NOT operator. When I use it to NOT positive integers, it returns the ...
2
votes
1answer
333 views

C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?

I'm working on the problem: Count smaller elements on right side using Set in C++ STL The solution is to add each element to the set and then to count the elements on the left, the distance function ...
2
votes
2answers
66 views

Compare each array $i$ member to all array $j$ member where $(i > j)$ , in time less than $O(n^2)$

I am new to algorithms so sorry to ask simple question I am working on a problem which is about array of integers, my solution is right but not good enough, because I have time exceeded exception on ...
2
votes
1answer
74 views

Math behind leetcode problem 47 permutations II

Please tell me why the expression i>0 && nums[i] == nums[i-1] && !used[i-1] works on getting unique permutations. And what is the math behind it? ...
2
votes
0answers
87 views

Summary of types of equivalence and equality in type theory, with notations and examples

Coming from non-computer science background, I am trying to understand the different types of equivalence and equality usually used in type theory. Ideally, I am looking for clear definitions and ...
2
votes
0answers
78 views

Implementing a linear programming feasibility test in 3D

I have a little problem which requires determining if a system of linear inequalities in 3D is infeasible. The constraints (or oriented planes) are added one by one, so there is an opportunity to stop ...
1
vote
2answers
113 views

How do compilers implement symbolic (rather than textual) insertion?

From a programming language designer's point of view, how is "symbolic" insertion implemented as opposed to "textual" insertion using pre-processor macros? I understand the basics of how "textual" ...
1
vote
2answers
33 views

Practice of setting parallelism as the default behaviour

This is a soft, and probably also an opinion based question. Suppose I am writing a library in C++ for the purposes of working with financial data. My goals are: Since I work with big data, I want to ...
1
vote
1answer
255 views

Complete the following table by specifying the scope of each declaration

I'm having a hard time understanding this question. Can each declaration have more than one scope or can a declaration have more than one scope? If it's the later it would be: Declaration ...
1
vote
1answer
357 views

Why isn't deque implemented as a dynamic array?

We know that std::vector in C++ is implemented as a dynamic array with specific pattern of reallocation (multiplying capacity by a constant), which allows it to ...
1
vote
2answers
43 views

Which goes first stl or data structures and algorithms?

So I'm a newbie to c++. I know the basic concepts of c++ as I have already learnt c language. For competitive programming DSA is very important. But I don't know any STL functions. Is it possible to ...
1
vote
1answer
60 views

Is C++ considered a language with high or low orthogonality?

I'm looking to make a comparison of regularity in languages - specifically orthogonality. If I were to say Java is weak in terms of orthogonality and Haskell stronger, where would C++ sit and why?
1
vote
1answer
60 views

Cancellation in C++

I am trying to figure out what the problem with the following expression in C++ is: y=std::log(std::cosh(x)); My first intention was that there might occure a ...
1
vote
1answer
51 views

Reason behind declaring iteration variables on a method level

Lately, I have been in touch with some C++ snippets, and I have a very strange observation on the tiny detail: Most of the times, I see, that people declare iteration variables outside of the for/...
1
vote
1answer
50 views

How to remove an ordering requirement from a board game simulation?

The Problem: I'm trying to simulate part of the game tantrix which is a board game played with hexagonal tiles. Each tile has 3 lines of different colors that each start at one side of the hexagon ...
1
vote
1answer
76 views

What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?

Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a number (possibly one) of continuous parts. For each part independently, I then choose any ...
1
vote
1answer
62 views

Time complexity of the travelling salesman problem (Recursive formulation)

According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (...
1
vote
1answer
61 views

How does C++'s type checking work when passing overloaded or templated functions as parameter

As I understand, C++ in general features 'one-way' type checking. That is checking the sub-expressions and get their types, and see if the types so far satisfy the constraints imposed by the current ...
1
vote
1answer
431 views

Find maximum non contiguous subarray that respect a specific rule [closed]

Given these two arrays: [5, 3, 4, 1, 2] [1, 3, 2, 4, 5] Find the maximum subsequence in both arrays that the index of the elements are in a crescent order: ...
1
vote
1answer
38 views

Is the Jacobian matrix calculation process correctly on this energy function?

When I implemented the paper Dynamic Fusion published in 2015 CVPR, I came into the trouble with how to solve the energy function: $$E(W_t, V, D_t, \mathcal{E}) = \text{Data}(W_t, V, D_t) + λ\text{Reg}...
1
vote
0answers
95 views

Unordered data structure with fast insertion, deletion, and iteration

So, I need a data structure that would support the following operations: Add an element to the structure and get some "handle" for that element Retrieve an element by a handle Remove an ...
1
vote
0answers
31 views

How to justify using available code (in different language) for comparing algorithms [closed]

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
1
vote
0answers
83 views

Generate an AST from an indefinite grammar and logic

As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a ...
1
vote
1answer
89 views

Print maximum frequency number in an array(with slight modification)

There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/...
0
votes
3answers
98 views

Why do we need value-returning functions?

I'm just a beginner at C++ programming. I am currently having hard time grasping the usage of value returning function and non-value returning function. Void functions are called non-value returning ...
0
votes
2answers
59 views

Understanding memory leaks in C/C++ [closed]

I was looking at an example here: https://blog.parasoft.com/finding-memory-leaks-in-c ...
0
votes
2answers
66 views

Is this a misleading or undesirable implementation of a hash map?

I read a C++ implementation of a hash map here. https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/ Let's say key k1 has a ...
0
votes
1answer
983 views

Bytes from integer using bitwise operators

So I am extremely confused with using bitwise shifts used to extract the bytes from an integer. I find that if I do something like this... ...
0
votes
1answer
225 views

How to count number of 1s of the first k positions in a bitset (bitmap)?

Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$. Output: the total number of 1s in the first $k$ position of $b$. Obviously it can be done in $...
0
votes
1answer
613 views

Find Length of longest substring with all 1's in a binary string with k queries

Given a string of size n consisting of 0s and/or 1s.you have to perform k queries and there are two types of queries possible. "1"(without quotes): Print length of the longest substring with all '1'. ...
0
votes
1answer
38 views

The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...
0
votes
1answer
38 views

Calculate the sum of all sub-arrays with given indices

I am new to Algorithms and Competitive Coding. I have a problem as follow: For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic ...
0
votes
2answers
60 views

Intuition behind the Reversal Algorithm [ Rotation of Array ]

I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody ...
0
votes
1answer
363 views

What is the difference between python list and c++ vector?

I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both ...
0
votes
2answers
165 views

Analyzing space complexity of passing data to function by reference

I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^...
0
votes
1answer
29 views

How will I calculate the time and space complexity for this pyramid algo? [duplicate]

This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345": ...
0
votes
1answer
23 views

Recursive Call Inside Argument List (C++) [closed]

So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came ...
0
votes
2answers
139 views

Count the possible plans for nurses

I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below: The director of a hospital want to schedule a working plan for a nurse in a given period of N ...
0
votes
0answers
23 views

All string matches for regular expression [duplicate]

Given a regular expression, the ask is to find all matches in a string, str. Most implementations give longest match only. For example, [\d]* in str "123456", the regex libraries in C++ or ...
0
votes
0answers
26 views

What is meant by the statement “Data is inactive but information is active”?

I came across the statement "data is inactive but information is active" while reading differences between data and information. What is meant by this statement?