How to stop std::set from sorting?

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.

Answer 2

After reading all comments and answers, I think the most direct way to answer my own question is to use std::vector and std::unique.

Point to note is:

1. I have a list of names that is small. Should not be more than 2000 names.
2. Each name appears in a cluster. If Mary appears 2 times, it will not appear any more in the rest of of the list.
3. I only need to get a set of unique names, but keep the initial ordering.
4. After getting that unique set, I do not need to do any more operation (insert/remove/etc) to the set.

So here is my coding:

#include <vector>

int main()
{
    std::vector<std::string> names;
    std::vector<std::string>::iterator last;
    std::vector<std::string>::iterator it;

    names.push_back("Mary");
    names.push_back("Mary");
    names.push_back("John");
    names.push_back("John");
    names.push_back("John");
    names.push_back("Apple");
    names.push_back("Apple");
    names.push_back("Apple");

    last = std::unique(names.begin(), names.end());
    for (it = names.begin(); it != last; ++it)
        std::cout << *it << endl;
}

And so the output will be (what I want):

Mary
John
Apple

That is it. Thanks for those contributing. Feel free to comment, especially about the efficiency.

Answer 3

You're attempting to change a fundamental design implementation. Instead you should probably rethink your own design and not try to go against the grain of the standard library.

My solution would be to use a std::vector<std::string> and depending on what your program aims to do either:

• Check for a duplicate before pushing onto the vector

or

• Create a function to return a new vector of the unique names

Either of these implementations will retain the insert order and you'll be able to handle duplicates on your own terms.

Here is the second version:

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> collection;

std::vector<std::string> getUniques(std::vector<std::string> collection)
{
    std::vector<std::string> uniques;
    for (std::string name : collection)
    {
        if (std::find(uniques.begin(), uniques.end(), name) == uniques.end())
            uniques.push_back(name);
    }

    return uniques;
}

int main()
{
    collection.push_back("John");
    collection.push_back("John");
    collection.push_back("Sally");
    collection.push_back("Kent");
    collection.push_back("Jim");
    collection.push_back("Sally");

    std::vector<std::string> uniques = getUniques(collection);

    for (std::string name : uniques)
        std::cout << name << std::endl;
}

Yields:

John
Sally
Kent
Jim

Answer 4

First question: No. As per cplusplus.com:

Sets are containers that store unique elements following a specific order.

Second question: you would need to have 2 points of data to do that. The first would be your actual string, the second would be a sort of 'insertion index', so you can store the order of insertion.

So basically, you could do it if you put std::pair in your std::set and basically increment the number you put in the std::pair. However, once you do that, it means each std::pair will be unique, meaning the use of 'std::set' is gone.

The above already sounds way too complicated, so why not go with a more suitable container? You could for example use an std::vector and remove doubles upon insertion.

If that's too slow (O(N) insertion), you could have an std::vector for the in-order storage, and keep an std::set next to it to be able to quickly check uniqueness.

Answer 5

From your example, it seems that the equal values follow each other.

If this is the case, there is no need for sophistication: you can start filling a new array and copy the elements one by one unless they are the same as the previous. This is a simple O(N) process.

Answer 6

Instead of std::set use std::unique

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

bool myfunction (char *i,char *j) 
{
    int x=strcmp(i,j);
    if(!x)
        return 1;
    else
        return 0;
}

int main () 
{
  char mywords[][10] = {"Mary","Mary","John","John","John","Apple","Apple","Apple"};
  vector<char*> myvector (mywords,mywords+8);
  vector<char*>::iterator it;
  it = unique (myvector.begin(), myvector.end(), myfunction);
  myvector.resize(distance(myvector.begin(),it));

  cout << "Output:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << ' ' << *it;
  cout << endl;

  return 0;
}