Как остановить std :: set от сортировки?

Question

У меня есть массив имен, но мне нужны только уникальные. Я использую std::set так, чтобы он очищал дубликат. Но мне нужно, чтобы имя отображалось в том же порядке, что и вход. Это означает, что, если мой вход:

Mary 
Mary 
John 
John 
John 
Apple 
Apple 
Apple 

[Изменить]: После проверки комментариев/ответов, я хочу внимание, что каждого имя появляется в группе и не обнаруживается позже на входе. См. Пример, Mary появляется два раза, и это так. Он не появляется снова позже [/ Edit]

Я хочу, чтобы мой выход будет:.

Mary 
John 
Apple 

Использование std::set, я получаю отсортированный одно:

Apple 
John 
Mary 

я узнаю есть unordered_set (от {cplusplus.com}). Это еще раз не сохранить порядок ввода.

Вопрос:

1. Есть ли способ, чтобы остановить std::set от сортировки?
2. Я читал, что {one can write own's sorting method for std::set}. Теперь, если я не могу остановить сортировку set, как насчет написания моего собственного метода сортировки, но всегда возвращайте первый элемент ввода как самый маленький? (Если я могу получить через подробности о том, как это сделать ...)
3. Или есть ли еще в std, который может свести группу строк в уникальный набор, но не сортирует его?

Спасибо!

Answer 1

После прочтения всех комментариев и ответов, я думаю, что самый прямой путь, чтобы ответить на мой собственный вопрос заключается в использовании std::vector и std::unique.

точка отметить это:

1. У меня есть список имен, который является маленьким. Не должно быть более 2000 имен.
2. Каждое имя появляется в кластере. Если Mary появляется 2 раза, оно больше не будет отображаться в остальной части списка.
3. Мне нужно только получить набор уникальных имен, но сохранить начальный порядок.
4. После получения этого уникального набора мне больше не нужно выполнять операцию (вставить/удалить/etc) в набор.

Так вот мое кодирование:

#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; 
} 

И поэтому выход будет (что я хочу):

Mary 
John 
Apple 

То есть это. Спасибо за помощь. Не стесняйтесь комментировать, особенно об эффективности.

Answer 2

Вы пытаетесь изменить фундаментальную реализацию проекта. Вместо этого вы должны, вероятно, переосмыслить свой собственный дизайн и не пытаться идти против зерна стандартной библиотеки.

Мое решение было бы использовать std::vector<std::string> и в зависимости от того, какие цели вашей программы, чтобы сделать либо:

• Проверить дубликата до нажатия на вектор

или

• Создайте функцию для возврата нового вектора уникальных имен

Любая из этих реализаций сохранит порядок вставки, и вы сможете обрабатывать дубликаты на своих условиях.

Вот вторая версия:

#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; 
} 

Урожайность:

John 
Sally 
Kent 
Jim 

Answer 3

Первый вопрос: НетСогласно cplusplus.com:

Наборы представляют собой контейнеры, которые хранят уникальные элементы в соответствии с конкретным заказом.

Второй вопрос: для этого вам нужно будет иметь 2 точки данных. Первая будет вашей фактической строкой, вторая будет своего рода «индексом вставки», поэтому вы можете сохранить порядок вставки.

Итак, вы можете сделать это, если вы поместите std :: pair в свой std :: set и в основном увеличите число, указанное в std :: pair. Однако, как только вы это сделаете, это означает, что каждая пара std :: будет уникальной, то есть использование «std :: set» исчезнет.

Выше уже звучит слишком сложно, так почему бы не пойти с более подходящим контейнером? Вы можете, например, использовать std :: vector и удалять удвоения при вставке.

Если это слишком медленно (установка O (N)), вы можете иметь std :: vector для хранения в порядке хранения и сохранить рядом с ним std :: set, чтобы можно было быстро проверить уникальность.

Answer 4

Проще всего сохранить 2 коллекции, vector и set (или unordered_set). Это будет потреблять больше памяти, но будет использовать set для проверки дубликатов (в O(log N) раз) и vector для поддержания порядка.

set также может также содержать положение в векторе изделия и иметь в качестве предиката v[i] < v[j]. Немного сложный, поскольку вам нужно будет сохранить ссылку/указатель на свой вектор в специальном предикате. Однако это можно сделать и будет использовать потенциально меньше памяти, поскольку у вас есть только один набор строк, а другой - из ints. Кроме того, он действует как индекс, способный быстро найти, где находится конкретный элемент.

Answer 5

Из вашего примера, кажется, что равные значения следуют друг за другом.

Если это так, нет необходимости в изощренности: вы можете начать заполнять новый массив и копировать элементы один за другим, если они не совпадают с предыдущими. Это простой процесс O (N).

Answer 6

Вместо станд :: набор использования станд :: уникальный

#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; 
}