title: Compute the count of unique values in vector of sorted vectors
body: <p>I have an object of type <code>std::vector&lt;std::vector&lt;size_t&gt;&gt;</code> called <code>v</code>, where each subvector (each <code>std::vector&lt;size_t&gt;</code>) is sorted. I would like to compute a count of how many times each unique <code>size_t</code> of <code>v</code> is found. I was thinking about using a <code>std::map&lt;size_t, size_t&gt;</code> and do something like</p>
  <pre><code>int main()
  {
      const std::vector&lt;std::vector&lt;size_t&gt;&gt; v = {
          {4, 10, 12, 18, 20, 28, 34},
          {4, 12, 18, 20, 28},
          {4, 17, 18, 20, 28},
          {4, 17, 18, 20, 28, 37}
      };
  
  
      std::map&lt;size_t, size_t&gt; counts;
      for (const auto&amp; a : v)
      {
          for (const auto&amp; b : a)
          {
              auto it = counts.lower_bound(b);
              if (it != counts.end() &amp;&amp; !(counts.key_comp()(b, it-&gt;first)))
              {
                  // mut already exist
                  ++(it-&gt;second);
              } else
              {
                  // mut is new
                  counts.insert(it, std::map&lt;size_t, size_t&gt;::value_type(b, 1));
              }
          }   
      }
  
      for (auto it = counts.begin() ; it != counts.end() ; ++it)
          std::cout &lt;&lt; it-&gt;first &lt;&lt; &quot;: &quot; &lt;&lt; it-&gt;second &lt;&lt; &quot;\n&quot;;
  }
  </code></pre>
  <p>, which outputs</p>
  <pre><code>4: 4
  10: 1
  12: 2
  17: 2
  18: 4
  20: 4
  28: 4
  34: 1
  37: 1
  </code></pre>
  <p>as expected.</p>
  <p>In practice, the values are uniformly distributed between 0 and 4e9 hence pushing me into using a <code>std::map</code> instead of a <code>std::vector</code>. If a value is present in one vector it increases the probably for this value to be found again and again in successive vectors hence making insertions relatively rare compared to incrementation of already inserted values. Also, subparts of vectors tend to be identical.</p>
  <p>Is there a better technique? For example, when computing <code>lower_bound</code>, it would be faster to make use of the point of insertion of the previous element as elements are sorted. Something like,</p>
  <pre><code>    for (const auto&amp; a : v)
      {
          MapType::iterator it = a.begin();
          for (const auto&amp; b : a)
          {
              auto it = counts.lower_bound(it, b); // Use `it` to avoid searching in elements that precedes its position
              
              // etc..
          }   
      }
  </code></pre>
  <p>, however I don't think <a href="https://en.cppreference.com/w/cpp/container/map/lower_bound" rel="nofollow noreferrer">std::map::lower_bound</a> can use a <code>from</code> iterator.</p>