000golabi's blog

useful simple C/C++ facts for programming contests .
By 000golabi, 13 years ago, In English

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 !

  • Vote: I like it
  • +65
  • Vote: I do not like it

»
13 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I didn't know about this one:

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

I tried in java but doesn't work.

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it +36 Vote: I do not like it

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
}
→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

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).

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

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.

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
→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

*insert trollface here*

→ Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
13 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
13 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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

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[][][]	
}
→ Reply
  • »
    »
    13 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    No its not !

    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
*/
    → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +9 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

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

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it
    • 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().
    → Reply