jason.cipriani@gmail.com
12/4/2008 8:09:00 PM
On Dec 4, 3:00 pm, "jason.cipri...@gmail.com"
<jason.cipri...@gmail.com> wrote:
> On Dec 4, 11:46 am, rockdale <rockdale.gr...@gmail.com> 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