如何构建一个 std::vector<std::string> 并对其进行排序？

Question

我有一堆需要排序的字符串。我想使用 std::vector 是最简单的方法。但是，我以前从未使用过 vector，因此需要一些帮助。

我只需要按字母数字顺序排序，没有什么特别的。string::compare 函数会起作用。

之后，我该如何迭代它们以验证它们已经排序？

这是我目前所拥有的：

std::sort(data.begin(), data.end(), std::string::compare);

for(std::vector<std::string>::iterator i = data.begin(); i != data.end(); ++i)
{
    printf("%s\n", i.c_str);
}

- samoz

---

请查看此答案：boost::sort - Denys Yurchenko

Answer 1

你可以直接这样做

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

使用该方法可以对字符串进行排序。然后遍历这些字符串，检查它们是否按照顺序排列。

if(names.empty())
    return true; // empty vector sorted correctly
for(std::vector<std::string>::iterator i=names.begin(), j=i+1; 
        j != names.end(); 
        ++i, ++j)
    if(*i > *j)
        return false;
return true; // sort verified

特别是，std::string::compare不能作为比较器使用，因为它不能执行sort想要的操作：如果第一个参数小于第二个参数，则返回true，否则返回false。 如果像上面那样使用sort，它将只使用operator<，这将确切地执行该操作（即std::string使其返回first.compare(second) < 0）。

- litb

---

仅供娱乐（未经测试）：检查向量是否已排序可以简化为std::adjacent_find(names.begin(), names.end(), std::greaterstd::string()) == names.end()。 - Éric Malenfant

Answer 2

这个问题是什么？好像一切都已经在那里了。

然而，你应该使用std::cout << *i << std::endl; i是指向容器中数据的迭代器==指针，所以需要用* c_str()是std::string的函数而不是变量

你代码中的问题与你的问题无关？

给你一些提示： std::vector也重载了[]运算符，因此你可以避免迭代器的麻烦，像数组一样使用它（从0到vector.size()迭代）。

你可以使用std::set，它在插入时自动排序（二叉树），因此可以避免额外的排序。

使用一个函数对象使你的输出更有趣：copy(V.begin(), V.end(), ostream_iterator<std::string>(cout, "\n"));

- ypnos

Answer 3

用于排序的方法：
使用std::sort或std::vector< std::string>::sort(..)方法进行排序。
检查是否已排序：
使用std::is_sorted检查是否已排序 - http://www.sgi.com/tech/stl/is_sorted.html
或者
std::adjacent_find( v.begin(), v.end(), std::greater< std::string >() ) == v.end()

对于您的情况，您可以使用默认比较器。

编辑:
std::is_sorted不是标准STL函数，它在SGI STL实现中定义。
感谢@Brian Neal提供此注释。

- bb

---

你不应该依赖sgi网站上关于STL的信息，因为它早于标准。is_sorted不是标准。 - Brian Neal

请纠正我，如果我错了：is_sorted 函数在 C++11 中被添加。http://en.cppreference.com/w/cpp/algorithm/is_sorted - abe312

Answer 4

litb是正确的，像往常一样。

我只想指出更普遍的观点 - 任何可以与<进行比较的内容都可以使用std::sort进行排序。 我有时会将operator<成员函数伪装成一个结构体，这样就可以做到这一点。

- Mark Ransom

Answer 5

对字符串进行排序：

using namespace std; // to avoid using std everywhere 
std::sort(data.begin(), data.end()); // this will sort the strings

检查向量是否已排序：

if(vec.empty())
    return true; // empty vector is sorted correctly
for(std::vector< std::string>::iterator i=vec.begin(), j=i+1; j != vec.end(); ++i, ++j)
    if(*i > *j)  return false;
return true; // sort verified

C++11检查已排序向量的方法： std::is_sorted(vec.begin(),vec.end())

现在打印已排序向量：

   for(std::vector< std::string>::iterator i = vec.begin(); i != vec.end(); ++i)
{
    std::cout<< *i <<std::endl;
}

- abe312

---

我已经在CodeBlocks和Ideone上检查过了，这个代码可以正常工作。 - abe312

自从 C++11 版本以来，检查向量是否已排序就是这么简单：std::is_sorted(vec.begin(), vec.end())。 - Éric Malenfant

你不应该依赖那个sgi网站上的STL信息，因为它早于标准。is_sorted不是标准。 - abe312

is_sorted不是标准的。 - abe312

据我所知，is_sorted是在C++11中添加的。 - Éric Malenfant

Answer 6

你可以使用 std::set，它是一个自然排序的容器。

- Joe

---

限制：std::set不支持像std::vector那样的随机访问。 - Joel

std::set不接受重复元素。 - undefined

Answer 7

尝试使用比较器：

 #include <cmath>
 #include <cstdio>
 #include <vector>
 #include <iostream>
 #include <algorithm>
 using namespace std;

//comparing function only sorts if string size is equal and keeps the larger integgers at last.
bool myfunction (string i,string j) 
{ 
int n=i.length();
int m=j.length();
if(n==m)
    return (i<j);

return n<m;   
  }


int main() {
int n;
cin>>n;
vector <string> arr(n);
for(int i=0;i<n;i++)
    cin>>arr[i];


sort(arr.begin(),arr.end(),myfunction);

for(int i=0;i<n;i++)
    cout<<arr[i]<<endl;

return 0;
 }

- Ashish Kapil