Re: Some proble on " merge() on vector "

gpfei6@gmail.com ha scritto:

You can also use:

  copy(istream_iterator<int>(fin_1), istream_iterator<int>(),
    back_inserter(vi_1));

You can also use:

  copy(vi_1.begin(), vi_1.end(), ostream_iterator<int>(cout, "\t"));

Strictly speaking, it's not needed, but it helps managing memory so that
reallocation does not occur during the execution of merge, possibly
making the algorithm much faster. However I would do this, instead:

  vi_3.reserve(vi_1.size() + vi_2.size());

Notice that this call does *not* change the size of vi_3 which is still
*empty*! In particular vi_3.begin() == vi_3.end() and is *not* a
dereferenceable iterator.


This is completely another story, see below.


No no no! As I said above, vi_3.begin() is not a dereferenceable
iterator (the vector is still empty) so it cannot be used here. You have
to pass a back_inserter iterator, that is an iterator that uses
push_back instead of assignment. Such an iterator will make vi_3 grow
each time merge produces an element. So the correct line is:

  merge(vi_1.begin(), vi_1.end(), vi_2.begin(), vi_2.end(),
    back_inserter(vi_3));

Alternatively, you can also do this:

  vi_3.resize(vi_1.size() + vi_2.size()); // resize, NOT reserve
  merge(vi_1.begin(), vi_1.end(), vi_2.begin(), vi_2.end(),
    vi_3.begin());

the call to resize() *will* make vi_3 grow to the expected (final) size.
This allows you to use vi_3.begin() freely to overwrite the contents of
vi_3. This approach has the disadvantage that resize() will initialize
all elements (in this case to the value 0), a waste of time because each
new element is going to be overwritten in the line below.

As for in-place merge, you could use the inplace_merge() algorithm, but
it needs a slight different setup because all data must be read into the
same vector. *Assuming input is already sorted* you could write:

  vector<int> vi; // only one vector!

  // read first file (assuming it's already sorted) into vi
  ifstream fin_1("test_1.txt")
  copy(istream_iterator<int>(fin_1), istream_iterator<int>(),
    back_inserter(vi));

  // save number of ints in the first file
  size_t n = vi.size();

  // read second file (assuming it's already sorted) also into vi
  ifstream fin_2("test_2.txt");
  copy(istream_iterator<int>(fin_1), istream_iterator<int>(),
    back_inserter(vi));

  // inplace merge
  inplace_merge(vi.begin(), vi.begin() + n, vi.end());

As in your case the input is *not* already sorted, then the best thing
you could do is to read everything into a vector and then just sort.
Using merge has no practical advantage in this scenario.

HTH,

Ganesh

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]