Re: Some proble on " merge() on vector "
gpfei6@gmail.com ha scritto:
ifstream fin_1("test_1.txt"), fin_2("test_2.txt");
int ii;
vector<int> vi_1, vi_2;
while(fin_1>>ii)
vi_1.push_back(ii);
You can also use:
copy(istream_iterator<int>(fin_1), istream_iterator<int>(),
back_inserter(vi_1));
for(vector<int>::iterator iter=vi_1.begin(); iter!=vi_1.end(); +
+iter)
cout<<*iter<<'\t';
You can also use:
copy(vi_1.begin(), vi_1.end(), ostream_iterator<int>(cout, "\t"));
//I don't know whether this is needed.*reserve*
vi_3.reserve(100);
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.
// could I replace *vi_3.begin()* to *vi_1.begin()*?
I just wanna use vi_1 .
This is completely another story, see below.
merge(vi_1.begin(), vi_1.end(), vi_2.begin(), vi_2.end(),
vi_3.begin());
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! ]