Use std::vector::iterator to alter values stored in std::vector?

Question

I'm new to C++, and am trying to implement the Selection Sort Algorithm as an exercise.

I've gotten as far as trying to swap the value in the left-most memory location with the value in the memory location of the minimum of the unsorted portion of the vector.

( See the code below. )

Is it possible to use std::vector::iterator's to alter the values contained in the vector it belongs to?

#include <vector>
#include <stdlib.h>
#include <time.h>
#include <iostream>

using namespace std;

template<typename T>
ostream& operator<<( ostream& out, vector<T> thisVector ) {

  for( size_t i = 0, choke = thisVector.size(); i < choke; i++ )
    out << thisVector[ i ] << " ";

  return out;
}

template<typename T>
typename vector<T>::iterator get_minimum( vector<T>& thisVector, typename vector<T>::iterator pos, typename vector<T>::iterator end ) {

  T min = *pos;
  typename vector<T>::iterator minPos;

  while ( pos != end ) {
    if ( *pos < min ) {
      min = *pos;
      minPos = pos;
    }
    pos++;
  }
  return minPos;
}

template<typename T>
void swap( typename vector<T>::iterator pos, typename vector<T>::iterator& minPos ) {

  T temp = *pos;

  // I was hoping the following two lines would modify the vector passed to selection_sort
  pos = *minPos;
  minPos = temp;
  return;
}

template<typename T>
void selection_sort( vector<T>& thisVector, typename vector<T>::iterator pos ) {

  typename vector<T>::iterator end = thisVector.end();
  typename vector<T>::iterator minPos = get_minimum( thisVector, pos, end );
  cout << "Swap was given this " << *pos << " " << *minPos << endl;
  swap( pos, minPos );
  cout << "and returned this " << *pos << " " << *minPos << endl;
  return;
}

int main() {

  // initialize random seed
  srand (time(NULL));

  // Create data stub
  vector<int> myThing;
  do {
    myThing.push_back( rand() % 20 );
  } while ( myThing.size() <= 10 );

  cout << "Unsorted: " << myThing << endl;
  selection_sort( myThing, myThing.begin() );
  cout << "  Sorted: " << myThing << endl;

  return 0;
}

Answer 1

The problem that you are facing with swapping the values the iterators point to is caused by the fact that the compiler picks up std::swap by using ADL. std::swap just swaps where the iterators point to but not the values the iterators point to.

If you name the function myswap and call myswap instead of swap, you are probably going to see compiler error messages. Check out my question on the subject.

Instead, if you use:

template<typename Iterator>
void myswap(Iterator pos1,
            Iterator pos2)
{
   auto temp = *pos1;
   *pos1 = *pos2;
   *pos2 = temp;
}

everything should work. Here's a working program, using g++ 4.8.2.

#include <iostream>
#include <vector>
#include <iterator>

template<typename Iterator>
void myswap(Iterator pos1, Iterator pos2)
{
   auto temp = *pos1;
   *pos1 = *pos2;
   *pos2 = temp;
}

void testMyswap()
{
   std::cout << "\nTesting myswap()\n";
   std::vector<int> v{1, 2, 3, 4, 5, 6};

   std::vector<int>::iterator iter = v.begin();
   std::vector<int>::iterator temp = std::next(iter, 2);

   std::cout << "Values iterators point to before swap.\n";
   std::cout << *iter << " " << *temp << std::endl;
   myswap(iter, temp);
   std::cout << "Values iterators point to after swap.\n";
   std::cout << *iter << " " << *temp << std::endl;

   std::cout << "The vector after the swap.\n";
   for ( iter = v.begin(); iter != v.end(); ++iter )
   {
      std::cout << *iter << " ";
   }
   std::cout << std::endl;
}

int main()
{
   testMyswap();
   return 0;
}

Output

Testing myswap()
Values iterators point to before swap.
1 3
Values iterators point to after swap.
3 1
The vector after the swap.
3 2 1 4 5 6