在插入集合 C++ 之前比较字符串

Question

我试图通过比较字符串的长度来比较字符串，然后再插入到我的集合中。应首先插入最短的字符串。不知道怎么回事，但有些台词不在片场。

我的代码：

#include <iostream>
#include <string>
#include <set>

struct compare {
    bool operator() (const string& a, const string& b) const{
        return a.size() < b.size();
    }
};

template<typename T>
void print(const T& t){
    for(auto& it : t)
        cout << it << endl;
}

int main() {    
    string word;
    set<string, compare> c;

    while(cin >> word)
        c.insert(word);

    print(c);

    return 0;
}

这里是要插入的测试词

Apple
Apricots
Avocado
Durian
Fig
Tangerine/Clementine
Kumquat
Lemon
Pear
Prunes
Raspberries
Strawberries
Watermelon

这是输出

Fig
Pear
Apple
Durian
Avocado
Apricots
Watermelon
Raspberries
Strawberries
Tangerine/Clementine

按预期工作，但显然缺少一些单词喜欢：

Kumquat
Lemon
Prunes

Answer 1

您是否注意到集合中的所有条目都有不同的长度？

那是因为 compare 函数决定是否认为某物与集合中已有的东西重复：

Two elements of a set are considered equivalent if key_comp returns false reflexively (i.e., no matter the order in which the elements are passed as arguments).

因为，对于相同长度的两个单词，key_comp(word1, word2) 和 key_comp(word2, word1) return 都为假，这两个单词被认为是相同的，因此不会将第二个单词插入到集合中。

您可以通过稍微修改您的函数来解决此问题：

bool operator() (const string& a, const string& b) const {
    if (a.size() == b.size()) return a < b;
    return a.size() < b.size();
}

执行基于内容的比较（而不是基于长度的比较），其中两个项目的长度相同。

Answer 2

集不允许重复元素。如果集合的比较函数是 less，那么集合使用 !less(a, b) && !less(b, a) 来确定两个元素是否相同（因此重复）。

默认情况下，集合使用的比较函数是 < 运算符。所以当你这样做时：

set::set<int> s;
int x = 42, y = 42;
s.insert(x);
s.insert(y);

只插入一个元素的原因是因为x < y为false并且y < x也为false，所以集合确定x == y并忽略第二个插入。

但是通过你定义的比较函数，所有相同长度的字符串都被认为是相同的。一旦集合中存在长度为 N 的字符串，以后您尝试插入的所有长度为 N 的字符串都不会被插入（因为集合认为它们已经存在）。

std::set<string, compare> s;
s.insert("abc");
s.insert("def");

less("abc", "def") 为假且 less("def", "abc") 为假，因此集合将 "abc" 和 "def" 解释为相同。

您可以使用打破平局的 less 函数解决此问题，例如：

bool operator() (const string& a, const string& b) const{
    if (a.size() == b.size()) {
      return a < b;
    }
    return a.size() < b.size();
}

这将首先按大小对字符串进行排序，但通过按字典顺序排序来打破平局。现在两个字符串不会被认为是相等的，除非它们实际上相同。

Answer 3

一个std::set can not contain duplicates. In this case it can't have two strings the same length. Perhaps you would do better using a std::multiset?

#include <iostream>
#include <string>
#include <set>

struct compare {
    bool operator() (const std::string& a, const std::string& b) const{
        return a.size() < b.size();
    }
};

template<typename T>
void print(const T& t){
    for(auto& it : t)
        std::cout << it << std::endl;
}

int main() {
    std::string word;
    std::multiset<std::string, compare> c; // multiset!!!

    while(std::cin >> word)
        c.insert(word);

    print(c);

    return 0;
}

输出：

Fig
Pear
Apple
Lemon
Durian
Prunes
Avocado
Kumquat
Apricots
Watermelon
Raspberries
Strawberries
Tangerine/Clementine

注意：此解决方案允许重复的字符串长度，以便可以按长度对字符串进行排序。但这意味着它也允许重复的字符串值，以便同一个字符串可以出现多次。

Answer 4

解决这个问题的第一步应该是简化，在这种情况下，删除作为潜在原因的输入。这样做表明问题不是由数据源引起的。因此，让我们看看是否存储了这些值：

#include <iostream>
#include <string>
#include <set>

struct compare {
    bool operator() (const std::string& a, const std::string& b) const{
        return a.size() < b.size();
    }
};

template<typename T>
void print(const T& t){
    for(auto& it : t)
        std::cout << it << "\n";
}

template<typename T>
void insert(T& t, const char* value)
{
    t.insert(value);
    std::cout << "After inserting " << value << "\n";
    print(t);
    std::cout << "\n";
}

int main() {    
    std::set<std::string, compare> c;

    insert(c, "Apple");
    insert(c, "Apricots");
    insert(c, "Avocado");
    insert(c, "Durian");
    insert(c, "Fig");
    insert(c, "Tangerine/Clementine");
    insert(c, "Kumquat");
    insert(c, "Lemon");
    insert(c, "Pear");
    insert(c, "Prunes");
    insert(c, "Raspberries");
    insert(c, "Strawberries");
    insert(c, "Watermelon");

    print(c);

    return 0;
}

这些值没有被存储，但我们似乎可以解决这个问题：

    insert(c, "Apple");
    insert(c, "Lemon");

http://ideone.com/aGZOIN

std::set::insert returns 一些可能有用的信息：http://www.cplusplus.com/reference/set/set/insert/

    auto result = t.insert(value);

我们对 result.second 很感兴趣。插入成功为真 (1)，插入失败为假 (0)。

http://ideone.com/wP4CaG

After inserting Apple. inserted? 1
Apple

After inserting Lemon. inserted? 0
Apple

您的比较运算符导致集合认为这两个值相等。 std::set 通过两次使用 < 运算符来确定等价性：

if (!cmp(a, b))
    if (!cmp(b, a))
        // equal;

您可能想使用：

struct compare {
    bool operator() (const string& a, const string& b) const{
        if (a.size() < b.size())
            return true;
        if (a.size() == b.size() && a.compare(b) < 0)
            return true;
        return false;
    }
};

完整代码：

#include <iostream>
#include <string>
#include <set>

struct compare {
    bool operator() (const std::string& a, const std::string& b) const{
        if (a.size() < b.size())
            return true;
        if (a.size() == b.size() && a.compare(b) < 0)
            return true;
        return false;
    }
};

template<typename T>
void print(const T& t){
    for(auto& it : t)
        std::cout << it << "\n";
}

template<typename T>
void insert(T& t, const char* value)
{
    auto result = t.insert(value);
    std::cout << "After inserting " << value << ". inserted? " << result.second << "\n";
    print(t);
    std::cout << "\n";
}

int main() {    
    std::set<std::string, compare> c;

    insert(c, "Apple");
    insert(c, "Lemon");
    insert(c, "Fig");
    insert(c, "Kumquat");

    print(c);

    return 0;
}

http://ideone.com/Vs5p0i

输出：

After inserting Apple. inserted? 1
Apple

After inserting Lemon. inserted? 1
Apple
Lemon

After inserting Fig. inserted? 1
Fig
Apple
Lemon

After inserting Kumquat. inserted? 1
Fig
Apple
Lemon
Kumquat

Answer 5

如果你不是特别关心最高效的方案，只关心插入的顺序。这是一个简单的解决方案：排序然后插入。

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

std::set<std::string> InsertByLength(std::vector<std::string> src)
{
  std::sort(src.begin(), src.end(), [](const std::string& a, const std::string& b)
            {
            return a.size() < b.size();
            });

  std::set<std::string> ret;
  for(auto s : src) {
    std::cout << s << std::endl;
    ret.insert(s);
  }

  return ret;
}

int main()
{
  auto result = InsertByLength({
    "Apple", "Apricots", "Avocado", "Durian", "Fig", "Tangerine/Clementine",
    "Kumquat", "Lemon", "Pear", "Prunes"  "Raspberries", "Strawberries",
    "Watermelon"});

  std::cout << "Inserted: " << result.size() << " elements\n";

  return 0;
}

http://ideone.com/d1T0ew

在插入集合 C++ 之前比较字符串

compare string before inserting into set c++

c++

set