CODEWITHSUNDEEP
c++data-structuresc++17std
cloudraven
cloudraven

Reputation: 2544

Sorted container of pointers to custom types based on a non-unique priority value, as a class member

I need a container that meets this scenario:

  1. Needs to be a member of a class
  2. Needs to contain pointers to a custom type
  3. The elements are sorted using a non-unique priority value (an integer. for example: priority 0 items go before priority 1 items, before priority 2 items. Order between items of the same priority is non-important)
  4. Cannot use boost or any other external library

Optionally , it would be really good if I don't have to create an additional class/struct to support sorting. Also, up to C++17 is good.

Note, I am using (auto item : collection), but if this only works with traditional iterators, that is also fine.

So for example:

class MyBigClass {

   Collection<Item*> myItems;
   void MyMain();
}

class Item {
   std::string data;
   int priority;
}


void MyBigClass::MyMain()
{
  Item i1("data1", 1);
  Item i2("data2", 0);
  Item i3("data3", 3);
  Item i4("data4", 1);
  myItems.insert(&i3);
  myItems.insert(&i1);
  myItems.insert(&i2);
  myItems.insert(&i4);
  
  for(auto item : myItems) {
     cout << item->data << endl;
  }

}


// expected output
// data2
// data1
// data4
// data3

I was hoping I could use a Set, but its associativeness is giving me trouble since my comparison function works with ordering, but not with uniqueness (for the set membership). I guess I could use a vector and order after every insert, but there may be something better I could do. As far as I can tell there is no non-associative sorted container.

Upvotes: 1

Views: 49

Answers (1)

Chad
Chad

Reputation: 19032

A std::multiset with a custom compare function will suffice:

#include <iostream>
#include <string>
#include <set>
using namespace std;

struct Item {
   std::string data;
   int priority;
};

struct item_compare
{
    bool operator()(Item* lhs, Item* rhs)
    {
        return lhs->priority < rhs->priority;
    }
};


int main() {
    std::multiset<Item*, item_compare> item_set;
    Item i1{"data1", 1};
    Item i2{"data2", 0};
    Item i3{"data3", 3};
    Item i4{"data4", 0};
    Item i5{"data5", 0};
    
    item_set.insert(&i1);
    item_set.insert(&i2);
    item_set.insert(&i3);
    item_set.insert(&i4);
    item_set.insert(&i5);

    for(auto item : item_set)
       std::cout << item->data << '\n';
    
    return 0;
}

Live example: https://ideone.com/iY9Jrp

Upvotes: 2

Related Questions