000golabi's blog

useful simple C/C++ facts for programming contests .
By 000golabi, 11 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

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

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

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

    humm , right (tnx) .

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      totally agree ! :)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it -8 Vote: I do not like it

        actually it think you mean 0x7F .

        int A[10]; memset(A, 0x7F, sizeof(A));
// A[i] == INT_MAX
        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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.

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

          A[i] != INT_MAX, btw

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

            you are right .

            A[i] = 2139062143 and INT_MAX = 2147483647

            can i initialize to INT_MAX ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

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

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

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

      → Reply
»
11 years ago, # |
← 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
»
11 years ago, # |
← 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
»
11 years ago, # |
← 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
»
11 years ago, # |
← 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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this works for arrays even without C++11:

    int A[5] = { 1 , 2 }; // A will be {1,2,0,0,0}
    → Reply
»
11 years ago, # |
  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
  • »
    »
    11 years ago, # ^ |
      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
    • »
      »
      »
      11 years ago, # ^ |
        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
»
11 years ago, # |
  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
»
11 years ago, # |
← 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
  • »
    »
    11 years ago, # ^ |
    ← 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
    • »
      »
      »
      11 years ago, # ^ |
      ← 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
      • »
        »
        »
        »
        11 years ago, # ^ |
          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
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← 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
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              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
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                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
      • »
        »
        »
        »
        11 years ago, # ^ |
          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
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
  • »
    »
    11 years ago, # ^ |
      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
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply