useful simple C/C++ facts for programming contests .

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

1- every variable declared outside of functions are static and have the default value of zero(0) .

int dp[100];
bool vis[100];
struct point { int x,y; }; 
point ps[100];
int main(){
   // all elements of dp are zero by default
   // all elements of vis are false
   // all points have x == 0 and y == 0
}

2- , is an operator and returns its rightmost statement value , for example if A and B be statements (A,B) == B .

if,for,while without a block { } take one statement so you can simply write multiple statements separated bye ,

int main() {
    int a = 1, b = 2;
    int c = a,b; // c == 2
    int A[100];
    int sumA = 0;
    for(int i = 0; i < 100; ++i)
        cin >> A[i],
        sumA += A[i];
}

3- if you declare an array inside a function the value of its elements are garbage , but if you write TYPE var[LEN] = { }; all elements will be zero by default.

int main(){
   int A[100] ; // elements of A have garbage values
   int B[100] = { } ; // all elements of B are zero 
}

4- memset is defined in <string.h> and sets the bye values of a block of memory . you can use memset to initialize all elements of an integer array to 0 or -1 but not the other values .

int main(){
   int A[100];
   memset(A,0,sizeof(A)); // all elements of A are zero
   memset(A,-1,sizeof(A)); // all elements of A are -1

   //NOT WORKING
   memset(A,other_numbers,sizeof(A)); // WRONG
}

help me update this post with other useful facts . have fun !

int A[3] = {1, 2, 3}; int B[5] = {2, 1}; // this will initialize all other elements to 0, so B is {2, 1, 0, 0, 0} vector <int> v {1, 2, 3, 4, 5}; map <string, int> M { {"bbb",1}, {"aaa",2} }; // creates a map like M["aaa"] = 2, M["bbb"] = 1

int main(){ int a[1000] ; fill(a , a+1000 , 2000000000 ) ; // fill 2000000000 into array a[] int b[139][201] ; fill(&b[0][0] , &b[0][0] + 139 * 201 , 2000000000 ) ; // fill 2000000000 into array b[][] vector<int> v (1000); fill(v.begin() , v.end() , 2000000000 ) ; // fill 2000000000 into vector<int> v int c[17][32][54] ; fill(&c[0][0][0] , &c[0][0][0] + 17 * 32 * 54 , 2000000000 ) ; // fill 2000000000 into array c[][][] }

int A[1000 * 1000 * 100]; clock_t clk; int main() { clk = clock(); memset(A, -1, sizeof(A)); printf("CPU Clocks : %d\n", clock() - clk); clk = clock(); fill(A, A + 1000 * 1000 * 100, -1); printf("CPU Clocks : %d\n", clock() - clk); return 0; } /* Output CPU Clocks : 299 CPU Clocks : 1317 */

Комментарии (34)

Написать комментарий?

Gassa

11 лет назад, # |

+28

Actually, you can memset correctly with 256 different values, for example, 0x3F3F3F3F.

→ Ответить

000golabi

11 лет назад, # ^ |

humm , right (tnx) .

caustique

← Rev. 2 →

So what's the point to use such complex constants where you can make mistake — isn't it easier to just iterate and assign all values?

totally agree ! :)

This particular constant can be used as an infinity in some contest solutions.

-8

actually it think you mean 0x7F .

int A[10]; memset(A, 0x7F, sizeof(A));
// A[i] == INT_MAX

No, I don't. Often I'd like the following to not overflow:

int a = INF, b = INF, c = INF;
a = min (a, b + c);

It's summing two values which can be infinities.

Having to add up three or more values which can all be infinities is much less frequent.

riadwaw

+13

A[i] != INT_MAX, btw

you are right .

A[i] = 2139062143 and INT_MAX = 2147483647

can i initialize to INT_MAX ?

no way with memset. you may use std::fill

Baklazan

I think it's even easier to use std::vector and its constructor, for most cases.

ilovealyona

-20

насколько я помню, в данном случае

for(int i = 0; i < 100; ++i)
        cin >> A[i],
        sumA += A[i];

порядок выполнения операций, разделенных запятой, вообще говоря, не определен, и может возникнуть очевидный фэйл. насколько я прав?

Fefer_Ivan

Запятая — это sequence point. Это значит, что порядок выполнения определен. Сначала то, что слева, потом то, что справа. То же самое верно для операторов && и ||. Подробнее: http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points

k790alex

I didn't know about this one:

I tried in java but doesn't work.

← Rev. 4 →

I don't know about Java , its all about C/C++ .

Kvark161

+36

I use fill() to initialize elements to any values. It's defined in <algorithm>.

int main() {
   int A[100];
   fill(A, A + 100, 7); // A[i] = 7, 0 <= i <= 99
}

Break-Neck

About memset: 0 and -1 work normal because memset fills bytes with a value, and 0 is "00…000", (-1) is "11…111" in binary format, so all bytes in (usually) int are filled like in a single char. So, if you use one-byte types (like [unsigned] char) you can use memset for any value (once I used it trying to avoid TL as std::fill works a little slower).

Igel_SK

About int B[100] = {}; You can also initialize like this arrays and STL containers to the custom sequence of values. This is true for C++11.

this works for arrays even without C++11:

int A[5] = { 1 , 2 }; // A will be {1,2,0,0,0}

Xellos

Arrays not initialized to zeroes, memset, various other stuff... what about vector<>s? You can resize them at initialization...

*insert trollface here*

yeputons

Yes, you can. vector<>s are initialized with default values (which is zero for embedded types), but it's done with something like fill, so memset is definetely not slower (I think it should be even faster, because it can set memory by very big blocks using CPU vector operations instead of just int-by-int filling).

I see. Still, it doesn't really hurt in a programming contest, unless the time limits are really tight.

kien_coi_1997

The 1st, 2nd, 4th tips are very basic. But this is the first time I see the third tip.

amirMD

← Rev. 3 →

fill form include string.h is more faster than memset and you can fill any value you want into arrays , vectors , etc . Examples :

No its not !

Edit: the data is not relevant, see the comment below.

It depends on the optimization level. With MinGW GCC 4.8.1:

(optimization flag: memset / fill)

-O0: 155 / 281
-O1: 148 /  56
-O2: 135 /  56
-O3: 140 /  22

The usual choice for programming contests is -O2.

310/63 for /Ox in VS 2013 . No more memset , i'm gonna use fill .

Ouch, sorry! The above's all wrong. The reason is that the whole benchmark is flawed. The first method actually accounts for allocations, too. Swap them, and you get the opposite picture.

Here's a more relevant one. With -O2, memset is 2x faster. With -O3, there's hardly a difference.

"The first method actually accounts for allocations, too. Swap them, and you get the opposite picture." ???

can you explain a little bit ! (allocation ? Swap ??)

In your program above, swap the lines with fill and memset. The timings will be different, at least they are when I do it locally.

andreyv

I don't think this is a good test case, because the compiler can optimize out calls to memset/fill.

No, the strange results are because the benchmark was flawed (see above).

std::fill is from <algorithm>
It will typically be slightly slower than memset() in most cases, equal in some cases (char/wchar_t), but almost never faster than memset().

Zlobober

Maybe he meant that "fill" is 2 characters shorter then "memcpy"?

Блог пользователя 000golabi