// Testing the Standard Template Library (STL) vector ...
// a vector forms an expandable array that can be reversed, sorted, 
// partitioned, copied, searched, shuffled, unequaled and much more
// a Dev-C++ tested console application by  vegaseat  10dec2004   
 
#include <iostream>
#include <algorithm>  // check stl_algo.h for details
#include <vector>     // vector header
#include <iomanip>    // setw()
#include <iterator>   // ostream_iterator
#include <functional> // bind2nd
#include <string>     // string output 
 
using namespace std;  // std::cout etc.
 
int main()
{
  int k;
  const int N = 10;
  // this is how an array can be initialized
  int ar[N] = { 12, 45, 234, 64, 99, 35, 63, 23, 17, 55 };
  // it was too simple for the folks who created the vector,
  // but you can use the array to initialize the vector, note
  // (ar, ar+N) dimensions vector iV and loads it with N elements
  vector<int> iV(ar, ar+N);
  cout << "vector initialized with an array:\n";
  // display it, similar to the array
  for(k = 0; k < iV.size(); k++)
  { 
    cout << setw(5) << iV[k];
  } 
  cout << endl;
 
  // a more intuitive method with a loop like the display loop
  // you can use this method because vector iV is dimensioned
  for(k = 0; k < iV.size(); k++)
  {
    iV[k] = ar[k];
  }
  cout << "vector loop-initialized with an array:\n";
  // should give the same display
  for(k = 0; k < iV.size(); k++)
  { 
    cout << setw(5) << iV[k];
  } 
  cout << endl;
 
  // you can initialize a vector with an existing vector
  vector<int> iV3 = iV;
  cout << "one vector initialized with another vector:\n";
  // display it, similar to the array
  for(k = 0; k < iV3.size(); k++)
  { 
    cout << setw(5) << iV3[k];
  } 
  cout << endl;
 
  // find the value 99 in the vector 
  vector<int>::iterator iter = find(iV.begin(), iV.end(), 99);
  if (iter == iV.end())
  {
    cout << "99 not found\n";
  }
  else
  {
    cout << "found 99 at element " << iter - iV.begin() << " (starts at 0)\n";
  }
  // advance the iterator 4 positions
  advance(iter, 4);
  cout << "element " << iter - iV.begin() << " has value of " << *iter;
  cout << endl;
 
  // another way to load a vector ...
  vector<char> cV(50, '-');
  cout << "this vector has 50 char - :\n";
  for(k = 0; k < cV.size(); k++)
  { 
    cout << cV[k]; 
  }
  cout << endl;
 
  // insert some additional elements
  cout << "inserted 10 char c starting with element 25:\n";
  cV.insert(cV.begin() + 25, 10, 'c');   
  for(k = 0; k < cV.size(); k++)
  { 
    cout << cV[k];
  } 
  cout << endl;
 
  // take the character vector and shuffle the characters
  cout << "let's shuffle the thing ...\n";
  random_shuffle(cV.rbegin(), cV.rend()); 
  for(k = 0; k < cV.size(); k++)
  { 
    cout << cV[k];
  } 
  cout << endl;  
 
  // how many elements can a vector hold?
  // a huge number, actually until memory runs out!
  // well, let's test it to a million elements ...
  vector<int> kV;
  cout << "loading an integer vector with numbers 0 to 999999 ...\n";
  for(k = 0; k < 1000000; k++)
  {
    kV.push_back(k);
  }
  cout << "content of element 123456 = " << kV[123456] << endl;  
  cout << "content of element 999999 = " << kV[999999] << endl;
 
  // create a vector for doubles
  vector<double> dV;
  double d; 
  // load a vector from the keyboard 
  cout << "Enter some floating point numbers (q to quit)\n";
  // actually, any non-numeric char will exit the loop
  while(cin >> d)
  {
    // push_back() appends the vector dV and also expands dV
    // so you don't have to predimension the vector!!!!
    dV.push_back(d);
  } 
 
  // number of elements in the vector
  cout << "counted " << dV.size() << " elements\n";
 
  if (dV.empty())
  {
    cout << "... cannot process an empty vector so I made one up:\n";
    dV.push_back(99.9);
    dV.push_back(7.1);
    dV.push_back(39.4);
    dV.push_back(72.0); 
  }
 
  cout << "elements in the order they were entered:\n";
  // display the entered elements
  for(k = 0; k < dV.size(); k++)
  { 
    cout << dV[k] << '\n';  
  }
  cout << "elements in reverse order:\n";
  reverse(dV.begin(), dV.end());
  // display the reversed order elements
  for(k = 0; k < dV.size(); k++)
  { 
    cout << dV[k] << '\n';
  }
 
  // find min and max values
  cout << "Min val is " << *min_element(dV.begin(), dV.end()) << endl;
  cout << "Max val is " << *max_element(dV.begin(), dV.end()) << endl;
 
  cout << "elements sorted:\n";
  sort(dV.begin(), dV.end());
  // display the sorted elements
  for(k = 0; k < dV.size(); k++)
  { 
    cout << dV[k] << '\n';
  } 
  cout << "could have picked min/max=begin/end from the sorted vector:\n";
  cout << "Min val is " << dV.front() << endl;
  cout << "Max val is " << dV.back() << endl;
 
  // create a vector for integers
  vector<int> iV1;
  // load the vector with 20 random integers (0 - 200)
  for(k = 0; k < 20; k++)
  {
    iV1.push_back(rand() % 200);
  }
  cout << "20 random integers:\n";
  // display the random integer elements
  for(k = 0; k < iV1.size(); k++)
  { 
    cout << setw(8) << iV1[k];
  } 
  cout << endl;
 
  // extract values less than 100 from vector iV using partition()
  // create an iterator (pointer) for an integer vector
  vector<int>::iterator itpV;
  cout << "partition elements with value < 100 :\n";
  // move all values < 100 to the front and point to partition end
  // bind2nd() converts a binary function to a unary function
  itpV = partition(iV1.begin(), iV1.end(), bind2nd(less<int>(),100));
  // display the partitioned vector
  for(k = 0; k < iV1.size(); k++)
  { 
    cout << setw(8) << iV1[k]; 
  }
  cout << endl;  
  // create a second vector to hold partioned elements
  vector<int> iV2;
  cout << "copy partioned elements to a new vector:\n";
  // copy partitioned elements to the new vector iV2
  copy(iV1.begin(), itpV, back_inserter(iV2));
  // display the new vector with the values < 100
  for(k = 0; k < iV2.size(); k++)
  { 
    cout << setw(8) << iV2[k]; 
  }
  cout << endl << endl;
 
  // load another integer vector with an array
  cout << "load a vector with an array:\n";
  int b[] = {0, 1, 2, 3, 4, 3, 4, 5, 6, 4};
  // using (array, array + NumberOfElements)
  vector<int> iV4(b, b + sizeof(b)/sizeof(int));
  cout << "number of elements = " << sizeof(b)/sizeof(int) << endl;
  for(k = 0; k < iV4.size(); k++)
  { 
    cout << setw(8) << iV4[k]; 
  }
  cout << endl;
 
  // remove the duplicates with sort(), erase() and unique()
  cout << "removed the duplicate elements:\n";
  sort( iV4.begin(), iV4.end() );
  iV4.erase( unique( iV4.begin(), iV4.end() ), iV4.end() );
  for(k = 0; k < iV4.size(); k++)
  { 
    cout << setw(8) << iV4[k]; 
  }
  cout << endl; 
 
  // Now on to a string vector
  // Just an example of a dimensioned vector (space for 4 strings),
  // later followed by expansion.
  // Don't get confused here ...
  // if you don't want to dimension the vector, use vector<string> sV
  // and load with sV.push_back() from the beginning
  //
  vector<string> sV(4);
  // load it ... 
  sV[0] = "red";
  sV[1] = "green";
  sV[2] = "yellow";
  sV[3] = "blue";
  // you will exceed 4 strings, push_back() takes care of this! 
  sV.push_back("purple");
  sV.push_back("bisque");
  cout << "display vector elements via ostream_iterator:\n";
  // just a different way to write out the elements
  // pipe to std::cout or, if you want, to a file
  copy(sV.begin(), sV.end(), ostream_iterator<string>(cout,"   ")); 
  cout << endl << endl;
 
  // create an iterator (pointer) for a string vector 
  vector<string>::iterator itsV;
  cout << "searching the vector for blue (elements start with 0)\n";
  // you can use  +=, --, -=, ++ operators, and comparison
  // operators <, <=, >, >=, ==, !=  with vector iterators  
  for(itsV = sV.begin(); itsV < sV.end(); itsV++)
  {
    // search using comparison operators
    if (*itsV == "blue")
    {
      cout << "found blue in element " << itsV - sV.begin() << "\n\n";
    }
  }
  // remove those remaining \n char, thanks to ~s.o.s~   
  cin.clear();
  cin.ignore(std::numeric_limits<streamsize>::max(),'\n');
  cin.get(); // console keypress wait
 
  return 0;
}