But that would then need O(n) extra space right?
yes. but it won't really matter if you can invent an O(n) time sorting algorithm like that.
Anonymous
Anonymous
but you can't
Anonymous
Well I don't know about that but I see this in a video lecture and he was telling like ok if you have such a problem then it's better to use a heap instead of sorting the complete array.
you should try benchmarking and see what is the best approach on a case by case basis. also see what feels more appropriate for a given problem.
https://quick-bench.com/
Anshul
Anshul
And also for the above problem. Even sorting the array is the optimal solution right?
Anshul
no. you measure how long things take.
Like getting to know the time required to run my program?
Anonymous
And also for the above problem. Even sorting the array is the optimal solution right?
theoretically yes. but practically 🤷 need to check on a case by case basis
Anonymous
Like getting to know the time required to run my program?
just open the website. the default code provided there shows an example
Anshul
And can you tell me more about why we actually need heap because the lectures what I was following basically focused on ok if you want to get maximum or minimum of N numbers then heap is the best option to do so. And now this thing seems to be taking the same time so.
Anshul
oh i got it now. If i have an array of numbers then extracting 3 top elements will take O(nlogn) time but in case of having a heap ready with me will take just o(3logn) time although the building of heap takes o (nlogn) time still its better than the array as in case if i get some more elements say m more elements,then i'll need to sort the array again and again while for heap i can insert the elements in o(mlog(n+m)) time and then extraction is easier. thus the building part takes time but its one time job and we're ahead of arrays. So its' gonna be almost the same complexity but still less number of operations.
Anshul
is it correct?
Shahar
Good C++ blogs?
Like realpython for Python.
神 ꜰʟᴀꜰꜰʏ
the expression before the brackets of the probable call must have the function type (pointer-to -)
who can explain how to fix this?
Anshul
the expression before the brackets of the probable call must have the function type (pointer-to -)
who can explain how to fix this?
What do you mean can you elaborate
Anshul
Why is exception handling provided by c++.
If there is some exception then we have to throw it ourselves using throw and then handle it ourselves, so what c++ is doing in it
Why don't just use if else block for it
神 ꜰʟᴀꜰꜰʏ
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
double x, m, j, f;
cout << "enter x: " << endl;
cin >> x;
cout << "enter m: " << endl;
cin >> m;
if (m > -1 && m < x) {
j = sin(5 * f * (x)+3 * m * fabs(f * (x)));
cout << j << endl;
}
else {
if (m > x) {
j = cos(3 * f(x) + 5 * m * fabs(f * (x)));
cout << j << endl;
}
else {
j = pow(f * (x)+m, 2);
cout << j << endl;
}
}
}
Captain
Captain
Like bad_alloc
Anshul
Like bad_alloc
I saw only these exception till now.
Divide by 0
Or somewhere when you want to throw and exception for an abnormal condition.
What they do is
int a,b,c; input a b c
Try
{
if(b==0)
Throw 1;
c is a divide by b
}
Catch(int)
(
Print exception thrown
)
This I can simply do
If b is 0 print exception thrown
No need of try catch throw
Anshul
What's alias.
namespace ms= myspace
(Assume myspace is an already existing namespace)
Can I do this for data types as well
Anshul
What's alias.
namespace ms= myspace
(Assume myspace is an already existing namespace)
Can I do this for data types as well
Using typedef myspace ms;
Is it exactly same ??
Mr
Hello
Mr
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
int isKeyword(char buffer[]){
char keywords[32][10] = {"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
int i, flag = 0;
for(i = 0; i < 32; ++i){
if(strcmp(keywords[i], buffer) == 0){
flag = 1;
break;
}
}
return flag;
}
int main(){
char ch, buffer[15], operators[] = "+-*/%=";
FILE *fp;
int i,j=0;
fp = fopen("program.txt","r");
if(fp == NULL){
printf("error while opening the file\n");
exit(0);
}
while((ch = fgetc(fp)) != EOF){
for(i = 0; i < 6; ++i){
if(ch == operators[i])
printf("%c is operator\n", ch);
}
if(isalnum(ch)){
buffer[j++] = ch;
}
else if((ch == ' ' || ch == '\n') && (j != 0)){
buffer[j] = '\0';
j = 0;
if(isKeyword(buffer) == 1)
printf("%s is keyword\n", buffer);
else
printf("%s is indentifier\n", buffer);
}
}
fclose(fp);
return 0;
}
klimi
For posting long code snippets:
* [GitHub Gist](https://gist.github.com)
* [Ubuntu Paste](https://paste.ubuntu.com/)
* [Pastebin](https://pastebin.com)
Mr
Any one help me for make a report of this program please
Anonymous
Why is exception handling provided by c++.
If there is some exception then we have to throw it ourselves using throw and then handle it ourselves, so what c++ is doing in it
Why don't just use if else block for it
Exception Handling is meant to separate the code where an error is detected from the place where the error can be handled.
We can do something similar using if else blocks and by returning error codes as well. But the problem with returning error codes is that people don't check them. Also the code becomes very convoluted. Exceptions avoid this problem. However exceptions should not be used indiscriminately. They impose a run time cost on your programs. Used judiciously, they can streamline your error handling code and also make it less error prone.
Anonymous
What's alias.
namespace ms= myspace
(Assume myspace is an already existing namespace)
Can I do this for data types as well
This is used to create an alias for a namespace.
If you have a long namespace like com::Palantir::Lexer::Token, you can refer to it using a shorter alias like
namespace lextok = com::Palantir::Lexer::Token;
Anonymous
Using typedef myspace ms;
Is it exactly same ??
No typedefs are aliases for types. They can't be used for namespaces. Also they can't be templated. Modern C++ recommends "using alias declarations" over typedefs.
Anshul
Exception Handling is meant to separate the code where an error is detected from the place where the error can be handled.
We can do something similar using if else blocks and by returning error codes as well. But the problem with returning error codes is that people don't check them. Also the code becomes very convoluted. Exceptions avoid this problem. However exceptions should not be used indiscriminately. They impose a run time cost on your programs. Used judiciously, they can streamline your error handling code and also make it less error prone.
What do you mean by these "exception should not be used indiscriminately"
"Streamline your error handling ..."
Anonymous
Anshul
No typedefs are aliases for types. They can't be used for namespaces. Also they can't be templated. Modern C++ recommends "using alias declarations" over typedefs.
Okay
how do I make an alias for data types? I mean typedef have any problems if I make an alias for my data types?
Anonymous
What do you mean by these "exception should not be used indiscriminately"
"Streamline your error handling ..."
Using exceptions for logical errors is bad. U must use assertions and programming logic checks to ensure logic errors don't happen. Throwing and catching exceptions is a costly affair. Logic errors must result in exceptions only if the code call transcends two silos or domains i.e code from a different domain calls your domain's code. Within your domain logic errorsshouldbe handle by programming logic checks and assertions rather than exceptions. These are all slightly advanced concepts. Once you work in C++ for a while and you become familiar with architecting code, you will understand them.
Anonymous
Okay
how do I make an alias for data types? I mean typedef have any problems if I make an alias for my data types?
You can make aliases for datatypes using either typedefs or "using alias declarations"
typedef MyData MD;
Here MD is an alias for MyData.
You can also use
using MD = MyData;
It has the same meaning. The latter method is recommended.
Anshul
Building of heap doesn't take O(N lg N). It can be done in O(N)
Can you explain this please
Anonymous
Also please don't tag me when you are looking for answers. Just ask your question and wait for a reply from someone.
Anshul
Also please don't tag me when you are looking for answers. Just ask your question and wait for a reply from someone.
Sorry for that, I'll keep it in mind.
Anonymous
Can you explain this please
What is there to explain? Building a max heap or a min heap is a linear time algorithm. It is not N lg N.
Anshul
What is there to explain? Building a max heap or a min heap is a linear time algorithm. It is not N lg N.
But as inserting one element takes o logn time and thus n insertion should take nlogn time
Anonymous
But as inserting one element takes o logn time and thus n insertion should take nlogn time
Heap building algorithms can work inplace. Don't build the heap as and when each element arrives (unless you have a sliding window requirement where elements have to be processed as and when they arrive). Get all the elements first Say you have an array of n elements. Then building a min ora max heap out of this will just be O(N)
Anshul
Heap building algorithms can work inplace. Don't build the heap as and when each element arrives (unless you have a sliding window requirement where elements have to be processed as and when they arrive). Get all the elements first Say you have an array of n elements. Then building a min ora max heap out of this will just be O(N)
So if I want to insert n elements in the heap, so first I should build an array and then convert it to min/max heap?
Anshul
What if I am doing this
Priority_queue<> pq;
for n elements
int no
Input no
pq.push(no)
Will this take o(nlogn) or o(n) time
Anonymous
So if I want to insert n elements in the heap, so first I should build an array and then convert it to min/max heap?
Yes that will be much more efficient as far as the building part is concerned. But the operations thereafter will determine your overall complexity.
If you want to heapsort an array of size N here are the steps:
Build max heap - O(n)
Repeat N times:
Extract max and move to end of array O(1).
Sift up the element at the original end position O(lg n)
Decrease array size by 1 O(1)
So overall complexity will be O(n) + n* O(lg n)
= O(n lg n)
Anonymous
What if I am doing this
Priority_queue<> pq;
for n elements
int no
Input no
pq.push(no)
Will this take o(nlogn) or o(n) time
This will take O(n lg n) because priority queue will build the heap bit by bit everytime you insert an element
Anshul
Anshul
Because think we want to get the top 3 largest elements of n integers. Then one way is I sort all the n numbers in o(nlogn). And then extract 3 top elements.
Other way is using heap for it.
Then if heap is also doing it in O(nlogn) what's the use
.see this
Here the steps do it in o(3logn)
First insert the n elements in a vector in O(n) time
Then build the heap O(n)
Then extracting 3 elements
O(3logn)
Is it correct?
Now the complexity will be maximum of the o(n) and o(klogn)
K is no. Of elements I want to extract (k is 3 in my example)
Anonymous
.see this
Here the steps do it in o(3logn)
First insert the n elements in a vector in O(n) time
Then build the heap O(n)
Then extracting 3 elements
O(3logn)
Is it correct?
Now the complexity will be maximum of the o(n) and o(klogn)
K is no. Of elements I want to extract (k is 3 in my example)
The complexity for extracting 3 max elements from an array using a heap will be O(n) + O (3 lg n) which will be O(n) when 3 <<< n
Anshul
.see this
Here the steps do it in o(3logn)
First insert the n elements in a vector in O(n) time
Then build the heap O(n)
Then extracting 3 elements
O(3logn)
Is it correct?
Now the complexity will be maximum of the o(n) and o(klogn)
K is no. Of elements I want to extract (k is 3 in my example)
Yes but I am asking that doing this is better than directly inserting elements into my priority queue object and then extracting?
Anonymous
Yes but I am asking that doing this is better than directly inserting elements into my priority queue object and then extracting?
Depends on the number of elements you want.
Anshul
How?
Anshul
In any case the 2nd approach will take o(nlogn) time right? But the first one will take o(klogn) time?
Anonymous
How?
If you extract n/2 max elements using a heap the complexity will be O(n lg n). It will be O(n^2) if you try to do it directly.
If you are extracting just 3 max elements, u can do it either directly or using a heap and in this case the complexity will just be O(n)
Anonymous
In any case the 2nd approach will take o(nlogn) time right? But the first one will take o(klogn) time?
When you say 2nd approach, do you mean sorting? I thought your approach was to sequentially scan the array to determine the max 3 elements.
Anshul
When you say 2nd approach, do you mean sorting? I thought your approach was to sequentially scan the array to determine the max 3 elements.
No I mean inserting directly into my priority queue object
Anshul
And 1st approach inserting in vector and then building heap
Anonymous
And 1st approach inserting in vector and then building heap
Ok for 3 elements, your 1st approach will be O(N)
For your 2nd approach, it will be O(N lg N).
This doesn't mean the 2nd method should never be used. A priority queue is useful when elements are processed as and when they arrive
If you can wait for all the elements to arrive and then start processing them, then using a vector to gather the elements and then building the heap will be more efficient.
Anshul
"It will be O(n^2) if you try to do it directly."
How?
Should it not be O(nlogn).
Building heap O(nlogn)
Extracting each element O(logn)
Extracting n/2 element O(nlogn)
Anonymous
"It will be O(n^2) if you try to do it directly."
How?
Should it not be O(nlogn).
Building heap O(nlogn)
Extracting each element O(logn)
Extracting n/2 element O(nlogn)
When you said "directly", I thought you meant scanning the array sequentially to determine the max elements.
Anshul
Thanks I understood it now.
Alex
Hi. do you know c++ string class for utf8? like QString str;
str[5] - got 5th codepoint, not byte. QString is not the option cause QChar is 16 bit width only. Also I don`t need recalculcation for every operator[] call. just get offset from uint32 array
Anonymous
Hi. do you know c++ string class for utf8? like QString str;
str[5] - got 5th codepoint, not byte. QString is not the option cause QChar is 16 bit width only. Also I don`t need recalculcation for every operator[] call. just get offset from uint32 array
std::u8string
str[5] will not get the 5th code point but the 5th code unit.
Anonymous
I need code point
It is not easy to get code points like that. If you must do that, then you must be willing to get your hands dirty with codecvt and facets. c++ doesn't offer much in the form i18n support or Unicode support. Just offers the bare minimum. You can see if there is some external library available that works well with Unicode strings in c++
Alex
It is not easy to get code points like that. If you must do that, then you must be willing to get your hands dirty with codecvt and facets. c++ doesn't offer much in the form i18n support or Unicode support. Just offers the bare minimum. You can see if there is some external library available that works well with Unicode strings in c++
I know. I don`t ask about std c++. maybe someone knows implementation like QString from github etc
A
Hello everyone, I want to ask about my code problem. When I run this program, it just show nothing.
A
#include <iostream>
#include <string>
#include <vector>
std::string DNAStrand(std::string dna)
{
int trA = dna.find("A");
int trT = dna.find("T");
int trC = dna.find("C");
int trG = dna.find("G");
bool tf = true;
while(tf) {
if(dna.find("A") != std::string::npos) {
dna.replace(trA, 1, "T");
dna.find("A");
} else if(dna.find("T") != std::string::npos) {
dna.replace(trT, 1, "A");
dna.find("T");
} else if(dna.find("C") != std::string::npos) {
dna.replace(trC, 1, "G");
dna.find("C");
} else if(dna.find("G") != std::string::npos) {
dna.replace(trG, 1, "C");
dna.find("G");
} else {
tf = false;
}
}
return dna;
}
int main() {
std::string word = "AAAA";
DNAStrand(word);
std::cout << word;
}
Ⓥovaꑭ
who knows how to make code from a mathematical expression?
Nishantha
Yes