5
\$\begingroup\$

I am trying to improve the algorithms for the following code!

The problem I am trying to solve is that I have nested loops that don't look efficient. This includes the Sales_item.h file from C++ primer 5th edition that may have to be updated if we want to go another design route.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "../include/Sales_item.h"

// This code transcends the book itself!
using namespace std;

int main()
{
    vector<Sales_item> library;
    Sales_item temp_book;
    ifstream file("../include/transactions.txt");
    bool new_book;

    while ( file >> temp_book )
    {
        new_book = true;
        for (int book=0; book<library.size(); book++)
        {
            if (library[book].isbn() == temp_book.isbn())
            {
                library[book] += temp_book;
                new_book = false;
            }
        }
        if (new_book)
        {
            library.push_back(temp_book);
        }
    }

    for ( Sales_item book : library )
    {
        cout << book << endl;
    }

    file.close();
    library.clear();

    return 0;
}

This below code is the Sales_item.h file.

/*
 * This file contains code from "C++ Primer, Fifth Edition", by Stanley B.
 * Lippman, Josee Lajoie, and Barbara E. Moo, and is covered under the
 * copyright and warranty notices given in that book:
 * 
 * "Copyright (c) 2013 by Objectwrite, Inc., Josee Lajoie, and Barbara E. Moo."
 * 
 * 
 * "The authors and publisher have taken care in the preparation of this book,
 * but make no expressed or implied warranty of any kind and assume no
 * responsibility for errors or omissions. No liability is assumed for
 * incidental or consequential damages in connection with or arising out of the
 * use of the information or programs contained herein."
 * 
 * Permission is granted for this code to be used for educational purposes in
 * association with the book, given proper citation if and when posted or
 * reproduced.Any commercial use of this code requires the explicit written
 * permission of the publisher, Addison-Wesley Professional, a division of
 * Pearson Education, Inc. Send your request for permission, stating clearly
 * what code you would like to use, and in what specific way, to the following
 * address: 
 * 
 *     Pearson Education, Inc.
 *     Rights and Permissions Department
 *     One Lake Street
 *     Upper Saddle River, NJ  07458
 *     Fax: (201) 236-3290
*/ 

/* This file defines the Sales_item class used in chapter 1.
 * The code used in this file will be explained in
 * Chapter 7 (Classes) and Chapter 14 (Overloaded Operators)
 * Readers shouldn't try to understand the code in this file
 * until they have read those chapters.
*/

#ifndef SALESITEM_H
// we're here only if SALESITEM_H has not yet been defined 
#define SALESITEM_H

// Definition of Sales_item class and related functions goes here
#include <iostream>
#include <string>

class Sales_item {
// these declarations are explained section 7.2.1, p. 270 
// and in chapter 14, pages 557, 558, 561
friend std::istream& operator>>(std::istream&, Sales_item&);
friend std::ostream& operator<<(std::ostream&, const Sales_item&);
friend bool operator<(const Sales_item&, const Sales_item&);
friend bool 
operator==(const Sales_item&, const Sales_item&);
public:
    // constructors are explained in section 7.1.4, pages 262 - 265
    // default constructor needed to initialize members of built-in type
    Sales_item() = default;
    Sales_item(const std::string &book): bookNo(book) { }
    Sales_item(std::istream &is) { is >> *this; }
public:
    // operations on Sales_item objects
    // member binary operator: left-hand operand bound to implicit this pointer
    Sales_item& operator+=(const Sales_item&);

    // operations on Sales_item objects
    std::string isbn() const { return bookNo; }
    double avg_price() const;
// private members as before
private:
    std::string bookNo;      // implicitly initialized to the empty string
    unsigned units_sold = 0; // explicitly initialized
    double revenue = 0.0;
};

// used in chapter 10
inline
bool compareIsbn(const Sales_item &lhs, const Sales_item &rhs) 
{ return lhs.isbn() == rhs.isbn(); }

// nonmember binary operator: must declare a parameter for each operand
Sales_item operator+(const Sales_item&, const Sales_item&);

inline bool 
operator==(const Sales_item &lhs, const Sales_item &rhs)
{
    // must be made a friend of Sales_item
    return lhs.units_sold == rhs.units_sold &&
           lhs.revenue == rhs.revenue &&
           lhs.isbn() == rhs.isbn();
}

inline bool 
operator!=(const Sales_item &lhs, const Sales_item &rhs)
{
    return !(lhs == rhs); // != defined in terms of operator==
}

// assumes that both objects refer to the same ISBN
Sales_item& Sales_item::operator+=(const Sales_item& rhs) 
{
    units_sold += rhs.units_sold; 
    revenue += rhs.revenue; 
    return *this;
}

// assumes that both objects refer to the same ISBN
Sales_item 
operator+(const Sales_item& lhs, const Sales_item& rhs) 
{
    Sales_item ret(lhs);  // copy (|lhs|) into a local object that we'll return
    ret += rhs;           // add in the contents of (|rhs|) 
    return ret;           // return (|ret|) by value
}

std::istream& 
operator>>(std::istream& in, Sales_item& s)
{
    double price;
    in >> s.bookNo >> s.units_sold >> price;
    // check that the inputs succeeded
    if (in)
        s.revenue = s.units_sold * price;
    else 
        s = Sales_item();  // input failed: reset object to default state
    return in;
}

std::ostream& 
operator<<(std::ostream& out, const Sales_item& s)
{
    out << s.isbn() << " " << s.units_sold << " "
        << s.revenue << " " << s.avg_price();
    return out;
}

double Sales_item::avg_price() const
{
    if (units_sold) 
        return revenue/units_sold; 
    else 
        return 0;
}
#endif
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Would you mind including the header since we don't know who the author of said book is, and we might not have access to the book? We can deduce much of what's in it, but I'm having a hard time guessing at what operator+=() does to a book. Does it simply add the price of temp_book to the one already in the library? \$\endgroup\$ Jun 18, 2018 at 0:54

2 Answers 2

5
\$\begingroup\$

Here are some things that may help you improve your program.

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.

Understand variable scoping

When a variable goes out of scope, as with file and library at the end of main, that variable's destructor is called, cleaning everything up. In this case, it means that file.close() and library.clear() are not needed because these things will happen automatically. Generally speaking, it's prudent to close files as soon as possible, so if you did decide to use an explicit close, it could appear just before the final for loop instead.

Don't hardcode file names

Generally, it's not a good idea to hardcode a file name in software, and generally especially bad if it's an absolute file name (as contrasted with one with a relative path). Instead, it would be better to allow the user of the program to specify the name, as with a command line parameter.

Be thoughtful about variable names

Variable names temp_book, new_book and library are good because they convey what those variables mean within the context of the program. I'm not as fond of the variable file -- maybe infile would be a small improvement.

Point the compiler to the required include directories

Rather than coding the relative location of the Sales_item.h file like this:

#include "../include/Sales_item.h"

it is generally better to only put the name of the header within the source code like this:

#include "Sales_item.h"

Then give the correct parameters to the compiler to be able to find that header (e.g. for gcc, that would be -I../include). This results in much less fragile and more portable builds because it doesn't presume a particular file structure for the source code.

Don't use std::endl if you don't really need it

The difference between std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Use const where practical

At the moment, the results are printed like this:

for ( Sales_item book : library )
{
    cout << book << endl;
}

This works, but may (depending on compiler) make a copy of each book before printing. To expressly tell the compiler that this is not needed, we can use the keyword const to indicate that the printing of a book does not alter its contents. Also, we can use the auto keyword to make the compiler do more of the work, and lessen the burden on the programmer:

for ( const auto &book : library )
{
    cout << book << endl;
}

Use standard library structures and functions

The printing noted above be done instead using std::copy:

std::copy(std::begin(library), std::end(library), 
    std::ostream_iterator<Sales_item>(std::cout, "\n"));

There is not a big difference here, but it's good to be aware of the more modern C++ idioms.

Rethink the data structures

Right now, the bulk of the code is concerned with making sure there is only one copy of each book in the vector. It also contains the somewhat peculiar line:

library[book] += temp_book;

by which I infer that each book contains its own count or cumulative sales. Consider how this might be written using C++17 and a std::unordered_set:

int main(int argc, char *argv[])
{
    if (argc != 2) {
        std::cout << "Usage: booksales infile.txt\n";
        return 1;
    }
    std::ifstream file(argv[1]);
    std::unordered_set<Sales_item> library{};
    Sales_item temp_book{};

    while ( file >> temp_book ) {
        auto [it, new_book] = library.insert(temp_book);
        if (!new_book) {
            *it += temp_book;
        }
    }
    std::copy(std::begin(library), std::end(library), 
        std::ostream_iterator<Sales_item>(std::cout, "\n"));
}

Since you've said you're just beginning, don't be too concerned if you don't understand all of this yet, or if you can't compile it because your compiler doesn't yet support C++17. My goal here is to inspire you to keep learning and use the whole language to write code that is elegant, expressive and error-free.

Use C++17 features if available

There are a number of C++17 features that are really handy. For example, the previous section of code includes this:

auto [it, new_book] = library.insert(temp_book);
if (!new_book) {
    *it += temp_book;
}

To understand this, we need to understand that set.insert returns a pair of values. The first is an iterator that points to either the newly inserted value or the value that prevented insertion (because only unique values are allowed within a set). The second is a bool that is true if a value was actually inserted into the set. Using auto frees us from having to declare variables, but the C++17 part is the [it, new_book]. This is called a structured binding and is new in C++17. However, if you only have C++11, you can still write code that uses the std::set. Using only C++11, here's how you could write that:

std::pair<decltype(library.begin()),bool>bookpair{library.insert(temp_book)};
if (!bookpair.second) {
    *(bookpair.first) += temp_book;
}

FYI

For what it's worth, here's the file I used to test. It's very likely it doesn't match the original, but it may help anyone else who is reading.

Sales_item.h

#ifndef SALES_ITEM_H
#define SALES_ITEM_H
#include <string>
#include <iostream>
#include <functional>

class Sales_item {
public:
    friend std::istream &operator>>(std::istream &in, Sales_item & si) {
        si.quantity = 1;
        return in >> si.my_isbn;
    }
    friend std::ostream &operator<<(std::ostream &out, const Sales_item &si) {
        return out << si.quantity << '\t' << si.my_isbn;
    }
    bool operator==(const Sales_item &other) const {
        return my_isbn == other.my_isbn;
    }
    const Sales_item &operator+=(const Sales_item other) const {
        quantity += other.quantity;
        return *this;
    }
    std::string isbn() const {
        return my_isbn;
    }
private:
    std::string my_isbn;
    mutable unsigned quantity = 0;
};

// std::hash template specialization
namespace std {
    template<> struct hash<Sales_item> {
        size_t operator()(const Sales_item& s) const {
            return hash<string>{}(s.isbn());
        }
    };
}

#endif // SALES_ITEM_H
\$\endgroup\$
2
  • \$\begingroup\$ Holy smokes, this answered so many questions I had. Thank you! I really appreciate the time and effort to help out the community. ( Because comments are used to ask for clarification, I really wish I can get an explanation of the part where we store new books in the library vector: namely, auto [it, new_book] ). Also I will note that my book is for C++11 and not C++17, so I do need to catch up. \$\endgroup\$
    – Randy Diaz
    Jun 19, 2018 at 22:45
  • \$\begingroup\$ I'm gratified that you found it useful. I've added some explanation about the C++17 feature and showed how something similar (but not quite as pretty) can be done with C++11. Hope it helps! \$\endgroup\$
    – Edward
    Jun 19, 2018 at 23:33
4
\$\begingroup\$

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)


new_book is defined outside the loop, but only used in side it. Move the declaration to the first line: bool new_book = true;


    for (int book=0; book<library.size(); book++)

Use a range-for.

for (auto& item : library) {
    if (item.isbn() == temp_book.isbn())
    ⋮

You are right: it is inefficient because you keep iterating through the entire library even after you found it.

But really, you should not write that loop at all. Use std::find_if.

In this case, you could maintain a sorted vector (probably faster for searching) or use std::map (simple to use). You are inefficient for doing a linear search, when you could be doing a binary search.

// using a std::map

auto [it,found] = library.insert(temp_book);
if (found) *it += temp_book;

and that’s it! [docs]


file.close();
library.clear();

return 0;

RAII. The file and library are both going out of scope, and your manual clean-up will not stop the automatic destructors from being used anyway.

\$\endgroup\$
4
  • \$\begingroup\$ You can, however, in a CPP. You can. Does not change the problem that it is bad practice and likely to get you trouble at some point in the future. I don't see a recommendation in the CG that says use it. Its diabolically bad in a header as you can break other peoples code. In a source file its stull bad as you can accidently break your own code. The actual issues is explained here: stackoverflow.com/questions/1452721/… \$\endgroup\$ Jun 18, 2018 at 23:25
  • \$\begingroup\$ @MartinYork You misread/misquoted that: no period after CPP. You can put individual declarations. In fact, I linked to the same S.O. post you did here! \$\endgroup\$
    – JDługosz
    Jun 18, 2018 at 23:36
  • \$\begingroup\$ It makes a lot of sense to sort the objects while I store it, I should've printed the book while I was storing it for this specific example. Is the purpose of std::map library used for vectorizing operations on vectors? \$\endgroup\$
    – Randy Diaz
    Jun 19, 2018 at 22:50
  • 1
    \$\begingroup\$ @RandyDiaz I don’t understand what you are asking. map is a collection that is indexed by an arbitrary key. I don’t know of any beginners’ information on the web off-hand, but search for STL Containers. \$\endgroup\$
    – JDługosz
    Jun 21, 2018 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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