title: Comparing two vectors of maps
body: <p>I've got two ways of fetching a bunch of data. The data is stored in a sorted <code>vector&lt;map&lt;string, int&gt; &gt;</code>.</p>
  
  <p>I want to identify whether there are inconsistencies between the two vectors.</p>
  
  <p>What I'm currently doing (pseudo-code):</p>
  
  <pre><code>for i in 0... min(length(vector1), length(vector2)):
      for (k, v) in vector1[i]:
          if v != vector2[i][k]:
              // report that k is bad for index i,
              // with vector1 having v, vector2 having vector2[i][k]
  
  for i in 0... min(length(vector1), length(vector2)):
      for (k, v) in vector2[i]:
          if v != vector1[i][k]:
              // report that k is bad for index i,
              // with vector2 having v, vector1 having vector1[i][k]
  </code></pre>
  
  <p>This works in general, but breaks horribly if <code>vector1</code> has <code>a, b, c, d</code> and <code>vector2</code> has <code>a, b, b1, c, d</code> (it reports brokenness for <code>b1</code>, <code>c</code>, and <code>d</code>). I'm after an algorithm that tells me that there's an extra entry in <code>vector2</code> compared to <code>vector1</code>.</p>
  
  <p>I think I want to do something where when I encountered mismatches entries, I look at the next entries in the second vector, and if a match is found before the end of the second vector, store the index <code>i</code> of the entry found in the second vector, and move to matching the next entry in the first vector, beginning with <code>vector2[i+1]</code>.</p>
  
  <p>Is there a neater way of doing this? Some standard algorithm that I've not come across?</p>
  
  <p>I'm working in C++, so C++ solutions are welcome, but solutions in any language or pseudo-code would also be great.</p>
  
  <h2>Example</h2>
  
  <p>Given the arbitrary map objects: <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code>, <code>e</code>, <code>f</code> and <code>g</code>;</p>
  
  <p>With <code>vector1</code>: <code>a</code>, <code>b</code>, <code>d</code>, <code>e</code>, <code>f</code></p>
  
  <p>and <code>vector2</code>: <code>a</code>, <code>c</code>, <code>e</code>, <code>f</code></p>
  
  <p>I want an algorithm that tells me either:</p>
  
  <blockquote>
    <p>Extra <code>b</code> at index 1 of <code>vector1</code>, and <code>vector2's c != vector1's d</code>.</p>
  </blockquote>
  
  <p>or (I'd view this as an effectively equivalent outcome)</p>
  
  <blockquote>
    <p><code>vector1's b != vector2's c</code> and extra <code>d</code> at index 2 of <code>vector1</code></p>
  </blockquote>
  
  <h1>Edit</h1>
  
  <p>I ended up using <code>std::set_difference</code>, and then doing some matching on the diffs from both sets to work out which entries were similar but different, and which had entries completely absent from the other vector.</p>