Maintaining sorted std::vector

test7.C

// g++ -O3 -std=c++0x -o test test7.C

#include <iostream>
#include <cstdint>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cassert>

using namespace std;

typedef std::vector<uint32_t> Uint32Vector;

bool findInsert( Uint32Vector & vv, uint32_t u ) { 
   Uint32Vector::iterator iter = std::lower_bound( begin( vv ), end( vv ), u );
   if( iter != end( vv ) && *iter == u ) return true;

   // Not found, insert
   vv.insert( iter, u );

   // Not found
   return false;
}

bool testSorted( const Uint32Vector & vv ) { 
   bool first = true;
   uint32_t last;
   for( Uint32Vector::const_iterator iter = begin( vv ); iter != end( vv ); ++iter ) { 
      if( distance( iter, begin( vv ) ) > 0 && last > *iter ) return false;
      last = *iter;
   }   
   return true;
}

int
main( )
{
   uint32_t len = 1000;
   Uint32Vector vv; 
   std::random_device rd; 
   std::mt19937 gen( rd() );
   std::uniform_int_distribution<uint32_t> dis( 1, len );
   for( int ii = 0; ii < 5*len; ++ii ) { 
      size_t oldSize = vv.size();
      bool found = findInsert( vv, dis( gen ) );
      assert( testSorted( vv ) );
      assert( !found || oldSize == vv.size() );
      // copy( begin( vv ), end( vv ), ostream_iterator<uint32_t>( cout, " " ) );
      // cout << "\n\n";
   }   
   return 0 ; 
}