Container ordering requirements (in an effort to understand boost::multi_index)

Question

Given a collection of something that is modeled as:

struct Foo { int id; std::string name; };

where id is unique and name is non-unique/non-{null|empty}.

How do I use a datastructure like boost::multi_index that will allow me to do the equivalent of:

select id, name from Foo group by name order by id

The standard STL containers aren't getting me to the promised land. I used a sql variant above only to get my point across. I am not really dealing with any databases.

UPDATE:

So, apparently all I need is:

typedef boost::multi_index_container<
  Foo,
  indexed_by<
    ordered_unique<identity<Foo>>,
    ordered_unique<member<Foo, std::string, &Foo::name>>
  >
> MIC;

Can someone confirm I have got this right? It seems to work. I haven't tested it yet.

Possible duplicate of [std::map, how to sort by value, then by key](http://stackoverflow.com/questions/19842035/stdmap-how-to-sort-by-value-then-by-key) — Treycos, Oct 06 '16 at 20:56
@Treycos Its not a duplicate at all. Please take a look at my sql query again. I didn't ask to sort by id, then by name. I said I wanted to sort by id, while at the same time grouping all *identical* names and assigning them _any_ id among them. So {1, "Foo"} {2, "Bar" } {3, "Foo"} will eventually return {1, "Foo"} {2, "Bar"} **OR** {2, "Bar"} {3, "Foo"} — ForeverLearning, Oct 07 '16 at 00:04
Could someone who has more SO mojo than me remove that "This question may already have an answer" tag? It looks inappropriate for my case. — ForeverLearning, Oct 07 '16 at 00:09

score 0 · Answer 1 · answered Oct 06 '16 at 21:04

In terms of using boost, I don't use it that much, but I don't think it's necessary here depending on how efficient you need this operation to be.

If you have a standard library container of Foo, let's say std::vector<Foo>for simplicity. You can do something like the following:

std::string nameToSearchFor( "Bar" );
std::vector<Foo> vecFoos;
std::vector<Foo> results;
auto it = std::find_if( it, vecFoos.cend(), [&]( const Foo& foo ) {
   return (foo.name == nameToSearchFor);
});

while (it != vecFoos.cend())
{
   results.emplace_back( *it );

   it = std::find_if( it, vecFoos.cend(), [&]( const Foo& foo ) {
       return (foo.name == nameToSearchFor);
   });
}

std::sort( results.begin(), results.end(), []( const Foo& lhs, const Foo& rhs ) {
    return lhs.id < rhs.id;
});

This will work with any STL container, or any container that provides at least ForwardIterator access to its elements. But if you are using something like std::unordered_multimap you will want to take advantage of its internal find/equal_range methods.

There are lots of ways you can speed this up, but this is a naive, quick and easy-to-understand approach that will give you what you want and should be fine for small data sets.

Thank you! I know how to do this the hard way. boost::multi_index seems to be tailor made for this purpose and I wanted to see how to get this stuff for free. I took a shot and if you see my updated post, it seems to work. I haven't tested it extensively with more inputs. — ForeverLearning, Oct 07 '16 at 00:06

Container ordering requirements (in an effort to understand boost::multi_index)

UPDATE:

1 Answers1