Advertisement

merging vectors

Started by June 09, 2021 11:26 PM
23 comments, last by shubham.puri.7742 3 years, 4 months ago

Btw, if you want to allocate some space to a vector but don't give it actual content, this is what ‘reserve’ is for.

Like i did here:

std::vector<int> merged; 
merged.reserve(a.size() + b.size());

Because i know how large the vector will become, i reserve space so no dynamic allocations happen in inner loop after that.

Same would work if you could assume the user will enter about 100 numbers:

vector<int> num_a; num_a.reserve(100);
vector<int> num_b; num_b.reserve(100);

Those vectors are ‘empty’, although some memory is already allocated to them.

If the user enters more than 100 numbers it still works but reallocation happens under the hood.

well I just need a little tweak to my code, I want output to be {1,9,4,7,9,4,16,9,11} with the first input to be {1,4,9,16} and the second input to be {9,7,4,9,11} as you can see the output is the alternate of the two inputs.

Advertisement

Not sure what you mean with ‘alternate of the two inputs’, but one flaw is; As you fill both input vectors with the same loop, user can only enter the same number of elements for both. But your example has 4 and 5 elements. So you'd need to change user input, e.g. making a function which enters numbers to a vector, and then calling it two times.

pbivens67 said:

well I just need a little tweak to my code, I want output to be {1,9,4,7,9,4,16,9,11} with the first input to be {1,4,9,16} and the second input to be {9,7,4,9,11} as you can see the output is the alternate of the two inputs.

well I am going back to this problem, can I get some help

vector<int> merge(const vector<int>& a, const vector<int>& b)

{

vector<int> c = a;

c.insert(c.end(), b.begin(), b.end());

return c;

}

If you need duplicates removed, consider using a map or set.

Advertisement
#include <iostream>
#include <vector>

using std::vector;
using std::cout;

vector<int> merge(vector<int> a, vector<int> b);

int main()
{
   vector<int> num_a { 1, 4, 9, 16 };
   vector<int> num_b { 9, 7, 4, 9, 11 };

   vector<int> num_c = merge(num_a, num_b);

   for (size_t i : num_c) cout << i << " ";
   return 0;
}

vector<int> merge(vector<int> vecA, vector<int> vecB)
{
   vector<int> retVal { };
   auto const MAX_SUBSCRIPT_VECA = vecA.size() - 1;
   auto const MAX_SUBSCRIPT_VECB = vecB.size() - 1;

   if (MAX_SUBSCRIPT_VECA >= MAX_SUBSCRIPT_VECB) // vecA has the most elements
   {
      for (int i = 0; i <= MAX_SUBSCRIPT_VECA; ++i)
      {
         retVal.push_back(vecA[i]); // push vecA
         if (MAX_SUBSCRIPT_VECB >= i) retVal.push_back(vecB[i]);  // push vecB if not past end
      }
   }
   else // vecB has the most elements
   {
      for (int i = 0; i <= MAX_SUBSCRIPT_VECB; ++i)
      {
         if (MAX_SUBSCRIPT_VECA >= i) retVal.push_back(vecA[i]); // push vecA if not past end
         retVal.push_back(vecB[i]); // push vecB
      }
   }
   return retVal;
}

Output

{ 1, 9, 4, 7, 9, 4, 16, 9, 11 }

I'm sure there is a better way to do this but I used it as a learning experience. I estimated it would take me under 30 minutes to figure out but it took me 2 hours because I had to use techniques (didn't want to say methods) that I've never used before.

🙂🙂🙂🙂🙂<←The tone posse, ready for action.

A simple merge could be

/* THE MERGE FUNCTION
* Appends vector b to a
* Call by constant reference for better performance
*/
vector<int> merge(const vector<int>& a, const vector<int>& b) {
	// Initialise the result vector
	vector<int> result;

	// Push back the elements of a
	for (auto& n : a)
		result.push_back(n);

	// Push back the elements of b
	for (auto& n : b)
		result.push_back(n);

	return result;
}

Although the performance boost is marginal for small vectors a and b, the advantage of passing by constant reference would be more noticeable if you're - say - working with two vectors having a few thousand elements each. This is also the reason the foreach loops use auto& n instead of auto n. The time that would've been spent copying stuff into the local variables for the function can be saved by using a reference. At the same time, to safeguard against accidental changes, the arguments are both made const. I have a pretty fast rig, but with a vector a of size 1000 and b of size 2500, I get a running time of 586.998 milliseconds without the &s and 531.03 milliseconds with the &s.

Interestingly, you can templatise the whole thing to generalise it to any type. The only constraint is that both a and b should be vectors of the same type (comments omitted for brevity).

template <typename T>
vector<T> merge(const vector<T>& a, const vector<T>& b) {

	vector<T> result;

	for (auto& n : a)
		result.push_back(n);
	for (auto& n : b)
		result.push_back(n);

	return result;
}

An interleaved merge would mean you'd have to iterate by indices and push back the element at the current index. Assuming the vectors are both the same size:

template <typename T>
vector<T> merge(const vector<T>& a, const vector<T>& b) {

	vector<T> result;
	int size = a.size(); // Also b.size
	
	for (int i = 0; i < size; ++i) {
		result.push_back(a.at(i)); // ith element of a
		result.push_back(b.at(i)); // ith element of b
	}

	return result;
}

There is a problem when the vectors are of different sizes. In that case, you interleave until you have elements in both vectors, and dump the rest of the values from the larger vector in after that. The logic thus goes

  1. Interleave as much as you can
  2. Dump the remaining elements from the larger vector
/* THE MERGE FUNCTION
 * Interleaved merge
 * Call by constant reference for better performance
 */
template <typename T>
vector<T> merge(const vector<T>& a, const vector<T>& b) {

	vector<T> result; // result vec
	
	// sizes
	int sizeA = a.size();
	int sizeB = b.size();

	// Could make this block another function min(a, b)
	int interleavedSize = (sizeA > sizeB) ? sizeB : sizeA; // the smaller of a and b

	int i = 0; // we need this to persist outside the loop

	// At the end of this loop, i is the smaller of sizeA and sizeB
	for (i = 0; i < interleavedSize; ++i) {
		result.push_back(a.at(i)); // ith element of a
		result.push_back(b.at(i)); // ith element of b
	}

	if (i == sizeA) // b is the larger vector
		for (; i < sizeB; ++i) // dump the remaining elements of b
			result.push_back(b.at(i));
	else if (i == sizeB) // a is the larger vector
		for (; i < sizeA; ++i) // dump the remaining elements of a
			result.push_back(a.at(i));

	return result;
}

shubham.puri.7742 said:
/* THE MERGE FUNCTION * Appends vector b to a

?

🙂🙂🙂🙂🙂<←The tone posse, ready for action.

fleabay said:
?

Beside the misleading comment, the function does not return result in interleaved order as requested.

So far only two guys passed the test. : )

This topic is closed to new replies.

Advertisement