• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 00:10
CEST 06:10
KST 13:10
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL19] Finals Recap: Standing Tall10HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Weekly Cups (June 30 - July 6): Classic Doubles2[BSL20] Non-Korean Championship 4x BSL + 4x China9Flash Announces Hiatus From ASL66Weekly Cups (June 23-29): Reynor in world title form?14FEL Cracov 2025 (July 27) - $8000 live event22
StarCraft 2
General
The GOAT ranking of GOAT rankings The SCII GOAT: A statistical Evaluation Weekly Cups (June 23-29): Reynor in world title form? Weekly Cups (June 30 - July 6): Classic Doubles Program: SC2 / XSplit / OBS Scene Switcher
Tourneys
RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event Sparkling Tuna Cup - Weekly Open Tournament WardiTV Mondays Korean Starcraft League Week 77
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ ASL20 Preliminary Maps [ASL19] Finals Recap: Standing Tall SC uni coach streams logging into betting site Flash Announces Hiatus From ASL
Tourneys
[BSL20] Non-Korean Championship 4x BSL + 4x China [BSL20] Grand Finals - Sunday 20:00 CET CSL Xiamen International Invitational The Casual Games of the Week Thread
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Nintendo Switch Thread Stormgate/Frost Giant Megathread Path of Exile What do you want from future RTS games? Beyond All Reason
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Summer Games Done Quick 2025! Russo-Ukrainian War Thread Stop Killing Games - European Citizens Initiative Summer Games Done Quick 2024!
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
Formula 1 Discussion 2024 - 2025 Football Thread NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
momentary artworks from des…
tankgirl
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Customize Sidebar...

Website Feedback

Closed Threads



Active: 615 users

The Big Programming Thread - Page 863

Forum Index > General Forum
Post a Reply
Prev 1 861 862 863 864 865 1031 Next
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.
Acrofales
Profile Joined August 2010
Spain17971 Posts
March 22 2017 18:33 GMT
#17241
On March 22 2017 19:03 dsyxelic wrote:
oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers

I went with array cause that seemed simpler

k then thinking of it now with some code

def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False


though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison.

this function would run in O(log n)
total O(m log n), m = size of string s for character comparison

or O(|S| log n) with the way you expressed it

Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with.
slmw
Profile Blog Joined October 2010
Finland233 Posts
March 22 2017 18:50 GMT
#17242
On March 23 2017 03:33 Acrofales wrote:
Show nested quote +
On March 22 2017 19:03 dsyxelic wrote:
oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers

I went with array cause that seemed simpler

k then thinking of it now with some code

def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False


though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison.

this function would run in O(log n)
total O(m log n), m = size of string s for character comparison

or O(|S| log n) with the way you expressed it

Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with.


If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)).
Acrofales
Profile Joined August 2010
Spain17971 Posts
Last Edited: 2017-03-22 19:23:23
March 22 2017 19:18 GMT
#17243
On March 23 2017 03:50 slmw wrote:
Show nested quote +
On March 23 2017 03:33 Acrofales wrote:
On March 22 2017 19:03 dsyxelic wrote:
oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers

I went with array cause that seemed simpler

k then thinking of it now with some code

def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False


though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison.

this function would run in O(log n)
total O(m log n), m = size of string s for character comparison

or O(|S| log n) with the way you expressed it

Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with.


If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)).


No you don't. You start with the beginning of the string. Once you're in the part of the array where your bounds match the first X characters, you only compare the X+1st character onwards, etc. Don't feel like writing out the code, because it's finicky and you have to deal with lots of corner cases, but I'll sketch it:

Search string: abcd

Array (with color codes for what the binary search checks, and strikethroughs for parts of string that are skipped):
aaaa
aaab
aaac
abbb
abbc
abcd
abce
abdd
addd
adde
addf
bcde
cccc
cccd
ccde
cddd
cdff
daaa
daba
dabc
ddaa
ddbb
dddd

So we start in the middle:
addf > abcd. But a matched, so we remember that
Next up: middle between start and addf: abbc
abbc < abcd. So now we know that everything between abbc and addf starts with a, so we move the search index up. Moreover, the second char matches too: b matched as well. So we remember that, and from now on skip the first char, so next: bdd
bdd > bcd. b is matched, so we know everything between abbc and abdd matches the first two chars. We once again move the search index up. Next test: cd == cd. We are done.

Thus we don't have to check m characters log n times. We have to check a couple of characters log n times, but m characters at most twice.
slmw
Profile Blog Joined October 2010
Finland233 Posts
March 22 2017 20:24 GMT
#17244
Obviously in the uniformly distributed case it is O(log N) as was established earlier in this thread. However in these types of puzzles we're usually talking about the worst case (and the prevailing question in the thread was whether there is anything better than O(M*log N) for the worst case). Your solution is O(M log N) as well in the worst case. "Couple of characters" and "at most twice" certainly isn't true in the general case.
meadbert
Profile Blog Joined October 2010
United States681 Posts
March 22 2017 20:30 GMT
#17245
On March 23 2017 04:18 Acrofales wrote:
Show nested quote +
On March 23 2017 03:50 slmw wrote:
On March 23 2017 03:33 Acrofales wrote:
On March 22 2017 19:03 dsyxelic wrote:
oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers

I went with array cause that seemed simpler

k then thinking of it now with some code

def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False


though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison.

this function would run in O(log n)
total O(m log n), m = size of string s for character comparison

or O(|S| log n) with the way you expressed it

Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with.


If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)).


No you don't. You start with the beginning of the string. Once you're in the part of the array where your bounds match the first X characters, you only compare the X+1st character onwards, etc. Don't feel like writing out the code, because it's finicky and you have to deal with lots of corner cases, but I'll sketch it:

Search string: abcd

Array (with color codes for what the binary search checks, and strikethroughs for parts of string that are skipped):
aaaa
aaab
aaac
abbb
abbc
abcd
abce
abdd
addd
adde
addf
bcde
cccc
cccd
ccde
cddd
cdff
daaa
daba
dabc
ddaa
ddbb
dddd

So we start in the middle:
addf > abcd. But a matched, so we remember that
Next up: middle between start and addf: abbc
abbc < abcd. So now we know that everything between abbc and addf starts with a, so we move the search index up. Moreover, the second char matches too: b matched as well. So we remember that, and from now on skip the first char, so next: bdd
bdd > bcd. b is matched, so we know everything between abbc and abdd matches the first two chars. We once again move the search index up. Next test: cd == cd. We are done.

Thus we don't have to check m characters log n times. We have to check a couple of characters log n times, but m characters at most twice.

I agree with you in the typical and average case, but the worst case would be O(m*log(n)).
Note that for you algorithm the worst case would be that the string you are looking for is first or last in the list.
Acrofales
Profile Joined August 2010
Spain17971 Posts
March 22 2017 21:04 GMT
#17246
On March 23 2017 05:30 meadbert wrote:
Show nested quote +
On March 23 2017 04:18 Acrofales wrote:
On March 23 2017 03:50 slmw wrote:
On March 23 2017 03:33 Acrofales wrote:
On March 22 2017 19:03 dsyxelic wrote:
oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers

I went with array cause that seemed simpler

k then thinking of it now with some code

def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False


though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison.

this function would run in O(log n)
total O(m log n), m = size of string s for character comparison

or O(|S| log n) with the way you expressed it

Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with.


If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)).


No you don't. You start with the beginning of the string. Once you're in the part of the array where your bounds match the first X characters, you only compare the X+1st character onwards, etc. Don't feel like writing out the code, because it's finicky and you have to deal with lots of corner cases, but I'll sketch it:

Search string: abcd

Array (with color codes for what the binary search checks, and strikethroughs for parts of string that are skipped):
aaaa
aaab
aaac
abbb
abbc
abcd
abce
abdd
addd
adde
addf
bcde
cccc
cccd
ccde
cddd
cdff
daaa
daba
dabc
ddaa
ddbb
dddd

So we start in the middle:
addf > abcd. But a matched, so we remember that
Next up: middle between start and addf: abbc
abbc < abcd. So now we know that everything between abbc and addf starts with a, so we move the search index up. Moreover, the second char matches too: b matched as well. So we remember that, and from now on skip the first char, so next: bdd
bdd > bcd. b is matched, so we know everything between abbc and abdd matches the first two chars. We once again move the search index up. Next test: cd == cd. We are done.

Thus we don't have to check m characters log n times. We have to check a couple of characters log n times, but m characters at most twice.

I agree with you in the typical and average case, but the worst case would be O(m*log(n)).
Note that for you algorithm the worst case would be that the string you are looking for is first or last in the list.


Hmm, you're right. I guess if you have something like:

aaaa

and your array is:

aaaa
aaab
aaac
etc.

You have to check m characters log n times, because you can never establish the baseline. Didn't think that one through. You are completely right.
dsyxelic
Profile Joined May 2010
United States1417 Posts
March 22 2017 22:25 GMT
#17247
thanks yall
was pretty fun thinking about this problem the last 2 days and definitely learned alot. especially about learning to understand the question in the first place x.x
TL/SKT
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
March 26 2017 14:20 GMT
#17248
Going over quiz for wednesday. It has this question

+ Show Spoiler +

What is wrong with the following code?

#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}



I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x?

I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?
waffelz
Profile Blog Joined June 2012
Germany711 Posts
Last Edited: 2017-03-26 14:50:32
March 26 2017 14:35 GMT
#17249
On March 26 2017 23:20 travis wrote:
Going over quiz for wednesday. It has this question

+ Show Spoiler +

What is wrong with the following code?

#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}



I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x?

I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?


Not sure, but:
Since it is a local variable, the moment the programm exists the function, the memory adress still holds the value but is no longer protected and could be used to store a differerent value by another programm and therefore could contain something completely different. Propably unlikely that this happens in the given example but anyways... I feel like there are a lot of coding questions that are just irrelevant as soon as you follow certain best practices... at least for my interview for an internship a while back it was.
RIP "The big travis CS degree thread", taken from us too soon | Honourable forum princess, defended by Rebs-approved white knights
beg
Profile Blog Joined May 2010
991 Posts
Last Edited: 2017-03-26 14:42:36
March 26 2017 14:38 GMT
#17250
On March 26 2017 23:20 travis wrote:
Going over quiz for wednesday. It has this question

+ Show Spoiler +

What is wrong with the following code?

#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}



I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x?

I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?

I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention.

If the code is intended to add 200 to y and return the result, then the mistake is that we're returning x's adress instead of its actual value
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-03-26 14:53:53
March 26 2017 14:41 GMT
#17251
On March 26 2017 23:38 beg wrote:
Show nested quote +
On March 26 2017 23:20 travis wrote:
Going over quiz for wednesday. It has this question

+ Show Spoiler +

What is wrong with the following code?

#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}



I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x?

I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?

I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention.


I don't think it's meant for practical application


ok how about this question:

". Name one advantage of initializing pointer variables to NULL?"

Is an advantage of doing this, that if you don't initialize them to null then if your code doesn't assign them to an address somewhere, and you try to grab the pointer, it may really mess up your program and be hard to debug?

I suppose also if your program is using memory allocation and you free the pointer, it will be no problem if the pointer was initialized to null, but a big problem if it was never initialized.
waffelz
Profile Blog Joined June 2012
Germany711 Posts
March 26 2017 14:52 GMT
#17252
On March 26 2017 23:41 travis wrote:
Show nested quote +
On March 26 2017 23:38 beg wrote:
On March 26 2017 23:20 travis wrote:
Going over quiz for wednesday. It has this question

+ Show Spoiler +

What is wrong with the following code?

#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}



I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x?

I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?

I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention.


I don't think it's meant for practical application


ok how about this question:

". Name one advantage of initializing pointer variables to NULL?"

Is an advantage of doing this, that if you don't initialize them to null then if your code doesn't assign them to an address somewhere, and you try to grab the pointer, it may really mess up your program and be hard to debug?


Yes. This is just a way to minimise the risk of stupid errors. If you don't initialize them with NULL, they could point to pretty much anything and can make debugging a mess since it can lead to inconsistent crashes.
RIP "The big travis CS degree thread", taken from us too soon | Honourable forum princess, defended by Rebs-approved white knights
beg
Profile Blog Joined May 2010
991 Posts
March 26 2017 14:52 GMT
#17253
Yea definitely. Did you see the edit of my last post?
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
March 26 2017 14:56 GMT
#17254
On March 26 2017 23:38 beg wrote:
Show nested quote +
On March 26 2017 23:20 travis wrote:
Going over quiz for wednesday. It has this question

+ Show Spoiler +

What is wrong with the following code?

#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}



I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x?

I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?

I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention.

If the code is intended to add 200 to y and return the result, then the mistake is that we're returning x's adress instead of its actual value


Why is that a problem? P is a pointer.
I mean we could make P an int and change our function and it would probably make more sense, but I don't see why this is a mistake as is.
beg
Profile Blog Joined May 2010
991 Posts
Last Edited: 2017-03-26 15:40:12
March 26 2017 15:24 GMT
#17255
Well shit, I just realized I never fiddled around with pointers to funciton. Nevermind. I'm playing around with it now.

EDIT: Yea you explained it correct in the same post where you asked the question
Blitzkrieg0
Profile Blog Joined August 2010
United States13132 Posts
March 26 2017 15:37 GMT
#17256
On March 26 2017 23:20 travis wrote:
is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?


Imagine if you did something like this instead:

#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
int *w;
p = get_val(y);
w = get_val(100);
printf("%d%d\n", *p, *w);
exit(0);
}


Pretty sure that will break and you can figure out why its bad.
I'll always be your shadow and veil your eyes from states of ain soph aur.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
March 26 2017 15:45 GMT
#17257
Oh blitz that's an excellent example, thank you.

Just to make sure I am on the right page here, the poblem is that when we dereference p and w in our print statement, they are both going to print from the same address, which currently holds the result of get_val(100) ?
Blitzkrieg0
Profile Blog Joined August 2010
United States13132 Posts
Last Edited: 2017-03-26 16:13:17
March 26 2017 16:11 GMT
#17258
On March 27 2017 00:45 travis wrote:
Oh blitz that's an excellent example, thank you.

Just to make sure I am on the right page here, the poblem is that when we dereference p and w in our print statement, they are both going to print from the same address, which currently holds the result of get_val(100) ?


The real problem is undefined behavior. When you're programming you have an expected result and this program does not always return the expected result because you're referencing a pointer that is out of scope. Because the pointer is declared in the function call, it is out of scope after the function ends and can be overwritten.

In the example you provided the print statement was immediately done and it probably wasn't a issue (note that this is still bad, the fact that it could have been wrong is still a problem even though it likely never happens).

In my example, the value is overwritten and the wrong value is printed.

In another example, you could get that memory allocated to another process and cause a segfault by trying to access memory in another process.

Bottom line is that you don't want to write code that can have undefined behavior. You can't know what will happen because it will depend on how the operating system assigns memory when the program is run.
I'll always be your shadow and veil your eyes from states of ain soph aur.
Mr. Wiggles
Profile Blog Joined August 2010
Canada5894 Posts
March 26 2017 16:31 GMT
#17259
On March 27 2017 00:45 travis wrote:
Oh blitz that's an excellent example, thank you.

Just to make sure I am on the right page here, the poblem is that when we dereference p and w in our print statement, they are both going to print from the same address, which currently holds the result of get_val(100) ?

Travis, have you learnt about memory layouts and the call stack yet? This is essentially the underlying reason for why the given program results in undefined behaviour.

https://en.wikipedia.org/wiki/Call_stack

When you call a function, we increment the stack pointer to make room for several things, including local variables of the function. So in your example, we're going to have some address on the stack which points to the local variable 'x'.

When the function terminates, we're going to decrement the stack pointer to where it was before the function was called. Therefore, referring to any of the locals from the function after we've returned now results in undefined behaviour.

Depending on what the function is actually supposed to do, I think the following might have been what was desired:

+ Show Spoiler +

#include <stdio.h>
#include <stdlib.h>

int * get_val(int y)
{
static int x = 200;
x += y;
return &x;
}

int main()
{
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}

you gotta dance
Acrofales
Profile Joined August 2010
Spain17971 Posts
March 26 2017 16:44 GMT
#17260
Regardless of what that code does and is supposed to do, that is some absolutely horrendous coding. I understand asking you general questions that require you to understand C code, but does it really have to be so incredibly shitty?
Prev 1 861 862 863 864 865 1031 Next
Please log in or register to reply.
Live Events Refresh
Next event in 5h 50m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RuFF_SC2 182
ProTech64
StarCraft: Brood War
GuemChi 1098
Leta 417
MaD[AoV]41
Bale 15
Icarus 9
PianO 6
Dota 2
monkeys_forever822
League of Legends
JimRising 789
Counter-Strike
Stewie2K187
Super Smash Bros
Mew2King188
Other Games
summit1g10031
shahzam811
WinterStarcraft345
Maynarde146
SortOf102
NeuroSwarm60
Organizations
Other Games
gamesdonequick43598
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 15 non-featured ]
StarCraft 2
• Berry_CruncH314
• practicex 22
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Lourlo778
Other Games
• Scarra2790
• Shiphtur361
Upcoming Events
Sparkling Tuna Cup
5h 50m
WardiTV European League
11h 50m
MaNa vs sebesdes
Mixu vs Fjant
ByuN vs HeRoMaRinE
ShoWTimE vs goblin
Gerald vs Babymarine
Krystianer vs YoungYakov
PiGosaur Monday
19h 50m
The PondCast
1d 5h
WardiTV European League
1d 7h
Jumy vs NightPhoenix
Percival vs Nicoract
ArT vs HiGhDrA
MaxPax vs Harstem
Scarlett vs Shameless
SKillous vs uThermal
uThermal 2v2 Circuit
1d 11h
Replay Cast
1d 19h
RSL Revival
2 days
ByuN vs SHIN
Clem vs Reynor
Replay Cast
2 days
RSL Revival
3 days
Classic vs Cure
[ Show More ]
FEL
3 days
RSL Revival
4 days
FEL
4 days
FEL
4 days
CSO Cup
4 days
BSL20 Non-Korean Champi…
4 days
Bonyth vs QiaoGege
Dewalt vs Fengzi
Hawk vs Zhanhun
Sziky vs Mihu
Mihu vs QiaoGege
Zhanhun vs Sziky
Fengzi vs Hawk
Sparkling Tuna Cup
5 days
RSL Revival
5 days
FEL
5 days
BSL20 Non-Korean Champi…
5 days
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Liquipedia Results

Completed

BSL Season 20
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
CSL Xiamen Invitational
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.