How to stop std::set from sorting? [duplicate]

Question

I have an array of names, but I require only the unique ones. I use std::set so that it clears out duplicate. Yet I need the name appear in the same order as input. That means if my input is:

Mary
Mary
John
John
John
Apple
Apple
Apple

[Edit]: After checking comments/answers, I want to emphasis that each name appears in group and does not show up later on in the input. Refer to example, Mary appears two times and that is. It does not show up again later on.[/Edit]

I want my output to be:

Mary
John
Apple

Using std::set, I get the sorted one:

Apple
John
Mary

I find out there is unordered_set (from {cplusplus.com}). This one again does not keep the input order.

Question:

1. Is there a way to stop the std::set from sorting?
2. I have read that {one can write own's sorting method for std::set}. Now if I cannot stop the set from sorting, how about writing my own sorting method, but always return the first element of input as the smallest? (If I can get thru the detail on how to do it...)
3. Or is there other thing in std that can reduce a group of strings into a unique set, but does not sort it?

Thanks!

Answer 1

The simplest thing is to keep 2 collections, the vector and the set (or unordered_set). This will consume more memory but will use the set to check for duplicates (in O(log N) time) and the vector to maintain order.

The set can also alternatively contain the position in the vector of the item and have as a predicate v[i] < v[j]. Slightly complicated as you'd need to store a reference/pointer to your vector in the special predicate. However it can be done and will use potentially less memory as you only have one collection of strings and the other is of ints. In addition it acts as an index, being able to quickly locate where a particular item is.