3
\$\begingroup\$

Background

I wrote a function update_list_v2(). And this function "maintains" a sorted list, g_list. g_list is declared globally like below.

static vector<element> g_list;

update_list_v2() do below works.

1) remove every element of g_list, if the element exists in v

2) add a element to g_list, if a element exists in v and does not exist in g_list.

3) if a element exists in v and in g_list and max_bmi of the element increases, print information of the element. (you can think the element is a person)

v is a list for recent data and update_list_v2() have to update g_list.

And I wrote some other functions to work update_list_v2().

Questions

I am not that familiar to c++ and vector. I wonder how to improve update_list_v2() and rest of my code.

Code

Here is code of update_list_v2()

int update_list_v2(vector<element> &v) {
  vector<element> new_items;
  if (g_list.size() == 0) {
    sort(v.begin(), v.end(), element::is_lower_id);
    g_list = v;
    for (int i=0; i<g_list.size(); i++) {
        g_list[i].update_bmi(v[i]);
    }
    return 0;
  }
  // initialize 'remove'
  for (int i=0; i<g_list.size(); i++) {
    g_list[i].remove = true;
  }
  for (int i=0; i<v.size(); i++) {
    int f = find_element(v[i]);
    if (f>=0) {
        g_list[f].remove = false;
        if (v[i].bmi > g_list[f].max_bmi) {
            printf("max_bmi will be increased!\n");
            printf("old data:");
            g_list[f].print();
            g_list[f].update_bmi(v[i]);
            printf("new data:");
            g_list[f].print();
        } else {
            g_list[f].update_bmi(v[i]);
        }
    } else {
        new_items.push_back(v[i]);
    }
  }
  // remove every element which 'remove' is true.
  for (vector<element>::iterator it = g_list.begin(); it != g_list.end(); ++it) {
    while (it != g_list.end()){
        if (it->remove) {
            g_list.erase(it);
        } else {
            break;
        }
    }
  }
  // now, merge new_items to g_list
  for (int i=0; i<new_items.size(); i++) {
    g_list.push_back(new_items[i]);
    new_items[i].update_bmi(new_items[i]);
  }
  // finally, sort g_list
  sort(g_list.begin(), g_list.end(), element::is_lower_id);

}

And this is rest of my source code.

#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>

using namespace std;

class element {
public:
  long long id;
  string name;
  int bmi; // body mass index
  int max_bmi;
  bool remove;
  static bool is_lower_id(element a, element b) {
    return a.id < b.id;
  }
  static bool is_same(element a, element b) {
    return (a.id == b.id) &&
            (0 == a.name.compare(b.name));
  }
  void update_bmi(element &a) {
    this->bmi = a.bmi;
    this->max_bmi = max(this->max_bmi, a.bmi);
  }
  void print() {
    printf("id/name bmi(max) : %lld/%s %d(%d)\n",
        this->id, this->name.c_str(), this->bmi, this->max_bmi);
  }
};

int find_element(element &e) {
  // find an element using binary search algorithm.
  int l = 0;
  int r = g_list.size() - 1;
  int m;
  while (l<=r) {
    m = l + (r-l) / 2;
    if (element::is_same(g_list[m], e)){
        return m;
    }
    if (element::is_lower_id(g_list[m], e))
        l = m + 1;
    else
        r = m - 1;
  }
  return -1;
}

int print_list(vector<element> &v) {
  printf("%s:%d\n",__func__,__LINE__);
  for(int i=0; i<v.size(); i++){
    v[i].print();
  }
}

int main(int argc, const char *argv[])
{
  int a_id[] = {12, 11, 13, 5, 6, 7};
  const char * a_name[] = {"a", "b", "c", "d", "e", "f"};
  int a_bmi[] = {12, 11, 13, 5, 6, 7};
  int b_id[] = {12, 1, 13, 5, 6, 99};
  const char * b_name[] = {"a", "x", "c", "d", "e", "y"};
  int b_bmi[] = {20, 5, 5, 10, 6, 5};
  vector<element> a, b;
  for(int i=0; i<6; i++){
    element x;
    x.id = a_id[i];
    x.name = string(a_name[i]);
    x.bmi = a_bmi[i];
    a.push_back(x);
  }
  update_list_v2(a);
  print_list(g_list);
  for(int i=0; i<6; i++){
    element x;
    x.id = b_id[i];
    x.name = string(b_name[i]);
    x.bmi = b_bmi[i];
    b.push_back(x);
  }
  update_list_v2(b);
  print_list(g_list);

  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ What's "do something"? An unfinished code or some removed stuff for the purpose of this example? Code Review is about improving existing, working code. Here, it already are many improvement possible on your code, but try to give a full working code example. If moderators think you're not off-topic, i'll be happy to help you improving your code and logic, but i'm afraid you are. \$\endgroup\$ – Calak Nov 8 '18 at 8:20
  • \$\begingroup\$ @Calak I don't know C++ so it'd be a great help if you could point to the code that is missing or not implemented. \$\endgroup\$ – Peilonrayz Nov 8 '18 at 9:21
  • \$\begingroup\$ You need to provide a minimal working example. I couldn't compile your code. It seems that g_list is some global variable that isn't mentioned in the code bits you've presented so far. \$\endgroup\$ – papagaga Nov 8 '18 at 9:27
  • 7
    \$\begingroup\$ @papagag, a minimal working example is a Stack Overflow thing - what we need on CR is real code, preferably complete (but certainly with sufficient context that we know the types of all variables, and the intended purpose). \$\endgroup\$ – Toby Speight Nov 8 '18 at 10:40
  • \$\begingroup\$ I updated my question to clarify "do something". \$\endgroup\$ – H. Jang Nov 10 '18 at 1:56
2
\$\begingroup\$

There are a number of things that could be improved in this code. I hope you find these suggestions helpful.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Eliminate global variables where practical

Having routines dependent on global variables makes it that much more difficult to understand the logic and introduces many opportunities for error. Eliminating global variables where practical is always a good idea, so I would strongly suggest passing g_list as a parameter to functions that need it rather than having it as a global variable.

Always return an appropriate value

Your print_list() and update_list_v2() routines have control paths that cause them to end without returning any int value. This is an error and should be fixed.

Don't write this-> in member function

The use of this-> in member functions just clutters the code and adds nothing of value. Instead, simply omit it for clarity. Thus this:

void update_bmi(element &a) {
    this->bmi = a.bmi;
    this->max_bmi = max(this->max_bmi, a.bmi);
}

could be written as this:

void update_bmi(element &a) {
    bmi = a.bmi;
    max_bmi = max(max_bmi, a.bmi);
}

However, I wouldn't actually write it that way for several reasons which are enumerated in the next few points.

Use const where practical

A number of places in the code should have the const keyword added. For example instead of this:

void update_bmi(element &a) {

I would write it this way:

void update_bmi(const element &a) {

Pass by const reference where practical

The arguments to is_lower_id and is_same are declared as element but that causes the entire object to be duplicated. Better would be to make it const element & because it is not modified and it doesn't need to be duplicated.

Prefer stream I/O to printf

The printf function was a capable workhorse for many years, but the C++ iostream library is better in a number of regards. Although it's often more typing for the programmer initially, it's better because it has better type checking, less possibility for runtime overhead, and it fits well with the rest of C++. So I would probably change your element::print to this:

friend std::ostream &operator<<(std::ostream &out, const element &el) {
    return out << "id/name bmi(max) : " << el.id << '/' << el.name
               << ' ' << el.bmi << '(' << el.max_bmi << ")\n";
}

Now instead of writing this:

v[i].print();

We can write this:

std::cout << v[i];

Use aggregate initialization where appropriate

Within main the a vector is currently initialized like this:

int a_id[] = {12, 11, 13, 5, 6, 7};
const char * a_name[] = {"a", "b", "c", "d", "e", "f"};
int a_bmi[] = {12, 11, 13, 5, 6, 7};
vector<element> a;
for(int i=0; i<6; i++){
    element x;
    x.id = a_id[i];
    x.name = string(a_name[i]);
    x.bmi = a_bmi[i];
    a.push_back(x);
}

A similar thing is done with b. A much simpler way to do that is supported in C++:

std::vector<element> a {
    { 12, "a", 12 },
    { 11, "b", 11 },
    { 13, "c", 13 },
    { 5, "d", 5 },
    { 6, "e", 6 },
    { 7, "f", 7 },
};

This is called aggregate initialization and makes this much neater and easier to understand and maintain. Note that to do this, I reordered the data members is element so that id, name and bmi are the first three members.

Use standard operators

The code currently contains this function:

static bool is_lower_id(element a, element b) {
    return a.id < b.id;
}

I would instead use the standard operator for this:

bool operator<(const element &b) const {
    return id < b.id;
}

Now instead of writing this:

if (element::is_lower_id(g_list[m], e))

you can write it like this:

if (g_list[m] < e)

Also this:

sort(v.begin(), v.end(), element::is_lower_id);

becomes this:

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

because std::sort uses operator< by default. Similarly, to replace is_same we can use this:

bool operator==(const element &b) const {
    return id == b.id && name == b.name;
}

Fix the bug

The current code uses the value of max_bmi before it is assigned any value, which is a bug. This should be fixed.

Prefer standard algorithms

I would drop the print() function and, now that there is an operator<< function (as suggested above), you can simply write this:

std::copy(g_list.begin(), g_list.end(), 
        std::ostream_iterator<element>{std::cout});

Eliminate processing variables from structures

The remove flag in element is just a by-product of the processing and isn't really a part of the node itself. I'd recommend removing it and using better algorithms instead, as shown later in this answer.

Keep private things private

It's usually good to keep data members private if they are expected to have an invariant, that is, a condition that must always be true. In the case of this program, the max_bmi is expected to be set properly. For that reason, I'd make all of the data members private and provide access mechanisms as needed.

Simplify your algorithm

The way the rules are constructed, the result after update_list_v2() is that the resulting g_list will have exactly the elements that v had, with any updates to max_bmi applied. Further, we can reduce the complexity of the algorithm by noting that if the two input lists are sorted, we can make a single pass through both rather than searching exhaustively for every element.

Results

Here's a version of the code that applies all of these ideas. Note that because the class is really a class now with private data members, we need to use initializer_lists to provide the initialization that had been done with aggregate initialization.

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <initializer_list>

class element {
    long long id;
    std::string name;
    int bmi; // body mass index
    int max_bmi = 0;
public:
    element(long long id, std::string name, int bmi) :
        id{id}, name{name}, bmi{bmi} 
    {}
    void update_max_bmi() { max_bmi = bmi; }
    void update_max_bmi(const element &b) { max_bmi = std::max(bmi, b.bmi); }
    bool is_smaller_bmi_than(const element &b) const {
        return bmi < b.bmi;
    }
    bool operator<(const element &b) const {
      return id < b.id;
    }
    bool operator==(const element &b) const {
        return id == b.id && name == b.name;
    }
    friend std::ostream &operator<<(std::ostream &out, const element &el) {
      return out << "id/name bmi(max) : " << el.id << '/' << el.name
            << ' ' << el.bmi << '(' << el.max_bmi << ")\n";
    }
};


void update_list_v2(std::vector<element> v, std::vector<element> &g_list) {
    std::sort(v.begin(), v.end());
    if (g_list.empty()) {
        std::for_each(v.begin(), v.end(), [](element &e){ e.update_max_bmi(); });
    } else {
        auto curr{g_list.begin()};
        for (auto &elem : v) {
            while (curr != g_list.end() && *curr < elem) {
                ++curr;
            }
            if (curr != g_list.end()) { 
                if (*curr == elem) {
                    curr->update_max_bmi();
                    elem.update_max_bmi();
                    if (curr->is_smaller_bmi_than(elem)) {
                        std::cout << "max_bmi will be increased!\n"
                            "old data:" << *curr << "new data:"
                            << elem;
                    }
                    elem.update_max_bmi(*curr);
                }
            } 
        }
    }
    std::swap(v, g_list);
}


int main(int argc, const char *argv[])
{
    std::vector<element> a {
        { 12, "a", 12 },
        { 11, "b", 11 },
        { 13, "c", 13 },
        { 5, "d", 5 },
        { 6, "e", 6 },
        { 7, "f", 7 },
    };
    std::vector<element> g_list;
    update_list_v2(a, g_list);
    std::copy(g_list.begin(), g_list.end(), std::ostream_iterator<element>{std::cout});
    std::vector<element> b {
        { 12, "a", 20 },
        { 1, "x", 5 },
        { 13, "c", 5 },
        { 5, "d", 10 },
        { 6, "e", 6 },
        { 99, "y", 5 },
    };
    update_list_v2(b, g_list);
    std::copy(g_list.begin(), g_list.end(), std::ostream_iterator<element>{std::cout});
}
\$\endgroup\$
2
\$\begingroup\$

Don't use using namespace std;

It's bad practice that can cause a lot of problems that are easy to avoid, most people are used to the prefix, and three letters aren't that hard to type.


Don't write C code in C++

They are different languages with different standard libraries, different conventions and standard practices.

The C++ version of <stdio.h> is <cstdio>. Always prefer the C++ headers of the C library when writing in C++. They always begin with c and won't end in .h. To that end the <iostream> is preferred for printing in C++.

In C++ it is preferred to declare the type specifier with the type not the variable.

vector<element> &v

would be declared

vector<element>& v

You should also eschew C style arrays and char* arrays. Prefer std::array for arrays you know the size of at compile time and std::vector for arrays you don't know the size of or that need to change size. (std::array is not dynamic and can't be resized)

You can replace the char* array with an std::array<char> or std::array<std::string>

And don't declare multiple variables on a single line. it is error prone and difficult to read. You did keep most variables on separate lines but you did declare:

vector<element> a, b;

Don't use Global variables

They are dangerous and can lead to hard to find bugs. Can they have a usefulness? Sure. I use them to name Magic Numbers and there are probably other uses but in this case almost definitely not. You could absolutely pass your vector by reference.


Don't return 0 from main()

The compiler will generate it for you and the implication is that you might return anything other than 0.


Use proper return types

Don't return int from functions that don't have a return value. They should be marked void. Your compiler also should have warned you about this.

So turn up your compiler warnings. this will help you tremendously. W4 on VS or Wall on gcc/Clang. Werror is also useful and highly recommended.


Use proper encapsulation

Your class member variables are exposed. This is almost as error prone as global variables and defeats the entire concept of encapsulation. This is however sometimes done with POD types. which I think is what your element essentially is. Switch to a struct (which is the publicly accessable user-defined type) and pull out the functions and you'll have:

struct element {
    long long id;
    std::string name;
    int bmi;
    int max_bmi;
    bool remove;
};

    bool is_lower_id(element a, element b) {
        return a.id < b.id;
    }
    bool is_same(element a, element b) {
        return (a.id == b.id) &&
            (0 == a.name.compare(b.name));
    }
    void update_bmi(element& a){
        this->bmi = a.bmi;
        this->max_bmi = max(this->max_bmi, a.bmi);
    }
    void print() {
        printf("id/name bmi(max) : %lld/%s %d(%d)\n",
            this->id, this->name.c_str(), this->bmi, this->max_bmi);
    }

Then prefer member initialization where possible. You have for loop dedicated to initializing every elements remove to true. That can be done with brace initialization. bool remove{ true }


You use a Yoda conditional in your is_same() function. These are considered outdated and difficult to read. Also any decent linter should catch the typo that they are used to prevent. You also unnecessarily use the std::string compare method. You don't need the conversion to int only to compare the int to 0 and convert to Boolean. Two strings can be compared with ==.

You should also pass by const reference in those functions to avoid unnecessary copying.

By removing your printf call and using std::cout those functions now look like this:

bool is_lower_id(const element& a, const element& b)
{
    return a.id < b.id;
}

bool is_same(const element& a, const element& b)
{
    return a.id == b.id && a.name == b.name;
}

void update_bmi(element& lhs, element& rhs) {
    lhs.bmi = rhs.bmi;
    lhs.max_bmi = std::max(lhs.max_bmi, rhs.bmi);
}

void print(const element& elem) {
    std::cout << elem.id << elem.name << elem.bmi << elem.max_bmi << '\n';
}

However you can overload the comparison operators for user defined types and this is the perfect opportunity for that! It should look something like this.

bool operator==(const element& lhs, const element& rhs) { return (lhs.id == rhs.id) && (lhs.name == rhs.name); }
bool operator!=(const element& lhs, const element& rhs) { return !operator==(lhs, rhs); }
bool operator< (const element& lhs, const element& rhs) { return lhs.id < rhs.id; }
bool operator> (const element& lhs, const element& rhs) { return operator< (rhs, lhs); }
bool operator<=(const element& lhs, const element& rhs) { return !operator> (lhs, rhs); }
bool operator>=(const element& lhs, const element& rhs) { return !operator< (lhs, rhs); }

Now all the traditional comparators will work with your user defined type.


In print_list why do you do this?:

printf("%s:%d\n", __func__, __LINE__);

I'm not certain what purpose this serves. After all most compilers and IDE's will give you the line of a function in the case of an error or exception. But by all means put it back in if you need it. This is also a great opportunity to use a ranged-for loop. They're less error-prone and neater and easier to read.

void print_list(std::vector<element>& vec)
{
    for (auto& elem : vec)
    {
        print(elem);
    }
}

Now for your update_list function. If I understand correctly you have two vectors. If an element of vector two doesn't exist in vector one then it is added. In your code you remove values from the second vector if adding it to the first leaving the second vector populated with the duplicates. However you seem only really interested in the (no-longer)global vector. If you don't need the vectors of duplicates then you can greatly simplify your code.

Switch to an std::map and set the keys to the element.id. This will keep your collection sorted and make merging non-duplicates fantastically easy. (this assumes elements that share an id are implicitly duplicate. Before you insert the new elements into the map test to see if they exist in the old one and update_max_bmi accordingly.

void update_list_v2(std::map<int, element>& lhs, std::map<int, element>& rhs)
{
    for (auto& elem : rhs)
    {
        if (lhs.count(elem.first)) // checks if the key from new data exists in the old data
        {
            update_bmi(elem.second, lhs[elem.first]);
        }
        lhs.insert(elem);
    }
}

*Note I passed both containers to the function and used the more common convention of naming them lhs (left-hand side) and rhs (right-hand side).


Putting it all together (using @Edward's aggregate initialization) it will look something like this:

#include <algorithm>
#include <iostream>
#include <map>
#include <string>

struct element
{
    int id;
    std::string name;
    int bmi;
    int max_bmi;
};

bool operator==(const element& lhs, const element& rhs) { return (lhs.id == rhs.id) && (lhs.name == rhs.name); }
bool operator!=(const element& lhs, const element& rhs) { return !operator==(lhs, rhs); }
bool operator< (const element& lhs, const element& rhs) { return lhs.id < rhs.id; }
bool operator> (const element& lhs, const element& rhs) { return operator< (rhs, lhs); }
bool operator<=(const element& lhs, const element& rhs) { return !operator> (lhs, rhs); }
bool operator>=(const element& lhs, const element& rhs) { return !operator< (lhs, rhs); }

void update_bmi(element& lhs, element& rhs) {
    lhs.max_bmi = std::max(lhs.max_bmi, rhs.bmi);
}

void print(const element& elem) {
    std::cout << elem.id << elem.name << elem.bmi << elem.max_bmi << '\n';
}

void print_list(const std::map<int, element>& vec) {
    for (auto& elem : vec) {
        print(elem.second);
    }
}

void update_list_v2(std::map<int, element>& lhs, std::map<int, element>& rhs)
{
    for (auto& elem : rhs)
    {
        if (lhs.count(elem.first)) // checks if the key from new data exists in the old data
        {
            update_bmi(elem.second, lhs[elem.first]);
        }
        lhs.insert(elem);
    }
}

int main()
{
    std::map<int, element> a = {
        { 12, { 12, "a", 12 } },
        { 11, { 11, "b", 11 } },
        { 13, { 13, "c", 13 } },
        { 5, { 5, "d", 5 } },
        { 6, { 6, "e", 6 } },
        { 7, { 7, "f", 7 } }
    };
    std::map<int, element> b ={
        { 12, {12, "a", 20} },
        { 1, { 1, "x", 5 } },
        { 13, { 13, "c", 5 } },
        { 5, { 5, "d", 10 } },
        { 6, { 6, "e", 6 } },
        { 99, { 99, "y", 5 } }
    };

    update_list_v2(a, b);
    print_list(a);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.