C++

Forum

 
Vector difference?

Nebur (68)
I am trying to write a function, that given 2 sorted vectors v1 and v2, returns a sorted vector with the elements of v1 that are not on v2.

The code computes the array difference, but I don't know how to eliminate an element when it is duplicated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
#include <vector>
using namespace std;

//Pre: v1 and v2 are sorted vectors
//Post: returns the elements of v1 that are not in v2
vector<double> difference(const vector<double>& v1, const vector<double>& v2) {
	vector<double> v3(v1.size());
	int i, j, k;
	i = j = k = 0;
	
	while (i < v1.size() and j < v2.size()) {
		if (v1[i] == v2[j]) ++i;
		else if (v1[i] > v2[j]) ++j;
		else {
			v3[k] = v1[i]; ++i; ++k;
		}
	}
	
	while (i < v1.size()) {
		v3[k] = v1[i]; ++i; ++k;
	}
	
	vector <double> Res(k);
	for (i = 0; i < k; ++i) Res[i] = v3[i];
	return Res;
}
Cubbi (4774)
Are you not allowed to use std::set_difference?

(both http://en.cppreference.com/w/cpp/algorithm/set_difference and http://www.cplusplus.com/reference/algorithm/set_difference demonstrate it with sorted vectors)
Last edited on
Nebur (68)
Hehe as you can expect, i am not allowed to use any of these methods :p
keskiverto (10395)
Do you mean by "not allowed" that you cannot call the std::set_difference, or also that you cannot study at all the logic of the code examples that could implement std::set_difference?
Nebur (68)
I will do it by using set_difference.

How could the code look? Just set_difference(v1.begin(), v1.end(), v2.begin(), v2.end()) ?

Thansk!
JLBorges (13770)
> How could the code look?

There is an example here: http://en.cppreference.com/w/cpp/algorithm/set_difference

Also possible implementation, if you want to understand the logic.
Nebur (68)
I am not allowed to use iterators, I made my own version, is it correct?

1
2
3
4
5
6
7
8
9
10
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<double> difference(const vector<double>& v1, const vector<double>& v2) {
	vector<double> result;
	set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
	return result;
}
JLBorges (13770)
vector<double> result;

This is an empty vector; you need to add elements to it. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator> // ***
using namespace std;

vector<double> difference(const vector<double>& v1, const vector<double>& v2) {

	vector<double> result;
        
        // http://www.cplusplus.com/reference/iterator/back_inserter/
	set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result) ); // ***

	return result;
}
Nebur (68)
It works, but when an element is repeated in v1 and does not appear in v2 it appears repeated in the result. It should only appear once.
keskiverto (10395)
std::unique

However, if you would not be allowed to use these library algorithms directly, you would look at the example implementations of both std::set_difference and std::unique, and rewrite them fused, with your original index style, rather than the interator/pointer style that the examples use.
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <cassert>

std::vector<double> difference( std::vector<double> v1, std::vector<double> v2 )
{
    static const auto is_nan = [] ( double v ) { return std::isnan(v) ; } ;
    assert( std::none_of( v1.begin(), v1.end(), is_nan ) &&
            std::none_of( v2.begin(), v2.end(), is_nan ) ) ;

    if( !std::is_sorted( v1.begin(), v1.end() ) ) std::sort( v1.begin(), v1.end() ) ;
    if( !std::is_sorted( v2.begin(), v2.end() ) ) std::sort( v2.begin(), v2.end() ) ;

	std::vector<double> result ;

	std::set_difference( v1.begin(), std::unique( v1.begin(), v1.end() ),
                             v2.begin(), v2.end(), std::back_inserter(result) ) ;
	return result;
}
Nebur (68)
Ok, so I managed to write a program that does what I initially wanted without using iterators.

However i get the error Invalid memory reference, and I have no idea why this happens.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
#include <iostream>
#include <vector>
using namespace std;
 
//Pre: v1 and v2 are sorted vectors
//Post: returns the elements of v1 that are not in v2
vector<double> difference(const vector<double>& v1, const vector<double>& v2) {
        //eliminate all duplicates of v1
	vector<double> va;
        va.push_back(v1[0]);
        for (int i = 1; i < v1.size(); ++i) {
        	if (v1[i-1] != v1[i]) va.push_back(v1[i]);
        }
        
        //eliminate all duplicates of v1
        vector<double> vb;
        vb.push_back(v2[0]);
       	for (int i = 1; i < v2.size(); ++i) {
        	if (v2[i-1] != v2[i]) vb.push_back(v2[i]);
        }
        
        //in the worst case va and vb have no elements in common
        vector<double> v3(va.size());
        
	//i for va, j for vb, k for v3
	int i, j, k;
        i = j = k = 0;
        
	//check which elements of va are not in vb and put them in v3       
        while (i < va.size() and j < vb.size()) {
                if (va[i] == vb[j]) {
                       ++i; ++j;
                }
                else if (va[i] > vb[j]) ++j;
                else {
        	        v3[k] = va[i]; ++i; ++k;   	
               }
	}
		
	//copy the remaining part of va which wasnt treated if there is any
        while (i < va.size()) {
           v3[k] = va[i];
	   ++k;
           ++i;
        }
        
	//copying the result in the resultant vector Res       
        vector <double> Res;
        for (i = 0; i < k; ++i) Res[i] = v3[i];
        return Res;
}
Last edited on
JLBorges (13770)
Working with integers instead of floating point values would put the entire focus on the algorithm (avoid taling care of floating point comparisons and treatment of possible NaNs).

Caveat: untested.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <vector>
using namespace std;

void push_back_if_unique( vector<int>& seq, int value )
{ if( seq.empty() || seq.back() < value ) seq.push_back(value) ; }

//Pre: first and second are sorted vectors
//Post: returns unique elements of first that are not in second
vector<int> difference( const vector<int>& first, const vector<int>& second )
{
    vector<int> result ;

    std::size_t i = 0 ; // position in first
    std::size_t j = 0 ; // position in second
    while( i < first.size() )
    {
        if( j == second.size() ) // nothing more in second
        {
            for( ; i < first.size() ; ++i ) push_back_if_unique( result, first[i] ) ;
            return result ;
        }

        if( first[i] > second[j] ) ++j ;
        else
        {
            if( first[i] < second[j] ) push_back_if_unique( result, first[i] ) ;
            ++i ;
        }
    }

    return result ;
}

Nebur (68)
Wow the code worked!

Thank you so much for helping me this much, you sure helped me more than my teachers!

really much thanks!
Topic archived. No new replies allowed.