Thread: Sorting list of shared pointers

  1. #1
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654

    Sorting list of shared pointers

    I need to sort a list of std::shared_ptr based on criteria defined via an overloaded operator < in the struct I'm storing via the smart pointers.
    Naturally, the std::shared_ptr define operator < as

    Code:
    template<class _Ty1,
    	class _Ty2>
    	bool operator<(const shared_ptr<_Ty1>& _S1,
    		const shared_ptr<_Ty2>& _S2)
    	{	// test if shared_ptr < shared_ptr
    	return (_S1.get() < _S2.get());
    	}
    That is, comparison of the pointers, while boost's smart pointer defines the operator via a comparison of the pointees.

    So say I have
    Code:
    std::list<std::shared_ptr<my_t>> list;
    // Add stuff to list
    list.sort();
    What would be a good approach to sort the list using the operator < defined in my_t?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #2
    Registered User
    Join Date
    Dec 2008
    Location
    Black River
    Posts
    128
    You can pass a strict weak ordering predicate to list::sort:

    Code:
    bool myt_lt (const std::shared_ptr<my_t>& left,
       const std::shared_ptr<my_t>& right)
    {
       return (*left.get() < *right.get());
    }
    
    ...
    std::list<std::shared_ptr<my_t> > list;
    ...
    list.sort(myt_sort);
    Stick close to your desks and never program a thing,
    And you all may sit in the standards commitee!

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    This doesn't work generically, though, if I have a parameter type T.
    Code:
    template<typename T> void mfunc()
    {
        std::list<std::shared_ptr<T>> list;
        // Add stuff to list
        list.sort();
    }
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User
    Join Date
    Dec 2008
    Location
    Black River
    Posts
    128
    So, make the predicate a template:

    Code:
    template<class T>
    bool shared_ptr_lt (const std::shared_ptr<T>& left,
       const std::shared_ptr<T>& right)
    {
        return (*left.get() < *right.get());
    }
    
    template<class T>
    void func()
    {
       std::list<std::shared_ptr<T> > list;
       //...
       list.sort(shared_ptr_lt<T>);
    }
    Stick close to your desks and never program a thing,
    And you all may sit in the standards commitee!

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Ah, I missed that predicate part. I wasn't aware sort had an overload that takes a predicate function to sort.
    Thanks. That's what I need.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Does Ronix's example even compile? I believe that you have to use a class template rather than a function template, and then pass an object of that class template to the sort member function.

    EDIT:
    Ooh, it does work.
    Last edited by laserlight; 10-23-2010 at 12:26 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Dec 2008
    Location
    Black River
    Posts
    128
    Compiles for me on g++ 4.4.1, although I used std::auto_ptr because I don't know the correct header for std::shared_ptr.
    Stick close to your desks and never program a thing,
    And you all may sit in the standards commitee!

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    It should be in <memory>. But it also requires C++0x enabled.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You could use std::tr1::shared_ptr if std::shared_ptr is not available.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Banal internet user
    Join Date
    Aug 2002
    Posts
    1,380
    If we're talking about C++0x you could take Ronix's example a step further and use a lambda for the predicate parameter to sort:
    Code:
    template<typename T>
    void mfunc()
    {
        std::list<std::shared_ptr<T>> list;
        // Add stuff to list
        list.sort([](const std::shared_ptr<T> & lhs, const std::shared_ptr<T> & rhs)
        {
            return (*lhs.get() < *rhs.get());
        });
    }

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I would rather have a functor or free function to do this, though, since it avoids code duplication and is shorter.
    Though that works, I think I would it for special occasions.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. c program that accepts and executes commands?
    By Cimposter in forum C Programming
    Replies: 3
    Last Post: 09-30-2009, 02:58 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  4. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 07:29 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM