Different sorting on a vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <locale>

struct Item {

	bool operator()(const Item& item1, const Item& item2) const
	{
		std::string st1{ item1.name };
		std::string st2{ item2.name };
		for (auto& c : st1)
			c = std::toupper(c, std::cout.getloc());
		for (auto& c : st2)
			c = std::toupper(c, std::cout.getloc());
		return st1 < st2;
	}

	std::string name;
	int iid;
	double value;
};

//***************************

int main()
{
	Item myItem;
	std::vector<Item> vi;
	std::ifstream in{ "input.txt" };

	if (!in) {
		std::cout << "Could not open file!\n\n";
		system("pause");
		return 1;
	}

	std::string s;
	int id;
	double value;

	for (size_t i = 0; i < 10; ++i) {
		in >> s >> id >> value;
		vi.push_back({ s, id, value });
	}

	sort(vi.begin(), vi.end(), myItem);
        // here

	for (const auto& v : vi)
		std::cout << v.name << "  " << v.iid << "  " << v.value << '\n';
	std::cout << "\n";

	system("pause");
	return 0;
}

If we were to have another sort on line 49 to sort the vector, this time, by iid, what would be your ideas on how to accomplish it in the project?
Last edited on
> If we were to have another sort on line 49 to sort the vector, this time, by iid,
> what would be your ideas on how to accomplish it in the project?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <algorithm>

// predicate to compare member objects of class T using CMP
template < typename T, typename MEM, typename CMP = std::less<> > struct cmp_member
{
    constexpr cmp_member( MEM T::*pm, CMP cmp = CMP{} ) noexcept : pm(pm), cmp(cmp) {}

    bool operator() ( const T& a, const T& b ) const { return cmp( a.*pm, b.*pm ) ; }

    MEM T::*pm ;
    CMP cmp ;
};

int main()
{
    struct A { int v = 0 ; std::string str ; };

    A seq[] { { 32, "ijk" }, { 57, "abc" }, { 12, "zzz" }, { 25, "def" }, { 21, "pqr" } } ;
    const auto print_seq = [&] () { for( A& a : seq ) std::cout << '{' << a.v << ',' << a.str << "} " ; std::cout << '\n' ; };
    std::cout << "                   unsorted: " ;
    print_seq() ;

    std::cout << "               sort on A::v: " ;
    std::sort( std::begin(seq), std::end(seq), cmp_member{ &A::v } ) ;
    print_seq() ;

    std::cout << "             sort on A::str: " ;
    std::sort( std::begin(seq), std::end(seq), cmp_member{ &A::str } ) ;
    print_seq() ;

    std::cout << "  sort on A::v (descending): " ;
    std::sort( std::begin(seq), std::end(seq), cmp_member{ &A::v, std::greater<>{} } ) ;
    print_seq() ;
}

http://coliru.stacked-crooked.com/a/e59f0120b308793c
Too complicated for me! There's huge difference between the two codes.
But thank you for your time.
Using lambda:
1
2
3
4
sort(vi.begin(), vi.end(), [](const Item& i1, const Item& i2)
{
  return (i1.iid < i2.iid);
});
Hello frek,

To start with it would help to know IDE you are using and which C++ standard you are compiling to. If you do not know the standard the IDE will help.

For something a bit simpler you can have a look at http://www.cplusplus.com/reference/algorithm/sort/

In the example code I would look at line 6.

For your use consider
1
2
bool sortStr (const Item& item1, const Item& item2)
bool sortId ((const Item& item1, const Item& item2)

For "sortStr" use what you have for the the content of the {}s.
For "sortId" change what is between the {}s to check the ID number.

Just a thought for now as I have not tried it yet.

Andy
@frek - have you come across lambdas yet? IMO that is the easier way to do these. See coder777's code above for an example. The Item struct operator() can also be replaced with a lambda:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cctype>
#include <locale>

struct Item {
	std::string name;
	int iid {};
	double value {};
};

std::ostream& operator<<(std::ostream& os, const Item& v)
{
	return os << v.name << "  " << v.iid << "  " << v.value;
}

std::istream& operator>>(std::istream& is, Item& v)
{
	return is >> v.name >> v.iid >> v.value;
}

auto sortItem {[](const auto& i1, const auto& i2) {
	std::string st1 {i1.name};
	std::string st2 {i2.name};

	for (auto& c : st1)
		c = std::toupper(c, std::cout.getloc());

	for (auto& c : st2)
		c = std::toupper(c, std::cout.getloc());

	return st1 < st2;
}};

auto sortiid {[](const auto& i1, const auto& i2)
{
	return (i1.iid < i2.iid);
}};

int main()
{
	std::ifstream in {"input.txt"};

	if (!in) {
		std::cout << "Could not open file!\n\n";
		return 1;
	}

	std::vector<Item> vi;

	for (Item it; in >> it; vi.emplace_back(std::move(it)));

	std::sort(vi.begin(), vi.end(), sortItem);

	for (const auto& v : vi)
		std::cout << v << '\n';

	std::cout << '\n';

	std::sort(vi.begin(), vi.end(), sortiid);

	for (const auto& v : vi)
		std::cout << v << '\n';

	std::cout << '\n';
}


Which given an input file of:


qwer 92 56.78
asdf 45 67.89
zxxc 78 98.88


displays:


asdf  45  67.89
qwer  92  56.78
zxxc  78  98.88

asdf  45  67.89
zxxc  78  98.88
qwer  92  56.78

Last edited on
@frek:
Your Item has operator() that can act as predicate. It is needlessly a non-static member function. (As non-static member function it has access to three Items: item1, item2, and *this.)

The traditional method to provide the default ordering is to create a standalone operator<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Item {
	std::string name;
	int iid;
	double value;
};

bool operator< (const Item& item1, const Item& item2)
{
  // code
}

//***************************

int main()
{
  std::vector<Item> vi;
  std::sort( vi.begin(), vi.end() ); // uses the operator< 

For the non-default ordering you use function objects / lambdas / functions.

1
2
3
4
5
6
7
bool byiid (const Item& item1, const Item& item2)
{
  return item1.iid < item2.iid;
}


  std::sort( vi.begin(), vi.end() byiid );


The program by JLBorges has three unique cmp_member structs that are all generated from one template.

The lambdas by seeplus are also effectively templates. Mostly because they use the auto type deduction mechanism.
Last edited on
Thank you. I used a functor and lambdas for various sortings. But one question regarding erase:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main()
{
	std::vector<std::string> vs{ "Cat", "Elephant", "Dog", "Ant", "Tiger" };
	std::cout << "Enter two names for removal: ";
	std::string str1, str2;
	std::cin >> str1 >> str2;
	std::cout << "Remove (erase) two Items identified by name from vs\n";

	/* for (auto iter = vs.begin(); iter != vs.end();) {
			if (*iter == str1 || *iter == str2)
				iter = vs.erase(iter);
			else
				++iter;
		}
		*/

	remove_if(vs.begin(), vs.end(),
		[=](const std::string& s) { return (s == str1 || s == str2); });

	/* vs.erase(remove_if(vs.begin(), vs.end(),
		[=](const std::string& s) { return (s == str1 || s == str2); })
		, vs.end()); */

	for (auto s : vs)
		std::cout << s << ' ';
	std::cout << '\n';

	system("pause");
	return 0;
}

In this simplified code both commented versions for removal work properly. But I don't know why I can't rely on remove_if alone to remove the last element from the vector!
Last edited on
remove_if does not remove elements.

It cannot alter the properties of the object containing the range of elements (i.e., it cannot alter the size, etc):
http://www.cplusplus.com/reference/algorithm/remove_if/

The remove_if is more a move_elements_that_we_want_to_keep_into_front_of_range.


Two reasons:
* Genericity: you can remove_if a range that is in plain array, but you cannot change its static size anyway.
* One function, one task principle
For C++20, there is now erase_if() which effectively combines erase with remove_if

See https://en.cppreference.com/w/cpp/container/vector/erase2
@keskiverto
Yes, it does not remove elements but it does remove data!

Enter two names for removal: Cat Elephant
Remove (erase) two Items identified by name from vs
Dog Ant Tiger
Press any key to continue . . .
And my question is why can't it remove data of the last element!?

@seeplus
For C++20, there is now erase_if() which effectively combines erase with remove_if
That's a nice future but my compiler, VS, can cover C++17 at the peak.

Another question!
Are my data members initialised by default or shall I initialise them in the struct?
1
2
3
std::string name;
int iid;
double value; 
Last edited on
It does not "remove" data. With more telling loop:
1
2
3
	for (auto s : vs)
		std::cout << "# " << s << '\n';
	std::cout << '\n';

Enter two names for removal: Elephant Cat
Remove (erase) two Items identified by name from vs
# Dog
# Ant
# Tiger
# Elephant
# Cat

It seems that the compiler/library in cpp.sh does effectively swap strings on move assignment.
remove_if
the elements between the returned iterator and last are left in a valid but unspecified state.

Your error is to print the entire vector after the remove_if. You print both the elements that were not removed and the remaining unspecified content.

If your library's move makes the moved from string empty, then you print cout << "" << ' '; which you can mistake as nothing, i.e. as removed.

If you try to remove Tiger -- there is nothing behind Tiger so nothing will be moved to the last element, nor will it be moved anywhere. Hence the last element is not modified.

If you want to use mere remove_if, then you have to keep track of the "logical size" of the vector yourself:
1
2
3
4
5
auto stop = remove_if(vs.begin(), vs.end(),
                [=](const std::string& s) { return (s == str1 || s == str2); });
for ( auto s = vs.begin(); s != stop; ++s )
    std::cout << "# " << *s << '\n';
std::cout << '\n';
Last edited on
For C++20, there is now erase_if() which effectively combines erase with remove_if
That's a nice future but my compiler, VS, can cover C++17 at the peak.


The current version of VS2019 supports it.

Set C++ Language standard to Preview.

This link details what aspects of the various C++ standards are implemented by various compilers
https://en.cppreference.com/w/cpp/compiler_support

valid but unspecified state
The problem is that! Some compiler like VS works as though it removes the elements/data whilst other ones work differently. This behavior of that API is error-prone "to me" and using it for a non-expert is ask for trouble.
Anyway, the main job of this function is to return an iterator back to the caller pointing to the one-past the last element meeting the predator condition. Lines 25 through 27 of my prior code above works properly using that main job by erase. Anyway, I guess the more straightforward and easy to spot alternative is the method written on lines 14 through 19.

@seeplus
I dare not setting the Language standards to preview! I'm not a C++ expert and may think of preview standards as the source of unexpected results before any other case when the code doesn't work the way it's assumed.
Last edited on
> Anyway, the main job of this function is to return an iterator back to the caller
> pointing to the one-past the last element meeting the predator condition.

No. That is the job that std::partition is designed to do; std::partition preserves values; it just swaps elements. https://en.cppreference.com/w/cpp/algorithm/partition
1
2
3
4
5
6
7
8
9
10
pivot = std::partition( first, last, pred );
// post-conditions:
// pred is true  for every element in range [first,pivot)
// pred is false for every element in range [pivot,last)

pivot = std::remove_if( first, last, pred );
// post-conditions:
// pred is false for every element in range [first,pivot)
// value of elements in range [pivot,last) is unspecified
// relative order of the elements that remain is preserved 


frek wrote:
The problem is that! Some compiler like VS works as though it removes the elements/data whilst other ones work differently.

No. Your problem is that you essentially do:
1
2
A = std::move(B);
std::cout << A << ' ' << B << '\n';

You print B after the move even though you know that you have moved it.
Last edited on
I dare not setting the Language standards to preview! I'm not a C++ expert and may think of preview standards as the source of unexpected results before any other case when the code doesn't work the way it's assumed.


For VS2019, preview enables standard C++20 features that have been implemented. It also enables any C++23 features that have been approved and implemented. Note that C++23 is a work in progress and features may change between approval and the final standard. The link in my previous post details the features in each version of C++ and which are currently implemented by which compiler.
@JLBorges
std::partition preserves values; it just swaps elements.
Good point, thanks.

@keskiverto
Thanks for the code. Yes, as I said, erase in my code uses that pivot and erases the rest of elements.

You print B after the move even though you know that you have moved it.
I simply merely wish to know if the incidence of removing elements took place by the API or not. That's why I print them on output and it's valid. (Otherwise I wouldn't recognise the exact job of erase/remove/remove_if!)

@seeplus
Yes, thank you.
Topic archived. No new replies allowed.