如何阻止std :: set從排序？

Question

我有一個名稱數組，但我只需要唯一的名稱。我使用std::set，以便清除重複。然而，我需要按照與輸入相同的順序出現名稱。這意味着，如果我輸入的是：

Mary 
Mary 
John 
John 
John 
Apple 
Apple 
Apple 

[編輯]：檢查的意見/回答後，我想那每個名字出現在組和不輸入後來出現的重視。參考例子，Mary出現兩次，那就是。它不會再次出現以後[/編輯]

我希望我的輸出是：

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. 得到這個獨特的集合後，我不需要做任何更多的操作（插入/刪除/等）到集合。

因此，這裏是我的編碼：

#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 :: pair將是唯一的，這意味着'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]。稍微複雜一點，因爲您需要在特殊謂詞中存儲引用/指向矢量的指針。然而，它可以完成並將使用潛在的更少的內存，因爲你只有一個字符串集合，另一個是整數。此外，它充當索引，能夠快速定位特定項目的位置。

Answer 5

從你的例子看來，相等的值似乎彼此相隨。

如果是這種情況，則不需要複雜性：您可以開始填充新數組並逐個複製元素，除非它們與前一個相同。這是一個簡單的O（N）過程。

Answer 6

相反的std ::設置使用std ::唯一

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