C++

Forum

 
Vector difference?

Dec 10, 2013 at 4:35pm
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;
}
Dec 10, 2013 at 4:37pm
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 Dec 10, 2013 at 4:39pm
Dec 10, 2013 at 9:15pm
Nebur (68)
Hehe as you can expect, i am not allowed to use any of these methods :p
Dec 10, 2013 at 11:12pm
keskiverto (10424)
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?
Dec 11, 2013 at 8:00am
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!
Dec 11, 2013 at 8:06am
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.
Dec 11, 2013 at 8:12am
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;
}
Dec 11, 2013 at 8:25am
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;
}
Dec 11, 2013 at 11:16am
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.
Dec 11, 2013 at 12:48pm
keskiverto (10424)
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.
Dec 11, 2013 at 1:08pm
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;
}
Dec 13, 2013 at 6:36pm
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;
}
Edit & run on cpp.sh
Last edited on Dec 13, 2013 at 6:37pm
Dec 13, 2013 at 8:15pm
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 ;
}

Dec 13, 2013 at 9:44pm
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.