Thread: Sorting Vector of string from another vector of strings

  1. #1
    Registered User subdene's Avatar
    Join Date
    Jan 2002
    Posts
    367

    Sorting Vector of string from another vector of strings

    Hello,

    I am having a bit of brain freeze today and cannot figure out the best way to implement this using the STL algorithms. I have these two vectors

    Code:
    	
    vector<string> valuesToSort = {"aa", "cc", "bb"};
    vector<string> orderToFollow = {"cc", "bb", "gg", "ii", "aa"};
    I want to sort valuesToSort by orderToFollow. So, using orderToFollow, valuesToSort will be modified to:

    Code:
    valuesToSort = {"cc", "bb", "aa"};
    Or if the values were the other way round:

    Code:
    	
    vector<string> valuesToSort =  {"cc", "bb", "gg", "ii", "aa"};
    vector<string> orderToFollow = {"aa", "cc", "bb"};
    valuesToSort would be:

    Code:
    valuesToSort = {"aa", "cc", "bb", "gg", "ii"};
    So if a value that do not exist in the valuesToSort their position is maintained relative. I am thinking of stable_sort with a comparitor but not quite sure how to implement it. Heres what I have so far:

    Code:
    	//values are distinct
    	vector<string> valuesToSort = {"aa", "cc", "bb"};
    	vector<string> orderToFollow = {"cc", "bb", "gg", "ii", "aa"};
    
    
    	//vector<string> orderToFollow = {"aa", "cc", "bb"};
    	//vector<string> valuesToSort = {"cc", "bb", "gg", "ii", "aa"};
    
    
    	vector<string> newOrder;
    
    	for (int i = 0; i < orderToFollow.size(); ++i)
    	{
    		auto val = find(valuesToSort.begin(), valuesToSort.end(), orderToFollow[i]);
    		if (val != valuesToSort.end())
    		{	
    			iter_swap(valuesToSort.begin() + i, val);
    		}
    	}
    
    	cout << "Order to follow:" << endl;
    	for (auto i : orderToFollow) cout << i << "\t";
    	cout << endl << endl;
    
    	cout << "Values to sort:" << endl;
    	for (auto i : valuesToSort) cout << i << "\t";
    	cout << endl<< endl;
    
    	cout << "New order:" << endl;
    	for (auto i : newOrder) cout << i << "\t";
    	cout << endl<< endl;
    This current implementation goes out of bounds on the iter_swap.

    All the strings when being searched should be compared case insensitive and there will never be any duplicates of a string in any vector, they will always be unique. So this could be a set container.
    Be a leader and not a follower.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    By any chance, would you be able to combine them as a pair or say, as members of an object?
    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

  3. #3
    Registered User subdene's Avatar
    Join Date
    Jan 2002
    Posts
    367
    I am currently looking into using a multi_index conatiner:

    Code:
    #include <boost/multi_index_container.hpp>
    #include <boost/multi_index/ordered_index.hpp>
    #include <boost/multi_index/member.hpp>
    #include <boost/multi_index/composite_key.hpp>
    
    using boost::multi_index_container;
    using namespace boost::multi_index;
    
    struct NameOrder
    {
    	explicit NameOrder(std::wstring name, unsigned int pos) : m_Name(name), m_Pos(pos){}
    	
    	std::wstring m_Name;
    	unsigned int m_Pos;
    };
    
    typedef multi_index_container<
    	NameOrder,
    	indexed_by<		
    				ordered_unique<member<NameOrder, unsigned int, &NameOrder::m_Pos> >
    	>
    > NAME_ORDER;
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	using namespace std;
    
    	//values are distinct
    	vector<string> valuesToSort = {"aa", "cc", "bb"};
    	vector<string> orderToFollow = {"cc", "bb", "gg", "ii", "aa"};
    
    	NAME_ORDER order;
    
    
    	for (int i = 0; i < valuesToSort.size(); ++i)
    	{
    		auto val = find(orderToFollow.begin(), orderToFollow.end(), valuesToSort[i]);
    		if (val != orderToFollow.end())
    		{
    			order.insert(NameOrder(*val, std::distance(orderToFollow.begin(), val)));
    		}
    	}
    }
    Conceptually, these two vectors represent two independent collections on different business objects. They can't really be refactored easily as you say.
    Be a leader and not a follower.

  4. #4
    Registered User
    Join Date
    Nov 2008
    Posts
    30
    Do you have to sort the vector in-place? You anyway need to convert the original vector to an unordered set, for performance reasons. So, you might as well empty the original vector and use it.

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Hmm... Would it be possible to just `std::sort` and the appropriate functor?

  6. #6
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I don't really see any sort of pattern that would make std::sort a good choice. I did however have a think on it, and one way to do it would be to copy from order to follow.
    Code:
    if (vectorToSort.size() > orderToFollow.size())
    {
        // Push elements not in orderToFollow to the end. 
        auto mark = remove_if(vectorToSort.begin(), vectorToSort.end(), [&](string n) { 
            return find(orderToFollow.begin(), orderToFollow.end(), n) == orderToFollow.end(); 
        });
        // Compute how much of the order to follow to copy.
        auto copyEnd = std::distance(vectorToSort.begin(), mark);
        // Copy.
        vectorToSort.assign(orderToFollow.begin(), orderToFollow.begin()+copyEnd);
    }
    else 
    {
        // Remove elements that will not be sorted. Note: this is possibly destructive to the orderToFollow vector. 
        // Copy it first to preserve the original order.
        auto mark = remove_if(orderToFollow.begin(), orderToFollow.end(), [&](string n) { 
            return find(vectorToSort.begin(), vectorToSort.end(), n) == vectorToSort.end();
        });
        // ...
        // Assign the sorted vector.
        vectorToSort.assign(orderToFollow.begin(), mark);
    }
    I probably skipped a few steps because I'm too lazy to do it.

    I still think this is bad. I would like to use an unordered set instead. I really don't see how this is "sorted order".
    Last edited by whiteflags; 08-02-2016 at 04:03 PM.

  7. #7
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Well, I did specify "appropriate functor". I think std::sort expects a binary functor that returns a boolean. So all you have to do for your array is write a function that takes two valid entries of the array and returns a boolean indicating "less than".

    The core of the logic would come from this:
    Code:
    std::vector<std::string> orderToFollow{ "cc", "bb", "gg", "ii", "aa" };
    For the sake of performance the logic can of course be refactored but the idea is, you could greatly simplify your problem by just creating a simple function that takes two strings and returns the appropriate boolean value.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Perhaps create a map for ordertofollow consisting of pairs of string, index. Then use a lambda function or comparator to find indexes for both strings of a compare. If the string (key) is not in the map, use size as the index value (so all missing keys will have the same index). To preserve the order of keys not in the map, use std::stable_sort().

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    That idea worked for me when I tested it, rcgldr... though I did simplify it. My lambda returned false if either value to sort wasn't a key.

  10. #10
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Quote Originally Posted by rcgldr View Post
    Perhaps create a map for ordertofollow consisting of pairs of string, index. Then use a lambda function or comparator to find indexes for both strings of a compare. If the string (key) is not in the map, use size as the index value (so all missing keys will have the same index). To preserve the order of keys not in the map, use std::stable_sort().
    Ha, I actually thought of this as well. You could easily use `std::map` or `std::unordered_map` to accomplish this goal easily.

    I must admit, this was a very interesting problem to try and solve!

  11. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by whiteflags View Post
    That idea worked for me when I tested it, rcgldr... though I did simplify it. My lambda returned false if either value to sort wasn't a key.
    std::stable_sort() does a compare(right object, left object), expecting it to return the result of right object < less object. Returning false means the left object is less than or equal to the right object (meaning objects are in order, left before right). If right object string is found, but left object string is not found, then the lambda should return true.

  12. #12
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Quote Originally Posted by rcgldr View Post
    std::stable_sort() does a compare(right object, left object), expecting it to return the result of right object < less object. Returning false means the left object is less than or equal to the right object (meaning objects are in order, left before right). If right object string is found, but left object string is not found, then the lambda should return true.
    Then I guess the only question is, have you written tests? XD

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by rcgldr View Post
    std::stable_sort() does a compare(right object, left object), expecting it to return the result of right object < less object.
    Quote Originally Posted by MutantJohn View Post
    Then I guess the only question is, have you written tests?
    I'm not sure what you mean. I've looked at the actual code in <algorithm>, and I've also stepped through the code. In general STL expects a compare function to be a less than compare. In order for stable_sort to be stable, it only reorders data if a left object is greater than a right object, otherwise it leaves the objects in place. Since the compare is a less than compare, it swaps the parameters from what you would usually expect, to compare for right object less than left object, which is the equivalent of not(left object less than or equal to right object), if the result is true, the objects are out of order.

  14. #14
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Well, it was largely a joke. Yes, you are probably right but in my mind, you never know until you actually run the code and see what you get.

    OP, I don't know if we confused you or not but in C++ and any other non-functional programming context, a "functor" is synonymous with "callable object". So these would be your function pointers, your lambdas, your std::function's, your objects that overload operator(). In this case, std::sort expects a "binary" one which is a fancy way of saying "two arguments", in this case two adjacent array entries. By focusing your attention on writing the callable object, you've massively simplified your problem while also still relying on the STL.

    I don't know if that was redundant information but I haven't seen the OP post since so I was thinking maybe we scared them off with our high highfalutin programmin' talk.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 03-21-2016, 09:38 AM
  2. Replies: 9
    Last Post: 09-22-2013, 07:00 AM
  3. Copying string vector to char vector
    By Ducky in forum C++ Programming
    Replies: 21
    Last Post: 07-10-2013, 11:22 AM
  4. Converting string vector to integer vector
    By CPlus in forum C++ Programming
    Replies: 4
    Last Post: 05-08-2010, 05:43 AM
  5. From it string to vector of strings.
    By krakz in forum C Programming
    Replies: 5
    Last Post: 01-06-2003, 08:54 AM

Tags for this Thread