Skip to main content
added 10 characters in body; added 51 characters in body
Source Link
Deduplicator
  • 19.3k
  • 1
  • 31
  • 65
  1. Take advantage of views, specifically C++17 std::string_view, to avoid needless allocations.

  2. Take advantage of the standard algorithms. They help writing clear, concise and fast code.

  3. Text is hard. So, do you really want uppercase ASCII letters, all narrowsingle-byte (nonthus non-unicode) uppercase letters the current locale supports, or full unicode support? I will ignore the last option.

  4. Minimize the accessible context, and decouple as you can. extractVariables() can be a free function. Actually, extract a function for listing runs of any kind.

  5. auto is very useful to avoid error-prone repetition.

Applying that:

template <class T, class F>
auto listRuns(T s, F f) {
    std::vector<T> r;
    auto first = begin(s);
    while ((first = std::find_if(first, end(s), f) != end(s)) {
        auto last = std::find_if_not(first, end(s), f);
        r.emplace(first, last - first);
        first = last;
    }
    std::sort(begin(r), end(r));
    r.resize(end(r) - std::unique(begin(r), end(r)));
    return r;
}

auto extractVariables(std::string_view s) {
    return listRuns(s, [](unsigned char c){ return std::is_upper(c); });
    // Keep in mind the defined domain of std::is_upper()

    return listRuns(s, [](char c){ return c >= 'A' && c <= 'Z';});
    // Assumes ASCII and asks for uppercase letters
}

Something to ponder:

It might seem (or rarely actually be) advantageous to first insert into a std::set or std::unordered_set to filter out duplicates.
ButUnfortunately the added complexity and reduced locality of reference will almost always destroy any possiblepotential advantage, unless it leads to a very significant saving of memory. Keep in mind the overhead associated with every singleEvery single dynamic allocation has (sometimes significant) overhead though.
So if you want to try it, measure.

  1. Take advantage of views, specifically C++17 std::string_view, to avoid needless allocations.

  2. Take advantage of the standard algorithms. They help writing clear, concise and fast code.

  3. Text is hard. So, do you really want uppercase ASCII letters, all narrow (non-unicode) uppercase letters the current locale supports, or full unicode support? I will ignore the last option.

  4. Minimize the accessible context, and decouple as you can. extractVariables() can be a free function. Actually, extract a function for listing runs of any kind.

  5. auto is very useful to avoid error-prone repetition.

Applying that:

template <class T, class F>
auto listRuns(T s, F f) {
    std::vector<T> r;
    auto first = begin(s);
    while ((first = std::find_if(first, end(s), f) != end(s)) {
        auto last = std::find_if_not(first, end(s), f);
        r.emplace(first, last - first);
        first = last;
    }
    std::sort(begin(r), end(r));
    r.resize(end(r) - std::unique(begin(r), end(r)));
    return r;
}

auto extractVariables(std::string_view s) {
    return listRuns(s, [](unsigned char c){ return std::is_upper(c); });
    // Keep in mind the defined domain of std::is_upper()

    return listRuns(s, [](char c){ return c >= 'A' && c <= 'Z';});
    // Assumes ASCII and asks for uppercase letters
}

Something to ponder:

It might seem (or rarely be) advantageous to first insert into a std::set or std::unordered_set to filter out duplicates.
But the added complexity and reduced locality of reference will almost always destroy any possible advantage, unless it leads to a very significant saving of memory. Keep in mind the overhead associated with every single dynamic allocation though.

  1. Take advantage of views, specifically C++17 std::string_view, to avoid needless allocations.

  2. Take advantage of the standard algorithms. They help writing clear, concise and fast code.

  3. Text is hard. So, do you really want uppercase ASCII letters, all single-byte (thus non-unicode) uppercase letters the current locale supports, or full unicode support? I will ignore the last option.

  4. Minimize the accessible context, and decouple as you can. extractVariables() can be a free function. Actually, extract a function for listing runs of any kind.

  5. auto is very useful to avoid error-prone repetition.

Applying that:

template <class T, class F>
auto listRuns(T s, F f) {
    std::vector<T> r;
    auto first = begin(s);
    while ((first = std::find_if(first, end(s), f) != end(s)) {
        auto last = std::find_if_not(first, end(s), f);
        r.emplace(first, last - first);
        first = last;
    }
    std::sort(begin(r), end(r));
    r.resize(end(r) - std::unique(begin(r), end(r)));
    return r;
}

auto extractVariables(std::string_view s) {
    return listRuns(s, [](unsigned char c){ return std::is_upper(c); });
    // Keep in mind the defined domain of std::is_upper()

    return listRuns(s, [](char c){ return c >= 'A' && c <= 'Z';});
    // Assumes ASCII and asks for uppercase letters
}

Something to ponder:

It might seem (or rarely actually be) advantageous to first insert into a std::set or std::unordered_set to filter out duplicates.
Unfortunately the added complexity and reduced locality of reference will almost always destroy any potential advantage, unless it leads to a very significant saving of memory. Every single dynamic allocation has (sometimes significant) overhead though.
So if you want to try it, measure.

Source Link
Deduplicator
  • 19.3k
  • 1
  • 31
  • 65

  1. Take advantage of views, specifically C++17 std::string_view, to avoid needless allocations.

  2. Take advantage of the standard algorithms. They help writing clear, concise and fast code.

  3. Text is hard. So, do you really want uppercase ASCII letters, all narrow (non-unicode) uppercase letters the current locale supports, or full unicode support? I will ignore the last option.

  4. Minimize the accessible context, and decouple as you can. extractVariables() can be a free function. Actually, extract a function for listing runs of any kind.

  5. auto is very useful to avoid error-prone repetition.

Applying that:

template <class T, class F>
auto listRuns(T s, F f) {
    std::vector<T> r;
    auto first = begin(s);
    while ((first = std::find_if(first, end(s), f) != end(s)) {
        auto last = std::find_if_not(first, end(s), f);
        r.emplace(first, last - first);
        first = last;
    }
    std::sort(begin(r), end(r));
    r.resize(end(r) - std::unique(begin(r), end(r)));
    return r;
}

auto extractVariables(std::string_view s) {
    return listRuns(s, [](unsigned char c){ return std::is_upper(c); });
    // Keep in mind the defined domain of std::is_upper()

    return listRuns(s, [](char c){ return c >= 'A' && c <= 'Z';});
    // Assumes ASCII and asks for uppercase letters
}

Something to ponder:

It might seem (or rarely be) advantageous to first insert into a std::set or std::unordered_set to filter out duplicates.
But the added complexity and reduced locality of reference will almost always destroy any possible advantage, unless it leads to a very significant saving of memory. Keep in mind the overhead associated with every single dynamic allocation though.