1

I am wondering how I can sort a set that contains strings. For example, I have a set:

std::set<std::string> setA = {"B","A","C"}

Then I wanna use this to do the sorting:

std::sort(setA.begin(),setA.end());

But the C++ compiler cannot let it pass. The error message reports: 

40: error: invalid operands to binary expression
('std::__1::__tree_const_iterator<std::__1::basic_string<char>, std::__1::__tree_node<std::__1::basic_string<char>, void *> *, long>'
and 'std::__1::__tree_const_iterator<std::__1::basic_string<char>, std::__1::__tree_node<std::__1::basic_string<char>, void *> *, long>')
difference_type __len = __last - __first;

Then I recheck sort function in C++, it seems that it can only deal with int, double, long ... but there is no way to use this function sort() to sort strings.

So how can I sort strings?

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
uniqueliu
  • 79
  • 2
  • 9

3 Answers3

4

std::sort requires random access iterators while std::set provides only bidirectional iterators.

Generally speaking, any try to sort a std::set contradicts to the design of this container, because it stores its elements in the sorted order.

From the cppreference.com:

std::set is an associative container that contains a sorted set of unique objects of type Key.

Edgar Rokjān
  • 17,245
  • 4
  • 40
  • 67
  • 1
    You can also say that it uses a red black tree most of the time. At least in gcc as it is apparent from the compilation from error. `__tree_node` – Shiv Jan 01 '17 at 16:30
  • @Bugbugbuggerbuggered It is not significant how it stores its elements internally. – Edgar Rokjān Jan 01 '17 at 16:31
  • I do not want to get into details but the thing is any storage backend with a tree cannot provide random access iterator. It has to be sequential/linear(do not know which is more suitable word) storage. – Shiv Jan 01 '17 at 16:33
  • @Bugbugbuggerbuggered I believe it can provide. But it would be inefficient. – Edgar Rokjān Jan 01 '17 at 16:34
  • Can does not mean will. It will be terribly inefficient not only inefficient. – Shiv Jan 01 '17 at 16:35
  • Try doing random access to a tree node and you will know the pain. – Shiv Jan 01 '17 at 16:38
0

You cannot resort a set, how it sorts is part of the type of the particular set. A given set has a fixed set order that cannot be changed.

You could create a new set with the same data relatively easily. Just create a new set that sorts based on the new criteria.

If you want to use the two sets in the same code, you'll have to abstract the access to the underlying set.

Copied shamelessly from Sorting Sets using std::sort. Change your container.

Community
  • 1
  • 1
Shiv
  • 1,912
  • 1
  • 15
  • 21
0

You just insert these three strings and they are already sorted if your using std::set

set<string> s;
s.insert("A");
...
OR
set<string> str = {"A", "B", "C", "D"}; //C++ 11
OR
string s[] = {"A", "B", "C", "D"};
set<string> str(s, s+ sizeof(s) / sizeof(s[0]));

And they are sorted.

If you want custom sorting (which is probably the case with you?)

Then use vector<string>() and sort()

bool cmp(string a, string b)
{
    // do something and return boolean
}
vector<string> v;
v.push_back("s");
...

sort(v.begin(),v.end(),cmp);

Btw you can't resort set as the sorting of it's elements is entirely upto the set's standard implementation as done in c++.

user2736738
  • 30,591
  • 5
  • 42
  • 56