# Help with optimizations

This topic is 2645 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

[size=2]Here is the test: You have an std::vector full of random numbers and some of the numbers are repeated several times randomly. You must find the most efficient[size=2] way to create another vector with all numbers in the list referenced[size=2] only once and ordered from the lowest to the highest.

##### Share on other sites
std::sort followed by std::unique, done. (For better performance you might want to use unique_copy to avoid O(n^2) complexity).

##### Share on other sites
Or just create a set from the data:

std::set<int>(input.begin(), input.end());

The set doesn't allow duplicates, and uses a binary search tree to sort from low to high.

##### Share on other sites
Or you take Washu's C++ Quiz
I swear, if you get them all straight, I'll buy you a drink

##### Share on other sites

std::sort followed by std::unique, done. (For better performance you might want to use unique_copy to avoid O(n^2) complexity).

std::unique has O(n) complexity.

##### Share on other sites

Or just create a set from the data:

std::set<int>(input.begin(), input.end());

The set doesn't allow duplicates, and uses a binary search tree to sort from low to high.

std::set definitely appears to be the best way to do it. Now I need a way to get a vector of the locations of values within the first vector that match the given set.

Example: {5,3,2,1,2,5}
Search: 5
Result: {0,5}

##### Share on other sites

Or just create a set from the data:

std::set<int>(input.begin(), input.end());

The set doesn't allow duplicates, and uses a binary search tree to sort from low to high.

I know this is going to sound stupid but how do I read an item from the set? Tried this but it does not work:

DWORD foo= *(theSet.begin() + n);

EDIT: This works:

DWORD foo= (DWORD)(&theSet+(n*sizeof(DWORD)));

However I assume there must be a better way?...

##### Share on other sites
You know, if you actually had a question you'd probably be better off phrasing your thread title as something other than a pissing contest. In any case, how you read elements from a set depend on how you want to use it. If you're iterating through the elements then you'd use a standard iterator loop:
 for (SetType::iterator i = my_set.begin(); i != my_set.end(); ++i) { // do something with *i } 

##### Share on other sites

You know, if you actually had a question you'd probably be better off phrasing your thread title as something other than a pissing contest. In any case, how you read elements from a set depend on how you want to use it. If you're iterating through the elements then you'd use a standard iterator loop:
 for (SetType::iterator i = my_set.begin(); i != my_set.end(); ++i) { // do something with *i } 

Yeah I already had code that did that and knew there must be a way to optimize it. I should have just tiled it something like "optimize this." Anyway, I was basically trying to create separate index buffers for each subset of my mesh given an attribute buffer.

Here is what I have now:

 // Create Index buffers. std::set<DWORD> usedAttributes(attributes.begin(), attributes.end()); std::vector<std::vector<Ovgl::Face>> index_subsets; index_subsets.resize(usedAttributes.size()); for( unsigned int i = 0; i < attributes.size(); i++ ) { unsigned int s = 0; for( std::set<DWORD>::iterator j = usedAttributes.begin(); j != usedAttributes.end(); ++j) { if( attributes == *j ) { index_subsets[s].push_back(faces); } s++; } }

See anything I can do to optimize that?

##### Share on other sites

std::unique has O(n) complexity.

Oh yeah, true that. I blame being tired for thinking of such a naive implementation.

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633387
• Total Posts
3011607
• ### Who's Online (See full list)

There are no registered users currently online

×