-1
    class AP {
public:
  AP():
    BSSID(""),
    SSID(""),
    PASSWORD(""),
    LinkStatus(eWifiAPLinkStatus_UnConnected),
    AuthType(eWifiSecurityType_Unknown),
    SignalLevel(eWifiAPSignalStrength_level0),
    Remembered(eWifiRememberedAP_Unknown)  {}

  AP(std::string ssid, WifiSecurityType authType, std::string password);
  AP(std::string bssid, std::string ssid, WifiAPSignalStrength sigLev,WifiSecurityType authType,int SignalDB);
  AP(std::string ssid, WifiAPSignalStrength sigLev,WifiSecurityType authType,int SignalDB);

  AP &operator=(const AP &);
  AP(const AP &);
  std::string BSSID;
  std::string SSID;
  std::string PASSWORD;
  WifiAPLinkStatus LinkStatus;
  WifiSecurityType AuthType; /// PasswordProtected is defined in patac's Proto
  WifiAPSignalStrength SignalLevel;
  int SignalDB;
  WifiRememberedAP Remembered;

  std::string getBSSID() const;
  void setBSSID(const std::string &value);
  std::string getSSID() const;
  void setSSID(const std::string &value);
  std::string getPASSWORD() const;
  void setPASSWORD(const std::string &value);
  WifiAPLinkStatus getLinkStatus() const;
  void setLinkStatus(const WifiAPLinkStatus &value);
  WifiSecurityType getAuthType() const;
  void setAuthType(const WifiSecurityType &value);
  WifiAPSignalStrength getSignalLevel() const;
  void setSignalLevel(const WifiAPSignalStrength &value);
  WifiRememberedAP getRemembered() const;
  void setRemembered(const WifiRememberedAP &value);
  int getSignalDB() const;
  void setSignalDB(int value);
};

std::ostream& operator<<(std::ostream &output, const AP &D);

std::vector ScanAps;

AP is class that has a getter function(among others functions) getSignalDB to return an int:

My question is :

 std::sort(ScanAps.begin(),ScanAps.end(),
               [](const AP &m, const AP &n)-> bool{return
      m.getSignalDB() < n.getSignalDB(); });

...will sometimes crash the whole process, but

 std::stable_sort(ScanAps.begin(),ScanAps.end(),
               [](const AP &m, const AP &n)-> bool{return
      m.getSignalDB() < n.getSignalDB(); });

...won't. And both sort take no effect:

PRINT_ELEMENTS(ScanAps,"AFTER SORT ScanAps IS :\n");

Print Results is (when not crash, attention to last col):

BSSID:fc:8b:97:5c:c1:fd SSID:dlink  PASSWORD:  LINKSTAUS:2  SignalDB:-57
BSSID:cc:d5:39:5d:d4:b0 SSID:YFVEGROUP  PASSWORD:  LINKSTAUS:2  SignalDB:-70
BSSID:fc:8b:97:5c:e7:3c SSID:dlink_mwang  PASSWORD:  LINKSTAUS:2  SignalDB:-73
BSSID:5c:63:bf:73:e9:6a SSID:eagle_link  PASSWORD:  LINKSTAUS:2  SignalDB:-46
BSSID:cc:d5:39:9e:30:b0 SSID:YFVEGROUP  PASSWORD:  LINKSTAUS:2  SignalDB:-49
BSSID:00:36:76:1c:ab:3f SSID:360WiFi-AB3F  PASSWORD:  LINKSTAUS:2  SignalDB:-54
BSSID:fc:8b:97:5c:bb:40 SSID:dlink_wj  PASSWORD:  LINKSTAUS:2  SignalDB:-57
BSSID:fc:8b:97:5c:e8:9f SSID:ARCH-HP_Network  PASSWORD:  LINKSTAUS:2  SignalDB:-62
BSSID:fc:8b:97:5c:d8:3c SSID:dlink_sammu  PASSWORD:  LINKSTAUS:2  SignalDB:-71
BSSID:cc:d5:39:9e:30:be SSID:YFVEGUEST  PASSWORD:  LINKSTAUS:2  SignalDB:-58
BSSID:cc:d5:39:e3:3c:00 SSID:YFVEGROUP  PASSWORD:  LINKSTAUS:2  SignalDB:-62
BSSID:cc:d5:39:9e:30:bf SSID:YFVEGROUP  PASSWORD:  LINKSTAUS:2  SignalDB:-75
BSSID:98:ff:d0:b4:07:2a SSID:Lenovo A375e  PASSWORD:  LINKSTAUS:2  SignalDB:-62
BSSID:fc:8b:97:5c:df:0d SSID:Matthew  PASSWORD:  LINKSTAUS:2  SignalDB:-80
BSSID:cc:d5:39:e3:3c:01 SSID:YFVEGUEST  PASSWORD:  LINKSTAUS:2  SignalDB:-73
BSSID:3c:df:bd:dd:fd:d3 SSID:Alex3G  PASSWORD:  LINKSTAUS:2  SignalDB:-67
BSSID:b8:a3:86:87:fe:b6 SSID:D-Link_DIR-600A  PASSWORD:  LINKSTAUS:2  SignalDB:-82
BSSID:cc:d5:39:9e:b0:b0 SSID:YFVEGROUP  PASSWORD:  LINKSTAUS:2  SignalDB:-94
BSSID:fc:8b:97:5c:c6:03 SSID:dlink_xlv1  PASSWORD:  LINKSTAUS:2  SignalDB:-82
BSSID:cc:d5:39:9e:b0:b1 SSID:YFVEGUEST  PASSWORD:  LINKSTAUS:2  SignalDB:-94
UNSTABLE
  • 393
  • 1
  • 4
  • 13
  • 1
    You are not showing 'AP' - there is no way to answer this. –  May 04 '14 at 05:55
  • You also haven't shown where n and m are assigned. Are we supposed to throw guesses? – o_weisman May 04 '14 at 05:59
  • The culprit is most likely the copy constructor of `AP`. – R Sahu May 04 '14 at 06:04
  • @o_weisman m and n are assigned by lambda. am i right? – UNSTABLE May 04 '14 at 06:05
  • @RSahu why? I can sort by other field like SSID, it works. – UNSTABLE May 04 '14 at 06:06
  • @user2361301 `std::sort` swaps objects in order to sort them -- which involves copy assignment operation. Swapping objects will require copy assignment. Now that I think about it, I am not sure whether it requires copy construction also. – R Sahu May 04 '14 at 06:14
  • @RSahu thank you for your reply. Do mis-copy construct make the sort crash or just no effect?? – UNSTABLE May 04 '14 at 06:18
  • @user2361301 it depends on what the destructor does. If your class has any data that is allocated from the heap, you have to make sure that you implement the copy constructor, the assignment operator, and the destructor properly. Checkout [What is The Rule of Three?](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three). – R Sahu May 04 '14 at 06:22
  • What the hack is `AP &operator=(co SSID(""), ...)`? –  May 04 '14 at 06:24
  • @RSahu but AP did not allocate any in heap, just plain int or std::string and their setter/getter,I added AP def. The question is why stable_sort won't crash?? – UNSTABLE May 04 '14 at 06:26
  • @user2361301 `SignalDB` is not initialized in the default copy constructor. Not that it explains why `std::sort` crashes. – R Sahu May 04 '14 at 06:36
  • @RSahu How? I don't know how to initialize the SignalDB to make sense, but before sort, it 100% has a proper value. – UNSTABLE May 04 '14 at 06:38
  • @user2361301 I am out of ideas. Sorry. – R Sahu May 04 '14 at 06:40
  • @RSahu You are right Sauhu, I forgot SignalDB = rhs.SignalDB; in assignment operator, Now I add it and it does not crash and the sort work perfectly! Thank you for your help! (although I do not 100% understand why) – UNSTABLE May 04 '14 at 06:44
  • @user2361301 - 1) why did you believe you needed a user-defined copy constructor? If you didn't write any copy constructor, the sorting wouldn't have crashed. Instead you created a problem when there was no problem. 2) leaving out members that are to be copied creates fake copies. A copy constructor's only purpose is to make copies, and you failed to do that. Instead you created half-baked copies, and using half-baked copies during the running of the program can cause all sorts of issues. – PaulMcKenzie May 04 '14 at 06:52
  • @PaulMcKenzie I don't really understand why the copy constructor creates fake copies. Can you explain more? AP::AP(const AP &orig) :BSSID(orig.BSSID), SSID(orig.SSID), PASSWORD(orig.PASSWORD), LinkStatus(orig.LinkStatus), AuthType(orig.AuthType), SignalLevel(orig.SignalLevel), Remembered(orig.Remembered), SignalDB(orig.SignalDB){} – UNSTABLE May 04 '14 at 06:59
  • @user2361301 - My point is that *you don't need any of that code*. There was no need for you to interfere with a buggy copy constructor when the compiler-generated copy constructor was perfectly ok. The compiler-generated copy constructor doesn't forget to copy members. Why did you need to override it and instead, write a buggy version?? If you want proof, remove that code you're showing me. The sorting functions will work. – PaulMcKenzie May 04 '14 at 07:01
  • @PaulMcKenzie I totally accept your words. I will remove this I think copy constructor. But Do this cause the crash? Because the assignment operator is also buggy? So the sort use a buggy assignment operator so it crash? I forgot SignalDB = rhs.SignalDB; in assignment operator by the way. – UNSTABLE May 04 '14 at 07:06
  • @user2361301 Remove assignment operator and copy constructor completely. All of the member variables of AP are safely copyable, therefore the compiler-generated versions of the assignment operator and copy constructor are perfectly adequate. Again, the compiler-generated version does not forget to copy members. – PaulMcKenzie May 04 '14 at 07:09
  • @user2361301 `? So the sort use a buggy assignment operator so it crash?` If you have an assignment operator/copy constructor that makes fake copies, yes, your program is buggy. The reason why is that copying objects *must* work correctly. Not *may*, but *must*. You see that copying objects occurs in places where you didn't expect, which means that the copying operation *must* perform correctly (make *perfect* copies). – PaulMcKenzie May 04 '14 at 07:11
  • @PaulMcKenzie Thank you for your reply. But last and not important if you don't want answer, I still wonder why the stable_sort didn't crash. – UNSTABLE May 04 '14 at 07:12
  • @user2361301 So you're asking `"why when I do this wrong thing in C++, my program works for a and not for b?"`. You do realize that when you make these types of mistakes, the behavior of the program is undefined? – PaulMcKenzie May 04 '14 at 07:15

1 Answers1

0

From the comment it seems the problem was a missing assignment of SignalDB in the assignment operator. This missing assignment would easily explain why neither sorting algorithm would actually sort the values: there is some random value there which keeps changing for the values.

Incidentally it also explains why std::sort() crashes while std::merge_sort() doesn't although there is certainly no guarantee that std::merge_sort() won't crash: the sorting criteria has to be a Strict Weak Order and the values being sorted have to be copyable. If these constraints don't hold, the behavior of either algorithm is undefined. The copyable constraint states that the copy of a value can't be distinguished from the original and can be used entirely interchangeably. If the value being compared on isn't really copied that isn't is the case.

The difference in crashing vs. non-crashing is based on how the sorting is actually implemented. Note that neither sort is guaranteed to crash as the behavior is undefined in either case. However, std::stable_sort() uses an algorithm which is more likely to just produce wrong results than to crash. To minimize the operations done in an inner loop of std::sort() a sentinel is used at the beginning of the sequence: in a strategic fashion it is made sure that a small enough element ends up in the right location of the sequence. This way the inner loop only needs to compare the values rather than also verifying if the value is still in the range: due to the sentinel a search used in the inner loop it will never try to move off the sequence. However, if that smallest element gets a more or less random value being ordered on it may turn out not to be the smallest element at all and the "sentinel" isn't really one, having the search wander off into looking at fields it isn't meant to look at.

For a more detailed explanation you might want to watch the last two videos of Stepanov's lectures on Efficient Programming with Components (although the lectures are kind of extremely slow, I think there is actually value in watching all of them). I think the specific issue is discussed in the second to last video but I don't recall exactly. The discussion is focused on the ordering not being a strict weak order but the effect is the same if the copy isn't really a copy.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • I accept as answer. But it's too complicated. I prefer someone to tell me how std::sort use assignment operator. – UNSTABLE May 04 '14 at 08:34
  • @huskarwang: `std::sort()` uses `swap()` to exchange values. The standard implementation is essentially as if is like `void swap(T& a, T& b) { T tmp(a); a = b; b = tmp; }` (the real implementation also uses moves). – Dietmar Kühl May 04 '14 at 13:21