std::cin's APIs

[frek]

Hi all,

I'm developing the project below. How is it from your point of view?

#include <iostream>
#include <vector>

bool binary_search(std::vector<int> vi, int low, int high, int val) {
	int mid;

	while (low <= high) {
		mid = (low + high) / 2;

		if (vi[mid] == val)
			return true;

		else if (vi[mid] < val)
			low = mid + 1;

		else if (vi[mid > val])
			high = mid - 1;
	}
	return false;
}

//************************************************************

void bubble_sort(std::vector<int>& vi) {

	for (int i = 0; i < vi.size(); ++i)
		for (int j = i + 1; j < vi.size(); ++j)
			if (vi[i] > vi[j])
				std::swap(vi[i], vi[j]);
}

//**********************************************

int main()
{
	std::vector<int> vi;
	std::cout << "Enter integer values for the vector. Enter ctrl+z at the end.\n";

	int n;
	while (std::cin >> n) vi.push_back(n);

	// To get rid of ctrl+z remained data in the buffer
	std::cin.clear();

	 // sorting the vector using the bubble sort
	bubble_sort(vi);

	std::cout << "Sorted values are { ";
	for (auto n : vi)
		std::cout << n << ", ";
	std::cout << "}\n";

	int val;
	std::cout << "Enter an integer value to search: ";
 	std::cin >> val;

	binary_search(vi, 0, vi.size() - 1, val) ? std::cout << "val: " << val << " is Found!\n"
		: std::cout << "val: " << val << " is not Found!\n";

	system("pause");
	return 0;
}

1) Apparently std::cin.clear(); on line 43 is not adequate to clean std::cin completely so that we can reuse it in the next operations in the code? Is there a correct and common way for this?

2) Does std::cin, for instance in while (std::cin >> n) on line 40, have any API to check the received data out to know whether it's a number or unwanted data? If not, what suitable method do you use for that purpose?

I checked std::cin's built-in functions for both questions above but couldn't find the answers I'm looking for.

[keskiverto]

I checked std::cin's built-in functions for both questions above but couldn't find the answers I'm looking for.

http://www.cplusplus.com/reference/ios/ios/clear/ Sets a new value for the stream's internal error state flags.
In other words, it does not affect the content of the stream.

If you want to read characters without storing them, there is http://www.cplusplus.com/reference/istream/istream/ignore/

int n;
std::cin >> n

That is formatted input. http://www.cplusplus.com/reference/istream/istream/operator%3E%3E/
The failbit is set if either no characters were extracted, or the characters extracted could not be interpreted as a valid value of the appropriate type.

The >> above attempts to read int. If the next character in stream is, for example 'm', then there is no way to interpret it as integer. Therefore, the failbit will be set.

while ( std::cin >> n )
The >> returns iostream&. Reference to std::cin. Effectively, you do test:
while ( std::cin )
That does use http://www.cplusplus.com/reference/ios/ios/operator_bool/

In other words, the while ( std::cin >> n ) does use the API. Condition is true, if stream had an integer. Condition is false, if there is unwanted data. In the latter case you have to deal with both the failbit and the remaining data in the stream.

[seeplus]

To remove unwanted data from the input stream, you can use .ignore(). This can either ignore a specified number of chars, or until a specified char or number of chars. See http://www.cplusplus.com/reference/istream/istream/ignore/ Note how to specify no limit on chars removed.

[dutch]

ctrl-z is not a character that is entered into the stream.
It is just a way to signal eof from the keyboard.
(Also, it's ctrl-d on linux and mac.)

Also, your binary_search is wrong.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

template <typename T>
bool binary_search(const std::vector<T>& vi, const T& val) {
    size_t low = 0, high = vi.size();
    while (low < high) {
        size_t mid = (low + high) / 2;
        if (vi[mid] == val)
            return true;
        if (vi[mid] < val)
            low = mid + 1;
        else
            high = mid;
    }
    return false;
}

template <typename T>
void selection_sort(std::vector<T>& vi) {
    for (auto it = vi.begin(); it != vi.end(); ++it)
        std::swap(*std::min_element(it, vi.end()), *it);
}

void reset(std::istream& in)
{
    bool eof = in.eof();
    in.clear();
    if (!eof) in.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

int main()
{
    using std::cout, std::cin;

    std::vector<int> vi;
    cout << "Enter integer values for the vector. Enter ctrl+z at the end.\n";

    for (int n; cin >> n; ) vi.push_back(n);
    reset(cin);

    selection_sort(vi);

    cout << "Sorted values are { ";
    for (int n: vi) cout << n << ' ';
    cout << "}\n";

    int val {};
    while (true)
    {
        cout << "Enter an integer value to find: ";
        if (cin >> val) break;
        reset(cin);
        cout << "Bad value!\n";
    }

    bool found = binary_search(vi, val);
    cout << val << " is " << (found ? "" : "not ") << "in the vector\n";
}

[frek]

@keskiverto, @seeplus
If the condition in while uses the API, so is it not suitable to inform the user of their bad input for instance by throwing? if (std::cin.failbit) throw("Bad input!");

Incidentally cin.ignore() doesn't work as expected yet!

// To get rid of ctrl+z remained data in the buffer
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

There's still some unwanted (mostly negative) data that will be used for val on line 55 automatically!

[frek]

I used the method below and it worked properly:

// To get rid of ctrl+z flags settings
std::cin.ignore(INT_MAX, '\n');
std::cin.clear();

Of course if we use std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); in lieu of std::cin.ignore(INT_MAX, '\n'); still the program works properly. And the point is that we must use clear after ignore as above.

[frek]

This is the complete project as a response to the exercise below:
Write a binary search function for a vector<int> (without using the standard one). You can choose any interface you like. Test it. How confident are you that your binary search function is correct? Now write a binary search function for a list<string>. Test it. How much do the two binary search functions resemble each other? How much do you think they would have resembled each other if you had not known about the STL?

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>

bool vector_binary_search(std::vector<int>& vi, const int& val) {
	int mid;
	size_t low = 0, high = vi.size();

	while (low < high) {
		mid = (low + high) / 2;

		if (vi[mid] == val)
			return true;

		else if (vi[mid] < val)
			low = mid + 1;

		else high = mid;
	}
	return false;
}

//************************************************************

bool list_binary_search(std::list<std::string>& ls, const std::string& str) {
	int mid;
	size_t low = 0, high = ls.size();

	while (low < high) {
		mid = (low + high) / 2;

		// Since std::list lacks a random-access iterator, we have to iterate over 
		// elements one by one from beginning up to the position we want to reach
		auto iter = ls.begin();
		for (rsize_t i = 0; i < mid; ++i)
			++iter;

		if (*iter == str)
			return true;

		else if (*iter < str)
			low = mid + 1;

		else high = mid;
	}
	return false;
}

//****************************************************

void bubble_sort(std::vector<int>& vi) {

	for (int i = 0; i < vi.size(); ++i)
		for (int j = i + 1; j < vi.size(); ++j)
			if (vi[i] > vi[j])
				std::swap(vi[i], vi[j]);
}

//***********************************************************

void selection_sort(std::list<std::string>& ls) {

	for (auto it = ls.begin(); it != ls.end(); ++it)
		std::swap(*std::min_element(it, ls.end()), *it);
}

//**********************************************

int main()
{
	std::vector<int> vi;
	std::cout << "Enter integer values for the vector. Enter ctrl+z at the end.\n";

	for (int n; std::cin >> n;) vi.push_back(n);

	// To get rid of ctrl+z flags settings
	std::cin.ignore(INT_MAX, '\n');
	std::cin.clear();

	//Sort the vector using the bubble sort
	bubble_sort(vi);

	std::list<std::string> ls;
	std::cout << "Enter string values for the list. Enter ctrl+z at the end.\n";

	for (std::string s; std::cin >> s;) ls.push_back(s);

	// To get rid of ctrl+z flags settings
	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
	std::cin.clear();

	// Sort the list this time using the selection sort
	selection_sort(ls);

	std::cout << "Sorted vector values are { ";
	for (auto n : vi)
		std::cout << n << ", ";
	std::cout << "}\n";

	std::cout << "Sorted list values are { ";
	for (auto s : ls)
		std::cout << s << ", ";
	std::cout << "}\n\n";

	int val;
	std::cout << "Enter an integer value to search in the vector: ";
	std::cin >> val;

	vector_binary_search(vi, val) ? std::cout << "val: " << val << " is Found!\n"
		: std::cout << "val: " << val << " is not Found!\n\n";

	std::string str;
	std::cout << "Enter a string value to search in the list: ";
	std::cin >> str;

	list_binary_search(ls, str) ? std::cout << "string: " << str << " is Found!\n"
		: std::cout << "string: " << str << " is not Found!\n";

	system("pause");
	return 0;
}

On lines 36 to 38 I had to write a code that mimics random access iterator functionality.

[seeplus]

bool vector_binary_search(std::vector<int>& vi, const int& val) {

If a variable is passed by ref and not changed, then mark as const.

There's no need to pass an int by const ref - it can just be passed by value.

eg

bool vector_binary_search(const std::vector<int>& vi, int val) {
	for (size_t low {}, high {vi.size()}; low < high; ) {
		const auto mid {(low + high) / 2};

		if (vi[mid] == val)
			return true;

		if (vi[mid] < val)
			low = mid + 1;
		else
			high = mid;
	}

	return false;
}

[JLBorges]

> Write a binary search function for a vector<int> (without using the standard one).
> Now write a binary search function for a list<string>.
> How much do the two binary search functions resemble each other?

The same code (with very different performance implications) can be used for both.

include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <string>

namespace frek
{
    template < typename ITERATOR, typename T >
    bool binary_search( ITERATOR begin, ITERATOR end, const T& value )
    {
        if( begin == end ) return false ;

        const auto n = std::distance( begin, end ) ;
        const auto mid = std::next( begin, n/2 ) ;

        if( *mid == value ) return true ;
        else if( *mid < value ) return frek::binary_search( std::next(mid,1), end, value ) ;
        else return frek::binary_search( begin, mid, value ) ;
    }

    template < typename SEQ, typename T >
    bool binary_search( const SEQ& seq, const T& value )
    { return frek::binary_search( std::begin(seq), std::end(seq), value ) ; }
}

int main()
{
    std::cout << std::boolalpha ;

    const std::vector<int> vec { 1, 2, 3, 4, 5 } ;
    for( int i = 0 ; i < 7 ; ++i ) std::cout << i << ' ' << frek::binary_search( vec, i ) << '\n' ;

    std::cout << '\n' ;

    std::list<std::string> lst ;
    for( int v : vec ) lst.push_back( std::to_string(v) ) ;
    for( int i = 0 ; i < 7 ; ++i ) std::cout << i << ' ' << frek::binary_search( lst, std::to_string(i) ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/69d5abe4e375bde6

[frek]

namespace frek! Hhhhhh, interesting. But why have you thought a namespace here is requited?

[keskiverto]

Namespace std has binary_search too. Depending on library implementation it could be a visible and valid candidate.

[frek]

But using a simple renaming (e.g., my_binary_search) instead, we could avoid that

[keskiverto]

The frek:: is the "simple rename".