Standard Library set_difference

closed account (S879Nwbp)
Hello,

I am having difficulty with std::set_difference;

struct data {
int element1;
int element2;
};

vector<data> data1(6), data2(6), data3(6);

data1[0].element1 = 1;
data1[1].element1 = 2;
data1[2].element1 = 2;
data1[3].element1 = 3;
data1[4].element1 = 3;
data1[5].element1 = 5;
data1[6].element1 = 5;

data2[0].element1 = 2;
data3[1].element1 = 3;

struct comp {

bool operator()(const data& data1, const data& data2) const

{

return (data1.element1 != data2.element2);

}

};

std::set_difference(data1.begin(), data1.end(), data2.begin(),
data2.end(), data3.begin(), comp());

The result I get is data3.element1 = {1,2,3,5,5}

The result I want is data3.element1 = {1,5,5}

i.e. all occurrences of 2 and 3 removed. I cannot run std::unique on the first container as I need element2 preserved. I need it in Standard Library so it will run as fast as possible.

Thankyou,

Regards James
The first thing I see is that your comp structure is incorrect. Also if you just added the operator() to your data structure you wouldn't need the comp structure.

From some documentation for std::set_difference():

The value returned indicates whether the first argument is considered to go before the second in the specific strict weak ordering it defines.


This means that you should be using the less than operator not the not equal to operator.

Lastly it would be helpful if you posted a small complete program that illustrates your problem.

closed account (S879Nwbp)
Hello,

I have changed the predicate for ordering as recommended and now get the output

data3.element1 = {1,2,2,4,4,5,5,0};

I want;

data3.element1 = {1,5}

Below is the updated code;



struct data {
int element1;
int element2;
};

vector<data> data1(9), data2(9), data3(9);

data1[0] = 1;
data1[1] = 2;
data1[2] = 2;
data1[3] = 2;
data1[4] = 4;
data1[5] = 4;
data1[6] = 4;
data1[7] = 5;
data1[8] = 5;

data2[0].element1 = 2;
data2[1].element1 = 4;

struct comp {

bool operator()(const data& d1, const data& d2) const

{

return (d1.element1 < d2.element1);

}

};

std::set_difference(data1.begin(), data1.end(), data2.begin(),
data2.end(), data3.begin(), comp());


Sorry, don't know how to use std::cout, however if you examine the contents of data3
you will see it contains element1 values {1,2,2,4,4,5,5,0}

Could I put an iterator into the predicate?


Thankyou,

Regards James
Lastly it would be helpful if you posted a small complete program that illustrates your problem.
closed account (S879Nwbp)
Hello,

Don't know what you mean, what is wrong with the code I posted? Here I have included
the relevant headers.

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

struct data {
int element1;
int element2;
};

vector<data> data1(9), data2(9), data3(9);

data1[0] = 1;
data1[1] = 2;
data1[2] = 2;
data1[3] = 2;
data1[4] = 4;
data1[5] = 4;
data1[6] = 4;
data1[7] = 5;
data1[8] = 5;

data2[0].element1 = 2;
data2[1].element1 = 4;

struct comp {

bool operator()(const data& d1, const data& d2) const

{

return (d1.element1 < d2.element1);

}

};

std::set_difference(data1.begin(), data1.end(), data2.begin(),
data2.end(), data3.begin(), comp());

A complete program is one that another user could copy and paste into a text file or internet compiler (e.g. http://cpp.sh ) and compile+run it without modification or errors (unless the compile errors are the point of the question).
Last edited on
data2 is not sorted, according to the criterion specified by comp. Therefore, the result of doing an asymmetric set different on [1, 2, 2, 2, 4, 4, 4, 5, 5] and [2, 4, 0, 0, 0, 0, 0, 0, 0] is undefined.

EDIT: Correction: elements 2 through 8 of data2 have undefined values. The array is in an undefined state of sortedness.
Last edited on
closed account (S879Nwbp)
Hello,

I wish to find the set_difference between two vector containers with non-unique values.
The program below illustrates the problem. The answer I get is

data3[0].element1 = 1
data3[1].element1 = 2
data3[2].element1 = 2
data3[3].element1 = 4
data3[4].element1 = 4
data3[5].element1 = 5
data3[6].element1 = 5
data3[7].element1 = 0

whereas, the answer I want is;

data3[0].element1 = 1
data3[1].element1 = 5
data3[2].element1 = 5

i.e. all 2's and 4's removed. Any ideas how my code could be modified to do this?

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

struct data {
int element1;
int element2;
};

int i, records;

std::vector<data> data1(10), data2(10), data3(10);

std::vector<data>::iterator it_difference;

struct difference {
bool operator()(const data& d1, const data& d2) const {
return (d1.element1 < d2.element1);
}
};

int main()
{

data1[0].element1 = 1;
data1[1].element1 = 2;
data1[2].element1 = 2;
data1[3].element1 = 2;
data1[4].element1 = 4;
data1[5].element1 = 4;
data1[6].element1 = 4;
data1[7].element1 = 5;
data1[8].element1 = 5;

data2[0].element1 = 2;
data2[1].element1 = 4;

it_difference = std::set_difference(data1.begin(), data1.end(),
data2.begin(), data2.end(),
data3.begin(), difference());

data3.resize(it_difference-data3.begin());

records = std::distance(data3.begin(), it_difference);

for(i = 0; i < records; i++)

std::cout << "data3[" <<i<<"].element1 = "<< data3[i].element1 << "\n";

}
Topic archived. No new replies allowed.