lovro-sinda's blog

List of 10 programming questions that I alwasys want to ask
By lovro-sinda, 10 years ago, In English

  1. In certain problems we can use an array of integers to solve the problem. But those can also be solved by using array of vectors. On which factors should I decide whether to use plain array of integers or array of vectors? If vectors, then what are the advantages?

  2. Can function write in C++ return more than one values?

  3. Can anyone tell me whats exact stack limit for c++ and can we increase it in some way from code?

  4. Is true that vector increasing size by 2,4,8,16...? If it is are vector still increasing after will write resize?

  5. What is complexity of memset(C++)? Is that faster then BF method?

  6. In what type of data do you keep binary tree at your C++ program? And what is the best way to do it?

  7. Is there any difference between char, string, vector in time complexity of processing(input, output...)?

  8. I read about function nth_element on STL. Can anyone help me to implement it because how I can understand it's cool function in linear time complexity.

  9. What is the difference between I write double pi = 3.14159; or #define pi 3.14159?

  10. Is there any link on the Internet on page or book title like: "Hasing for dummies "

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

Comments Comments (25)
| Write comment?
»
10 years ago, # |
← Rev. 14   Vote: I like it +3 Vote: I do not like it

2.Yes

vector<int> func(){
    vector<int> ans;
    //do stuff
    return ans;
 }
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    actually it's one value .

    2.No C++ functions return at most one variable , but there is some tricks :

    a-passing variable by reference , change them in the function as you want .

    b-return pair<type1,type2> or tuple

    c-pointers [to an array for example]

    (and of course vectors and maps and ... any collection ) and like so .

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

      Thank you! I didn't know about tuple

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

        Welcome , tuple is since c++11 only , using templates list of types[this list is infinite like in printf] which is also new in c++11.

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

      Let's say that you have function that need to calculate sum and product of two numbers. You can do that by using pointers: http://pastebin.com/KACm8QNT With that, you are not returning values with function (you are actually pointing at memory), but it's can be useful when you need to do several operation in the function like i mention above.

      → Reply
»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it

What is the difference between I write int pi = 3.14159; or #define pi 3.14159?

Easy. The first pi equals 3, the second could possibly be used as a floating point value. :P

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

9.

double pi = 3.14159 : this is a variable that reserve a 64bit memory , and you can change it inside the program [in short : it's a variable]

#define pi 3.14159 : this is a compiler command , that substitute every word pi by 3.14159 , it's the same to make an CTRL+H to replace every pi with 3.14159 , think about it like a shortcut

have a look for this :

#include<cstdio>
#define ICPC puts("Hello World");
#define ACM  int main(){
#define CF   }
ACM ICPC CF

Hope I helped

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

    What is difference about memory use?

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

      no memory use for #define it's one of the very first steps of compilation

      It's A PRE-processor's job , no memory used because no variable reserve space .

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

10 . this link

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
  1. When you are using arrays, you must declare how many elements you need while in vector you don't need. Vectors have some useful functions that can be extremely useful in some problems vec.back(), vec.erase(), vec.size() and others. To be more accurate, use vectors when you need direct access to any elements in sequence (adding, removing).

In problems when you need to manipulate with sequence without adding and removing items, I think that it's same if you use vector or array.

→ Reply
»
10 years ago, # |
  Vote: I like it -55 Vote: I do not like it

I think that you don't like to read books and sources...

  1. Well, if you mean structs for 2D or 3D vectors, then read about structs and classes in any good book about C++.
  2. Read any good book about C++.
  3. Read the documentation to the compiler you use.
  4. Read the source codes of your compiler's standard library (it's available at least for GCC and MSVC).
  5. The same as for question 4.
  6. The same as for question 4 (look at the implementation of set/map).
  7. The same as for question 4.
  8. The same as for question 4.
  9. The same as for question 2.
  10. www.google.com
→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +41 Vote: I do not like it

4) No, vector increasing size by 2,22,228, and not increasing more

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

  1. Vectors offer you the ability to resize. If you are uncertain how much memory you will need beforehand, or you need something like pop_back, insert or erase, you should go for a vector. Otherwise, if you only need a plain array with a fixed number of elements, an array works faster than a vector and you should use it.

  2. Return a vector or a pair

  3. I don't believe you can increase it from code (at least for these competitions). This differs between every programming competition website. CodeForces has 256 MB available (source)

  4. Yes. When vector needs more memory than it has currently reserved, it resizes and allocates double the memory it currently uses. If you resize it manually, it can still resize itself if you need more memory (example if you resize it to 10,000, you insert 10,000 members and you decide to push_back again).

  5. Memset operates on a very low level and is therefore much faster, but I am not completely certain how stable is it. If there's any case when you can't use memset, std::fill is faster than a BF with for.

  6. Just like vector vs array, more primitive types work faster (which means char would be a bit faster here)

  7. The first one (double pi = 3.14159) defines it as a variable of type double and stores it in memory while the second one just replaces all instances of pi with 3.14159 in the text. I doubt you could see any difference between the two.

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

    4) Nope. That depends on compiler which growth factor to use. For example for Visual Studio C++ compiler it is 1.5.

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

      Some times ago I've read the following idea on Usenet. By doing some maths, it might look better to use a growth factor less than the golden ratio φ. Let C be the initial allocation and x the growth factor. Then the allocated memory will be C, Cx, Cx2, ... At the n-th allocation, we know that there are of previously freed memory. We would like to reuse that memory for the next allocation of Cxn + 1. The inequation is equivalent to , and thus xn - 1 - xn + 2 + xn + 1 ≥ 0. By dividing by xn we get . As n becomes large, becomes negligible, so that we get the well known inequation  - x2 + x + 1 ≥ 0. Finally . In pratice the growth factor 1.5 is quite easy to code (just a statement like size += size / 2). Of course it's still theory.

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

For #6, it's really up to you. I would use something like the following:

struct node
{
    node* left;
    node* right;
};

For #10, I think the Wikipedia article is pretty good: http://en.wikipedia.org/wiki/Hash_table

→ Reply
»
10 years ago, # |
← Rev. 6   Vote: I like it +11 Vote: I do not like it

  1. Vectors are generally used when you don't know the number of elements in advance (for example generate all prime numbers between 1 and 100000 and other similar problems). Vectors are also used (at least by me) in graph representation. Suppose you have 100000 vertices in a graph and the graph has about 500000 edges in total. Then to represent adjacencies in the graph you'd need a matrix of size 100000 x 100000 or you can simply use 100000 vectors each of varying size (one vertex can have 5 adjacencies, another one 500, another 12424...).

  2. It can return only one variable, however that variable can also be container for other variables. For example a vector or a pair.

  3. Depends on your system, but default usually isn't more than 8MB (on codeforces it's 256MB). To increase it you can either increase in the OS itself, or at compile time (depending on what compiler you use). For example in g++ you can use --stack=X, where X is the number of bytes. It's similar in visual c++.

  4. Vector has size (current number of elements in it) and capacity (number of storage spaces allocated to it). If you want to push_back a new element and size < capacity then that element is simply added to the vector. If size == capacity then vector's capacity increase by about 2X (compiler implementation dependant) and the old stuff get's copied to the new vector. If you call resize(x, n) that would simply mean that vector's size (not capacity) becomes n, and any index larger than the current vectors size becomes filled with x. If you know in advance the number of elements that should be in a vector then you should call reserve() function (which changes vector capacity).

  5. Memory in a computer is represented in binary system bit by bit. If you have an array of short ints(2 bytes) for example arr[] = {1, 3} than in binary that is written in memory as "00000000000000010000000000000011". Note that the entire length of this memory segment is 4bytes. So if you call memset(arr, x, 4), 4 bytes will be filled, byte by byte with value x. Value x is in range 0-255 (if it's not it gets converted to unsigned char). So for example if we call memset(arr, 127, 3) (127 = 01111111 in binary) our array becomes "01111111011111110111111100000011" (arr[] = {32639, 32515}. This is way faster than changing numbers individually. You should also read about representations of signed and unsigned numbers here.

  6. Usually people(including me) use array (indexed from 1 to N, N = number of nodes in a complete binary tree) where index i is a parent of 2*i and 2*(i+1). However you can also use an approach with dynamic memory, but many people don't like dynamic memory in programming competitions because it is fairly hard to debug.

  7. String is a class where char[] is, well array of chars. There might be some small overhead in using string vs char[], because it is a class and it has to implement it's own methods and so on... but really for all intents and purpose there shouldn't be any real difference.

  8. Look here and here.

  9. First one replaces every occurrence of pi in your code with 3.14159. So if you have "#define pi 2+1.14159" and then somewhere in your code you write "2*pi" the result is going to be 2*2+1.14159=5.14159 which probably isn't what you've expected. Where as if you write "double pi = 2+1.14159", result of "2*pi" is going to be 6.28318.

  10. This approach is used in programming competitions when it comes to hashing. If you wan't to know more general info about hashing then google and wikipedia.

Apologizes for spelling\grammar errors and I hope i helped :)

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

2) Function in C can return only one value, but nobody said about structures:

struct some_type_t
{
int a;
int b;
};
some_type_t f()
{
some_type_t abc;
return abc;
}

Note that in this case compiller will copy memory of struct.

→ Reply