在C/C++中列出項目的最有效方法

我有一個說100個未排序項目的列表。每個項目都屬於一個組。項目所屬的組只是項目類別的成員。在C/C++中列出項目的最有效方法

使用C/C++我正在尋找最有效的方式來掃描項目列表，檢查它們所在的組以及將項目打印到屏幕。儘管如此。一旦組中的項目已經打印到屏幕上，我不想再打印屬於該組的任何項目。

我正在使用STL編譯器，可執行文件的大小很關鍵，所以我不想開始定義我自己的Hash類。

來源

2008-11-09 KJF

您需要提供更多信息。您的物品清單是否已分類？項目和組之間的聯繫是什麼？這只是一個std :: string成員命名組？ – 2008-11-09 14:31:35

感謝您的反饋。我做了一些編輯。 – KJF 2008-11-09 14:38:13

您可以創建組的字典/散列表，併爲每個組存儲一個布爾值，說明是否打印了該組的一個項目。

示例代碼：

#include <unordered_map> 
#include <string> 
#include <iostream> 

std::string getGroupForNumber(int num) 
{ 
// 
} 

int main() 
{ 
    typedef std::tr1::unordered_map< std::string, bool > hashmap; 
    hashmap groupsPrinted; 

    for(int i = 0 ; i < 100 ; ++i) { 
     if (groupsPrinted[ getGroupForNumber(i) ] == false) { 
      groupsPrinted[ getGroupForNumber(i) ] = true; 
      std::cout << i << std::endl; 
     } 
    } 
    return 0; 
}

來源

2008-11-09 14:25:37 Kasprzol

謝謝，我想到了，但問題是我正在使用STL編譯器，這意味着我需要創建自己的哈希類。這是我想避免空間限制的原因。 – KJF 2008-11-09 14:31:50

排序根據組值的項目（如果它是一個指針，那麼你可以使用它的地址，否則辭書排序串）。然後遍歷該排序列表，始終使每個組的第一個項目。

這大約

n + n * log(n)

我覺得這是你的可執行文件和速度的大小之間一個合理的選擇。

來源

2008-11-09 14:46:09

如果您可以給組0..99編號，那麼您需要一個布爾值數組，或者如果您想優化，則需要bitset。將所有數組初始化爲'false'。打印完成後設置arr [groupId] ='true'，並在打印之前下次檢查值。不需要STL。

來源

2008-11-09 15:15:52 Drakosha

保留一個std :: set的組名稱，其項目不應再被打印。

來源

2008-11-09 15:20:03

你確實在問題中編寫了c/C++，所以這裏有一些c代碼。有幾個問題是爲了。未來某個組織是否可以打印？項目列表是靜態的嗎？您打印的特定組中的哪個項目有關係嗎？

我建議下面的結構（用我有限的對問題的理解）：

列表的數組。

typedef struct node{ 
    void *item; /* this is your item */ 
    node *next; 
    } node_t; 

    typedef struct { 
    node_t *my_group; 
    int used; 
    } group_t; 

    static group_t my_items[NUM_OF_GROUPS]; /* this is your ordered by groups list.*/

更好的是，使用列表清單。 group_t將是：

typedef struct group{ 
    node_t *my_group; 
    group *next_free; 
} group_t;

來源

2008-11-09 15:32:41

要回答更多問題。

項目列表是否爲靜態？

不，它可以隨時收縮或增長。

打印您打印的特定組中的哪個項目有意義嗎？

不是暫時的，沒有。也許在將來，但目前應該足以打印屬於獨特組的第一個項目。

來源

2008-11-09 15:58:27 KJF

羣體呢？你可以得到一個新的組？打印其中一個成員後，一個組可能會變得相關嗎？

來源

2008-11-09 17:32:52

打印到屏幕上的成本比對物體所能做的任何事情都要高出幾個數量級。如果只有幾個組中有1000萬個對象，那麼排序不是一個合理的選擇。如果可以通過靜態索引（即給定範圍內的整數）識別組，則只需使用掩碼數組來指示是否已經看到它。如果組更復雜，則可以存儲在任何集合數據結構（哈希，樹等）中看到的組。

來源

2008-11-09 22:42:43 Jed

在C/C++中列出項目的最有效方法

回答

相關問題