Feeds:
Posts
Comments

Posts Tagged ‘stl’

whenever possible one should use the standard library tools provided. std::mismatch() returns a pair of iterators to the first mismatch. examples of this are abundant on the WWW but i wanted to find all the mismatches and could not find an example online, hence this post. i don’t think the code is elegant so please let me know better versions of my code.

#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
  std::vector<unsigned> a = {1,2,3,4,5,6};
  std::vector<unsigned> b = {1,2,33,4,55,66};
 
  // find the first mismatch
  auto p = std::mismatch(a.begin(), a.end(), b.begin());

  while(p.first != a.end())
    {
      std::cout << *p.first << std::endl;
      std::cout << *p.second << std::endl;
      p = std::mismatch(++p.first, a.end(), ++p.second);
    }
 
return 0;
}

havent’ tried the above on list container but i believe list iterators support the increment operator.

don’t forget to compile the above using -std=c++0x

Read Full Post »

erase set_difference idiom stl c++

[UPDATE] 03Jan2011 : Please note that the following works ONLY because a and b are “sorted” already

say we have two sets

a = [1,2,34]

and

b = [2,4]

and i want to perform the set difference operation:

a = a/b OR a = a-b

that is remove from a the elements that are also present in b.

then is the following c++ solution valid?

 a.erase(set_difference(a.begin(), a.end(), b.begin(), b.end(), a.begin()), a.end());

i noticed that the following

 set_difference(a.begin(), a.end(), b.begin(), b.end(), a.begin());

changed a in to

[1,3,3,4]

and returned an iterator to the 3 to the left of 4. this remined me of the erase-remove idiom hence this post.

is it ok to do this?

Read Full Post »

many numerical software and libraries handle multidimensional arrays as a single dimension array. i don’t know why but i don’t like to write

a[i*numCols+j]

instead of

a[i][j]

so i resort to using multidimensional versions of stl containers. i wonder why it is not used.

this is how i store a matrix with 4 rows and 3 columns.

// declaration and memory allocation done together
std::vector <std::vector <double > > matrix(4, std::vector<double>(3));

that creates a vector of vector.

however one can also resize the vector later after an initial declaration. up until now i only resized one-dimensional vectors but here is how one can resize multi-dimensional vectors.

// declaration alone
std::vector <std::vector<double> > matrix;
// blah blah
// 
//
// now for memory allocation
matrix.resize(4, std::vector<double>(3));

Read Full Post »

it is possible to specify your own random number generator to be used with std::random_shuffle() which accepts either of the following:
0) function object a.k.a functor
1) pointer to a function

this article will use the pointer to a function approach.

first we create a unary function that accepts an appropriate type of argument. by appropriate i mean a type which is convertible from std::iterator_traits::difference_type. we will be using the gsl_rng_uniform_int() function provided by the GSL library.

long unsigned myrng(long unsigned n)
{
  return gsl_rng_uniform_int(rng, n);
}

notice how using myrng() we will be able to call a binary function using a unary interface. of course one must ensure that the variable rng is globally defined.

now that we have defined the unary function we need to define a pointer to this function, which we will pass to the
std::random_shuffle() function.

this is how we achieve that

long unsigned (*fp)(long unsigned) = myrng;

all the parts are in place for the final working program which is listed below:

#include <vector>

#include <gsl/gsl_rng.h>
// for gsl_rng_uniform_int

#include <algorithm>
// for random_shuffle

// global definition
gsl_rng * rng;

// unary function 
long unsigned myrng(long unsigned n)
{
  return gsl_rng_uniform_int(rng, n);
}

// pointer to unary function
long unsigned (*fp)(long unsigned) = myrng;

int main()
{
  rng = gsl_rng_alloc(gsl_rng_default);

  // [1.0, 2.0, 3.0, 4.0]
  std::vector <double> a;
  a.push_back(1.0);
  a.push_back(2.0);
  a.push_back(3.0);
  a.push_back(4.0);

  std::random_shuffle(a.begin(), a.end(), fp);

  gsl_rng_free(rng);

  return 0;
  }

i m not too happy with this implementation as this uses a global definition of gsl_rng *. i will also try to write a version using functors at a later date.

Read Full Post »

this is the program


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

int main()
{
 // 2-dimensional array
 std::vector <std::vector <double> > d2;

 // [1.0, 1.0, 1.0, 1.0]
 std::vector <double> vecOne(4, 1.0);

 // [2.0, 2.0, 2.0, 2.0]
 std::vector <double> vecTwo(4, 2.0);

 //[ ] empty vector
 std::vector <double> blank;

 // fill up the 2-dim array
 d2.push_back(blank);
 d2.push_back(blank);
 d2.push_back(vecOne);
 d2.push_back(blank);
 d2.push_back(vecTwo);
 d2.push_back(blank);
 d2.push_back(blank);

 // search for the first non-empty element in the 2-dim array
 std::vector <std::vector <double> >::iterator iter;
 iter = find_if(d2.begin(), d2.end(), std::not1(std::mem_fun_ref(&std::vector<double>::empty)));

 // print the content of vector to standard output
 std::copy(iter->begin(), iter->end(), std::ostream_iterator<double>(std::cout, "\t"));

 return 0;
}

  1. i wanted to implement a 2 dimensional array. i could have implemented it as a class but i have used a nested container of a vector of a vector. i do not know if this is a good way to implement multi-dimensional matrices in terms of speed or efficiency. let me know in the comments.
  2. i could have used a for loop to iterate thru and using the empty() member function of the vector container class i could have determined the non-empty vector. however i chose not to do this. i instead chose the find_if() function to help me with the task.
  3. find_if(startIterator, endIterator, predicateFunction) returns an iterator to the position where predicateFunction is boolean true otherwise it returns end().
  4. mem_fun_ref() allows one to use a member function of the container class to be used. the member function that we want to use is empty(). and mem_fun_ref() will allow us to use it within find_if().
  5. we want to find the non-empty vector which means we really want something like not_empty() instead of the member function empty(). the function not1() comes to our rescue here. it boolean inverts a unary predicate function : find_if(startIterator, endIterator,  std::not1(predicateFunction))
  6. the container std::vector have a member function called std::vector<double>::empty(). we pass a reference to it to mem_fun_ref() to get std::mem_fun_ref(&std::vector<double>::empty))

that is it 🙂

many many thanks to the lovely people over at the ##c++-basic irc channel who have helped me tremendously.

Read Full Post »