[C++知识库]HJ14 字符串排序

HJ14 字符串排序

#include <iostream>
#include <vector>
#include <algorithm>

static bool strlt(std::string a, std::string b) {
    int delta = 0;
    for (size_t i = 0; i <a.size() && i<b.size(); i++) {
        delta = a.at(i) - b.at(i);
        if (delta != 0) {
            return delta < 0;
        }
    }
    return a.size() < b.size();
}

int main(int argc, const char *argv[]) {
    std::vector<std::string> words;
    std::string w;
    int n = 0;
    
    std::cin >> n;
    
    while (n-- > 0) {
        std::cin >> w;
        words.push_back(w);
    } 
    std::sort(words.begin(), words.end(), strlt);
    
    for (std::vector<std::string>::const_iterator it = words.begin(); 
         it != words.end(); ++it) {
        std::cout <<*it << std::endl;
    }
}

std::sort用法?

std::sort(words.begin(), words.end(), strlt);

前个参数表示容器迭代器开始，迭代器结束，

最后1个参数传比较大小的方法

表示小于，返回bool (从小到大排序, 返回true则排前面)，不是比较大小返回int 0,>0, <0

bool (*cmp)(*迭代器的类型， *迭代器类型)

对于std::vector<std::string>, 迭代器it数据类型为 std::string *, 那么*it类型就是std::string

D:\Programs\mingw64\lib\gcc\x86_64-w64-mingw32\8.1.0\include\c++\bits\stl_algo.h

 /**
   *  @brief Sort the elements of a sequence using a predicate for comparison.
   *  @ingroup sorting_algorithms
   *  @param  __first   An iterator.
   *  @param  __last    Another iterator.
   *  @param  __comp    A comparison functor.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [__first,__last) in ascending order,
   *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
   *  range @p [__first,__last-1).
   *
   *  The relative ordering of equivalent elements is not preserved, use
   *  @p stable_sort() if this is needed.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
	 _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
	    typename iterator_traits<_RandomAccessIterator>::value_type,
	    typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }

D:\Programs\mingw64\lib\gcc\x86_64-w64-mingw32\8.1.0\include\c++\bits\predefined_ops.h

  template<typename _Compare>
    _GLIBCXX14_CONSTEXPR
    inline _Iter_comp_iter<_Compare>
    __iter_comp_iter(_Compare __comp)
    { return _Iter_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)); }

  template<typename _Compare>
    struct _Iter_comp_iter
    {
      _Compare _M_comp;

      explicit _GLIBCXX14_CONSTEXPR
      _Iter_comp_iter(_Compare __comp)
	: _M_comp(_GLIBCXX_MOVE(__comp))
      { }

      template<typename _Iterator1, typename _Iterator2>
        _GLIBCXX14_CONSTEXPR
        bool
        operator()(_Iterator1 __it1, _Iterator2 __it2)
        { return bool(_M_comp(*__it1, *__it2)); }
    };

测试用例自测，改下面的代码，避免手动输入

#include <fstream>
#define DEBUG

// ...

#ifndef DEBUG
    std::cin >> n;
    while (n-- > 0) {
        std::cin >> w;
        words.push_back(w);
    }
#else
    std::ifstream ifs;
    ifs.open("../input2.txt", std::ios_base::in);
    if (!ifs.is_open()) {
        std::cout << "打开../input2.txt失败";
        return -2;
    }
    ifs >> n;
    while (n-- >0) {
        ifs >>w;
        words.push_back(w);
    }
    ifs.close();
#endif

input2.txt

54
MGDa
aha
BDTmfV
ShOBHM
QqFdcsFk
WeSj
YDyBY
RldCiGFB
h
gLmLEXW
pWOJywCx
eFcUlSfaH
krFjsPC
Vv
viYTX
bhkHwulzFC
Ya
R
EEhgyd
zM
IHp
pSDmVZ
oAeSLWTtd
bZO
F
kD
TqPZ
hI
ITwU
BMpsBRkQ
ZQhOGB
LCvYTEqHqA
flp
Bcc
VDEtYbz
uprsKe
zJYEEPiVkL
KYUwgtJfL
vVZp
AmnaxgeA
QwDXJQOxNU
thkhsKEMBr
zM
DxnWRwnfh
PDYaSCbwmR
n
kG
KfDD
tLpaLPqBaj
oXBLTJGo
pnEwvEHhic
WzMfONKYG
CiFcccEh
vfKRxZbLhq

输出:

D:\Users\mzh\CLionProjects\HJ14\cmake-build-debug\HJ14.exe
AmnaxgeA
BDTmfV
BMpsBRkQ
Bcc
CiFcccEh
DxnWRwnfh
EEhgyd
F
IHp
ITwU
KYUwgtJfL
KfDD
LCvYTEqHqA
MGDa
PDYaSCbwmR
QqFdcsFk
QwDXJQOxNU
R
RldCiGFB
ShOBHM
TqPZ
VDEtYbz
Vv
WeSj
WzMfONKYG
YDyBY
Ya
ZQhOGB
aha
bZO
bhkHwulzFC
eFcUlSfaH
flp
gLmLEXW
h
hI
kD
kG
krFjsPC
n
oAeSLWTtd
oXBLTJGo
pSDmVZ
pWOJywCx
pnEwvEHhic
tLpaLPqBaj
thkhsKEMBr
uprsKe
vVZp
vfKRxZbLhq
viYTX
zJYEEPiVkL
zM
zM

Process finished with exit code 0
?

不需要自己写排序, 直接调用系统函数std::sort