Most efficient way to list items in C/C++

Question

I have a list of say 100 unsorted items. Each item belongs to a group. The group the item belongs to is simply a member of the item class.

Using C/C++ I'm looking for the most efficient way of scanning through the list of items, checking which group they are in and printing the item to the screen. Here's the catch though. Once an item from a group has been printed to the screen, I don't want to print any more items belonging to that group.

I'm using a pre STL compiler and the size of the executable is critical so I don't want to start defining my own Hash classes.

Answer 1

You can create a dictionary/hashmap of groups and for each group store a bool saying if a item of that group was printed or not.

Sample code:

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

Answer 2

Sort the items according the group value (if it's a pointer, then you can use its address, otherwise lexicographical sort the string). Then loop through that sorted list, taking the first item of each group always.

This takes approximately

n + n * log(n)

I think this is a reasonable alternative between the size of your executable and speed.

Answer 3

If you can number the groups 0..99 then you'll need an array of booleans, or bitset if you want to optimize. Init all the array to 'false'. Set arr[groupId] = 'true' after you print it, and check the value next time before printing. No STL required.

Answer 4

Keep a std::set of the group names that items of which should no longer be printed.

Answer 5

You did write c/c++ in the question, so here's some c code. A couple of questions are in order. Does a group become printable sometime in the future? Is the item list static? Does it matter which item from a specific group you print?

I would suggest the following construct (with my limited understanding of the problem):

An array of lists.

  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.*/

Better yet, use a list of lists. group_t will be:

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

Answer 6

To answer some more questions.

Is the item list static?

No, it can shrink or grow at any time.

Does it matter which item from a specific group you print?

Not for the time being, no. Maybe in the future, but at the moment it should be sufficient to print the first item found belonging to a unique group.

Answer 7

What about groups? can you get a new group? And can a group become relevant after you print one of its members?

Answer 8

The cost to print to the screen is several orders of magnitude more than anything else you can do with the objects. If you had an array of 10 million objects in only a few groups, then sorting is not a reasonable option. If the groups can be identified by a static index (i.e. an integer in a given range), just use a mask array to indicate whether it's been seen. If the groups are more complicated, you can store the groups that have been seen in any set data structure (hash, tree, etc).