title: performance of array vs. map
body: <p>I have to loop over a subset of elements in a large array where each element point to another one (problem coming from the detection of connected component in a large graph).</p>
  
  <p>My algo is going as follows:
  1. consider 1st element
  2. consider next element as the one pointed by the previous element.
  3. loop until no new element is discover
  4. consider next element not already consider in 1-3, get back to 1.
  Note that the number of elements to consider is much smaller than the total number of elements.</p>
  
  <p>For what I see now, I can either:</p>
  
  <pre><code>//create a map of all element, init all values to 0, set to 1 when consider
  map&lt;int,int&gt; is_set; // is_set.size() will be equal to N
  </code></pre>
  
  <p>or</p>
  
  <pre><code>//create a (too) large array (total size), init to 0 the elements to consider
  int* is_set = (int*)malloc(total_size * sizeof(int)); // is_set length will be total_size&gt;&gt;N
  </code></pre>
  
  <p>I know that accessing keys in map is O(log N) while it's only constant for arrays, but I don't know if malloc is not more costly at the creation while it also requires more memory?</p>