Searching for amount of unique values in vector

[reborn]

I have a std::vector<Record> RecordSet; where Recrod is a struct I made:
struct Record
{
int value;
bool switch;
float accurate;
std::string resource;
};

The vector may well contains several thousand elements, but I would like to know how I would efficiently seach for how many unique values for "resource" and "value" there are (there will likely only be a max of 20 or so unique resource strings).

Anyone care to throw up some code?

[bartoli]

If you can't change of container, i would recommend to sort elements by value (or resource), since the position in the vector doesn't seem important to you.
I think sort() can take a custom comparison function in argument, that you would define to compare the value field of your struct.
That way, the items that will have a same value will be at consecutive positions in the vector, so you can count them when you find the first one in the vector.

[Syuf]

One way is to use two sets instead of vector, sorted by value and resource each one, and before every insertion of an element check if there was this key, and, if there wasn't, increase the "unique counter". Its complexity will increase only to O(2*log(n)) from O(1) for each insertion, and memory use will be 2*n instead of n, but the query will take O(1) instead of O(n).

[reborn]

Ok, thank you for the replies.

It seems I need a function for my third param in std::sort, but I am unsure how to write it. Would anyone care to help, please?

bool mySort (Record a, Record b) 
{ 
	//no idea what to write here, anyone care to help?
        // I tried this (not really understanding what I was doing), and it did not work:
        //return (a.Resource.c_str() < b.Resource.c_str()); 
}

void Mini_Report()
{
	std::sort(RecordSet.begin(), RecordSet.end(), mySort);
	for(unsigned int i = 0; i < RecordSet.size(); i++)
	{
		printf("%s\n", RecordSet[i].Resource.c_str());
	}
	printf("\n\n");
}

[Syuf]

I don't know what predicate you would use to sort, because I don't know, what are you going to do. Do you want to count the number of unique elements with O(n*log(n)) complexity?
About this code, I can help only with it:

#include <algorithm>
#include <iterator>


bool operator < (const Record &r1, const Record &r2)
{
   return r1.Resource < r2.Resource;
}

std::ostream& operator << (std::ostream &stream, const Record &r)
{
   stream << r.Resource;
}

void mini_report()
{
   std::sort(RecordSet.begin(), RecordSet.end());
   std::copy(RecordSet.begin(), RecordSet.end(), std::ostream_iterator<Record>(std::cout, "\n"));
   std::cout << std::endl << std::endl;
}

[reborn]

Thank you for the suggestion, but I think your code should be this:

bool operator < (const Record &r1, const Record &r2)
{
   return r1.Resource.c_str() < r2.Resource.c_str();
}

std::ostream& operator << (std::ostream &stream, const Record &r)
{
   stream << r.Resource.c_str();
   return stream;
}

However, it does not do what I want it to do. In fact, it does the same as my first attempt (seems to group clumps of the values together, but not all of them are consequetive).

What I want to do is list and sum all the unique values of "Resource" in the vector. I believe the best way to do this is to sort the vector by the "Resource" part of the struct so all unique values of "Resource" are consequetive, which would allow me to do an iterative count (loop through the vector and if RecordSet[i].Resource.c_str() != RecordSet[i - 1].c_str() increase the count and capture the value too).

[andywestken]

Are you sure about your change to:

r1.Resource.c_str() < r2.Resource.c_str();

This compares the address of the char* string inside the std::string owned by r1 against the address of the char* string inside the string owned by r2.

Is that what you want?

If you want to compare the actual string values, you need Syuf's version.

[reborn]

Yes, I want to compare the string. However, I get a "Error, no operateor '<' matches these operands" using syuf's code. I assumed he made a mistake.

If anyone has an answer, I would greatly appreciate it. Thank you.

[andywestken]

"Error, no operateor '<' matches these operands"

Should be just a mattar of including <string>

What line of code does your error occur on?

[reborn]

Excellent, thank you! It wiorks.

The error was on "r1.Resource.c_str() < r2.Resource.c_str();", you was right, including <string> resolved it.