how to sort std::vector contains user defined struct by multiplevalue?

Discussion in 'C++' started by rockdale, Dec 4, 2008.

  1. rockdale

    rockdale Guest

    Hi, all:

    I have a std::vector which contains my struct. The data in the vector
    is inserted from a std::map, then I will need to sort the vector based
    on some criteria and then get the sorted data out. my struct is like:

    struct item
    {
    int itemtypeid;
    int itemid;
    };

    typedef std::deque<item> ItemList;
    struct order
    {
    int orderid;
    int ordertypeid;
    ItemList itemdata;
    };

    typedef std::vector<order> VectorOrder;

    I use a functor to do the sort by orderid

    this is the functor:
    class COrderSorter
    {
    public:
    bool operator()(const order& lhs, const order& rhs)
    {
    return lhs.orderid < rhs.order;
    }
    };

    VectorOrder m_vecOrder

    std::sort(m_vecOrder.begin(), m_vecOrder.end(), COrderSorter());

    NOW, I need to sort the order by the its item first by itemtypeid,
    then by itemid.
    for example:
    orderid itemtypeid itemid
    1 2 4
    1 2 3
    1 1 5
    2 1 2

    the final result I need to get:
    orderid itemtypeid itemid
    2 1 2
    1 1 5
    1 2 3
    1 2 4


    Is there a way to achieve this other than the plain iterate through
    every order and then iterate through its item?
    What the efficient, memory consideration about this?

    thanks in advance
    -rockdale
    rockdale, Dec 4, 2008
    #1
    1. Advertising

  2. rockdale

    Rolf Magnus Guest

    Re: how to sort std::vector contains user defined struct by multiple value?

    rockdale wrote:

    > Hi, all:
    >
    > I have a std::vector which contains my struct. The data in the vector
    > is inserted from a std::map, then I will need to sort the vector based
    > on some criteria and then get the sorted data out. my struct is like:
    >
    > struct item
    > {
    > int itemtypeid;
    > int itemid;
    > };
    >
    > typedef std::deque<item> ItemList;
    > struct order
    > {
    > int orderid;
    > int ordertypeid;
    > ItemList itemdata;
    > };
    >
    > typedef std::vector<order> VectorOrder;
    >
    > I use a functor to do the sort by orderid
    >
    > this is the functor:
    > class COrderSorter
    > {
    > public:
    > bool operator()(const order& lhs, const order& rhs)
    > {
    > return lhs.orderid < rhs.order;
    > }
    > };
    >
    > VectorOrder m_vecOrder
    >
    > std::sort(m_vecOrder.begin(), m_vecOrder.end(), COrderSorter());
    >
    > NOW, I need to sort the order by the its item first by itemtypeid,
    > then by itemid.
    > for example:
    > orderid itemtypeid itemid
    > 1 2 4
    > 1 2 3
    > 1 1 5
    > 2 1 2
    >
    > the final result I need to get:
    > orderid itemtypeid itemid
    > 2 1 2
    > 1 1 5
    > 1 2 3
    > 1 2 4
    >
    >
    > Is there a way to achieve this other than the plain iterate through
    > every order and then iterate through its item?


    Why don't you just add another function object that does this, with an
    operator() like this;

    bool operator()(const order& lhs, const order& rhs)
    {
    if (lhs.itemtypeid == rhs.itemtypeid)
    return lhs.itemid < rhs.itemid;
    else
    return lhs.itemtypeid < rhs.itemtypeid;
    }
    Rolf Magnus, Dec 4, 2008
    #2
    1. Advertising

  3. rockdale

    Lance Diduck Guest

    On Dec 4, 11:46 am, rockdale <> wrote:
    > Hi, all:
    >
    > I have a std::vector which contains my struct. The data in the vector
    > is inserted from a std::map, then I will need to sort the vector based
    > on some criteria and then get the sorted data out. my struct is like:
    >
    > struct item
    > {
    >     int itemtypeid;
    >     int itemid;
    >
    > };
    >
    > typedef std::deque<item> ItemList;
    > struct order
    > {
    >      int orderid;
    >      int ordertypeid;
    >      ItemList itemdata;
    >
    > };
    >
    > typedef std::vector<order> VectorOrder;
    >
    > I use a functor to do the sort by orderid
    >
    > this is the functor:
    > class COrderSorter
    > {
    > public:
    >         bool operator()(const order& lhs, const order& rhs)
    >         {
    >                 return lhs.orderid < rhs.order;
    >         }
    >
    > };
    >
    > VectorOrder m_vecOrder
    >
    > std::sort(m_vecOrder.begin(), m_vecOrder.end(), COrderSorter());
    >
    > NOW, I need to sort the order by the its item first by itemtypeid,
    > then by itemid.
    > for example:
    > orderid itemtypeid itemid
    >     1            2           4
    >     1            2           3
    >     1            1           5
    >     2            1           2
    >
    > the final result I need to get:
    > orderid itemtypeid itemid
    >     2            1           2
    >     1            1           5
    >     1            2           3
    >     1            2           4
    >
    > Is there a way to achieve this other than the plain iterate through
    > every order and then iterate through its item?
    > What the efficient, memory consideration about this?
    >
    > thanks in advance
    > -rockdale

    You need to also sort the items. The easy way looks like this:
    struct item
    {
    int itemtypeid;
    int itemid;
    bool operator<(item const&rhs)const{

    if (itemtypeid == rhs.itemtypeid)
    return itemid < rhs.itemid;
    else
    return itemtypeid < rhs.itemtypeid;
    }
    };

    typedef std::set<item> ItemList;
    struct order
    {
    int orderid;
    int ordertypeid;
    ItemList itemdata;
    bool operator<(const order& rhs)const
    {
    //assuming unique ids
    //note "backwards" sense
    return rhs.orderid < orderid;
    }

    };

    typedef std::set<order> VectorOrder;


    Lance
    Lance Diduck, Dec 4, 2008
    #3
  4. rockdale

    Guest

    On Dec 4, 11:46 am, rockdale <> wrote:
    > Hi, all:
    >
    > I have a std::vector which contains my struct. The data in the vector
    > is inserted from a std::map, then I will need to sort the vector based
    > on some criteria and then get the sorted data out. my struct is like:
    >
    > struct item
    > {
    >     int itemtypeid;
    >     int itemid;
    >
    > };
    >
    > typedef std::deque<item> ItemList;
    > struct order
    > {
    >      int orderid;
    >      int ordertypeid;
    >      ItemList itemdata;
    >
    > };
    >
    > typedef std::vector<order> VectorOrder;
    >
    > I use a functor to do the sort by orderid
    >
    > this is the functor:
    > class COrderSorter
    > {
    > public:
    >         bool operator()(const order& lhs, const order& rhs)
    >         {
    >                 return lhs.orderid < rhs.order;
    >         }
    >
    > };
    >
    > VectorOrder m_vecOrder
    >
    > std::sort(m_vecOrder.begin(), m_vecOrder.end(), COrderSorter());
    >
    > NOW, I need to sort the order by the its item first by itemtypeid,
    > then by itemid.
    > for example:
    > orderid itemtypeid itemid
    >     1            2           4
    >     1            2           3
    >     1            1           5
    >     2            1           2
    >
    > the final result I need to get:
    > orderid itemtypeid itemid
    >     2            1           2
    >     1            1           5
    >     1            2           3
    >     1            2           4
    >
    > Is there a way to achieve this other than the plain iterate through
    > every order and then iterate through its item?
    > What the efficient, memory consideration about this?


    Others have posted code examples. The general solution is you just
    have to clearly define exactly what criteria makes one item come
    before another one.

    In your case, if itemtypeid for one item is different than another
    item, then the lower itemtypeid comes first -- and you don't really
    care about the itemid at all. If itemtypeid's are identical then you
    turn to the itemid to determine who comes first. Once you can express
    it in English (or whatever), you can translate it to C++, as in the
    posted examples.

    There's no need to iterate twice if you define your criteria
    correctly.

    Jason
    , Dec 4, 2008
    #4
  5. rockdale

    Guest

    On Dec 4, 3:00 pm, ""
    <> wrote:
    > On Dec 4, 11:46 am, rockdale <> wrote:
    >
    >
    >
    > > Hi, all:

    >
    > > I have a std::vector which contains my struct. The data in the vector
    > > is inserted from a std::map, then I will need to sort the vector based
    > > on some criteria and then get the sorted data out. my struct is like:

    >
    > > struct item
    > > {
    > >     int itemtypeid;
    > >     int itemid;

    >
    > > };

    >
    > > typedef std::deque<item> ItemList;
    > > struct order
    > > {
    > >      int orderid;
    > >      int ordertypeid;
    > >      ItemList itemdata;

    >
    > > };

    >
    > > typedef std::vector<order> VectorOrder;

    >
    > > I use a functor to do the sort by orderid

    >
    > > this is the functor:
    > > class COrderSorter
    > > {
    > > public:
    > >         bool operator()(const order& lhs, const order& rhs)
    > >         {
    > >                 return lhs.orderid < rhs.order;
    > >         }

    >
    > > };

    >
    > > VectorOrder m_vecOrder

    >
    > > std::sort(m_vecOrder.begin(), m_vecOrder.end(), COrderSorter());

    >
    > > NOW, I need to sort the order by the its item first by itemtypeid,
    > > then by itemid.
    > > for example:
    > > orderid itemtypeid itemid
    > >     1            2           4
    > >     1            2           3
    > >     1            1           5
    > >     2            1           2

    >
    > > the final result I need to get:
    > > orderid itemtypeid itemid
    > >     2            1           2
    > >     1            1           5
    > >     1            2           3
    > >     1            2           4

    >
    > > Is there a way to achieve this other than the plain iterate through
    > > every order and then iterate through its item?
    > > What the efficient, memory consideration about this?



    Also, I slightly misunderstood your problem. Yes, with the way you
    have your data structures set up, the only real way to do it is to
    sort the vector of orders, then go through each order and sort it's
    items.

    There a few other things you could do but I'm not sure how much is to
    gain by them:

    1. Define your < operators for orders and items, and use a std::set
    instead of a vector. It will naturally keep everything sorted as you
    insert new items and orders. This could be efficient depending on how
    you typically use your data (e.g. if you sort frequently and insert
    less frequently).

    2. Do it like you might do it in an ORM database. Rather than
    storing a list of items in each order, represent an Item and an Order
    independently, and use a third data structure for the links:

    struct Item {
    int itemtypeid;
    int itemid;
    }

    struct Order {
    int ordertypeid;
    int orderid;
    }

    struct OrderedItem {
    Order *order;
    Item *item;
    bool operator < (const OrderedItem &) const;
    }

    Maintain all ordered items as a vector<OrderedItem>. Then, your
    OrderedItem operator < criteria can be what you want... first check
    order ID, then item type ID, then item ID, of the associated order and
    item. To sort by everything, simply sort the OrderedItems.

    That's just an alternative way of doing it; it's the way you'd do it
    if you were working with a database, and may or may not be appropriate
    for your application.


    HTH,
    Jason


    >
    > Others have posted code examples. The general solution is you just
    > have to clearly define exactly what criteria makes one item come
    > before another one.
    >
    > In your case, if itemtypeid for one item is different than another
    > item, then the lower itemtypeid comes first -- and you don't really
    > care about the itemid at all. If itemtypeid's are identical then you
    > turn to the itemid to determine who comes first. Once you can express
    > it in English (or whatever), you can translate it to C++, as in the
    > posted examples.
    >
    > There's no need to iterate twice if you define your criteria
    > correctly.
    >
    > Jason
    , Dec 4, 2008
    #5
  6. rockdale

    Guest

    On Dec 4, 3:09 pm, ""
    <> wrote:
    > On Dec 4, 3:00 pm, ""
    >
    >
    >
    > <> wrote:
    > > On Dec 4, 11:46 am, rockdale <> wrote:

    >
    > > > Hi, all:

    >
    > > > I have a std::vector which contains my struct. The data in the vector
    > > > is inserted from a std::map, then I will need to sort the vector based
    > > > on some criteria and then get the sorted data out. my struct is like:

    >
    > > > struct item
    > > > {
    > > >     int itemtypeid;
    > > >     int itemid;

    >
    > > > };

    >
    > > > typedef std::deque<item> ItemList;
    > > > struct order
    > > > {
    > > >      int orderid;
    > > >      int ordertypeid;
    > > >      ItemList itemdata;

    >
    > > > };

    >
    > > > typedef std::vector<order> VectorOrder;

    >
    > > > I use a functor to do the sort by orderid

    >
    > > > this is the functor:
    > > > class COrderSorter
    > > > {
    > > > public:
    > > >         bool operator()(const order& lhs, const order& rhs)
    > > >         {
    > > >                 return lhs.orderid < rhs.order;
    > > >         }

    >
    > > > };

    >
    > > > VectorOrder m_vecOrder

    >
    > > > std::sort(m_vecOrder.begin(), m_vecOrder.end(), COrderSorter());

    >
    > > > NOW, I need to sort the order by the its item first by itemtypeid,
    > > > then by itemid.
    > > > for example:
    > > > orderid itemtypeid itemid
    > > >     1            2           4
    > > >     1            2           3
    > > >     1            1           5
    > > >     2            1           2

    >
    > > > the final result I need to get:
    > > > orderid itemtypeid itemid
    > > >     2            1           2
    > > >     1            1           5
    > > >     1            2           3
    > > >     1            2           4

    >
    > > > Is there a way to achieve this other than the plain iterate through
    > > > every order and then iterate through its item?
    > > > What the efficient, memory consideration about this?

    >
    > Also, I slightly misunderstood your problem. Yes, with the way you
    > have your data structures set up, the only real way to do it is to
    > sort the vector of orders, then go through each order and sort it's
    > items.


    Which, btw, is going to work just fine, and in some cases may or may
    not be more efficient than doing it any other way. Are you currently
    experiencing performance or memory problems?

    (Sorry about all the emails).

    Jason
    , Dec 4, 2008
    #6
  7. rockdale

    LR Guest

    rockdale wrote:
    > Hi, all:
    >
    > I have a std::vector which contains my struct. The data in the vector
    > is inserted from a std::map, then I will need to sort the vector based
    > on some criteria and then get the sorted data out. my struct is like:
    >
    > struct item
    > {
    > int itemtypeid;
    > int itemid;
    > };
    >
    > typedef std::deque<item> ItemList;
    > struct order
    > {
    > int orderid;
    > int ordertypeid;
    > ItemList itemdata;
    > };
    >
    > typedef std::vector<order> VectorOrder;
    >
    > I use a functor to do the sort by orderid
    >
    > this is the functor:
    > class COrderSorter
    > {
    > public:
    > bool operator()(const order& lhs, const order& rhs)
    > {
    > return lhs.orderid < rhs.order;
    > }
    > };
    >
    > VectorOrder m_vecOrder
    >
    > std::sort(m_vecOrder.begin(), m_vecOrder.end(), COrderSorter());
    >
    > NOW, I need to sort the order by the its item first by itemtypeid,
    > then by itemid.
    > for example:
    > orderid itemtypeid itemid
    > 1 2 4
    > 1 2 3
    > 1 1 5
    > 2 1 2
    >
    > the final result I need to get:
    > orderid itemtypeid itemid
    > 2 1 2
    > 1 1 5
    > 1 2 3
    > 1 2 4
    >
    >
    > Is there a way to achieve this other than the plain iterate through
    > every order and then iterate through its item?



    I'm not sure that I understand the above. Wouldn't it be easier to
    create a struct,

    struct OI { // sorry, I couldn't think of a better name
    int orderid;
    int itemtypeid;
    int itemid;
    };

    and a std::vector<OI> with one element for every "item" in m_vecOrder's
    itemdatas and sort it according to whatever criteria you want?

    As it is, I don't quite see how sorting m_vecOrder and then sorting each
    itemdata member of m_vecOrder or even iterating through it could achieve
    the results you need, since it seems you can have the same itemtypeid in
    more than one struct of type order.

    But I'm almost certain that I didn't understand something. What if there
    exists the possibility that this is your data?

    order item itemid
    1 1 10
    1 2 5
    1 3 10
    2 1 5
    3 2 7
    3 3 7
    4 2 2

    Would this be your final output?
    order item itemid
    2 1 5
    1 1 10
    4 2 2
    1 2 5
    3 2 7
    3 3 7
    1 3 10


    If not, then sorry, but I don't understand what you wanted.


    LR
    LR, Dec 5, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Anonymous
    Replies:
    20
    Views:
    4,288
    Pete Becker
    Mar 30, 2005
  2. Jason Heyes
    Replies:
    8
    Views:
    718
    Andrew Koenig
    Jan 15, 2006
  3. Replies:
    1
    Views:
    484
    Marcus Kwok
    Apr 6, 2007
  4. Alexis Berry

    Generics for a multiplevalue hashmap

    Alexis Berry, Jul 18, 2011, in forum: Java
    Replies:
    8
    Views:
    729
    Stefan Ram
    Jul 19, 2011
  5. Richard
    Replies:
    2
    Views:
    382
    lewbloch
    Jul 21, 2011
Loading...

Share This Page