Блог пользователя Arturgo

Автор Arturgo, история, 5 лет назад, По-английски

Hi everybody,

I started to implement very general functions to use in programming competitions, such as this general reader/writer for C++ tuple, containers, and basic types~:

#include <iostream>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;


template <typename T>
constexpr bool is_tuple = false;

template<typename ... types>
constexpr bool is_tuple<tuple<types...>> = true;

template<typename A, typename B>
constexpr bool is_tuple<pair<A, B>> = true;

	
template<typename T> struct IsContainer { 
	typedef typename remove_const<T>::type test_type;
	template<typename A> static constexpr bool test(A* pt, decltype(pt->begin())* = nullptr, decltype(pt->end())* = nullptr) 
	{ return is_same<decltype(pt->begin()),typename A::iterator>::value && is_same<decltype(pt->end()),typename A::iterator>::value; }
	template<typename A> static constexpr bool test(...) { return false; }
	static constexpr bool value = test<test_type>(nullptr);
};

template<typename T>
constexpr bool is_container = IsContainer<T>::value;


template <typename T>
constexpr bool is_string = is_same<T, string>::value;

template<typename>
struct to_mutable { };

template<typename... Ts>
struct to_mutable<tuple<Ts...>> {
    using type = tuple<typename remove_cv<Ts>::type...>;
};

template<typename... Ts>
struct to_mutable<pair<Ts...>> {
    using type = pair<typename remove_cv<Ts>::type...>;
};


string readline() { string value; getline(cin, value); return value; }

template<typename T, typename ...Args> typename enable_if<!is_tuple<T> && (!is_container<T> || is_string<T>), T>::type read() {
	T value;
	cin >> value;
	return value;
}

template<typename T, typename ...Args> typename enable_if<is_tuple<T>, T>::type read(Args ...args);
template<typename T, typename ...Args> typename enable_if<is_container<T>, T>::type read(size_t N, Args... args);

template<typename T> typename enable_if<is_container<T> && !is_string<T>, T>::type read() { 
	size_t N = read<size_t>();
	return read<T>(N);
}

template<typename X, size_t I = 0, typename ...Args, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I == tuple_size<X>::value, typename to_mutable<X>::type>::type read_tuple(Args... args) { return typename to_mutable<X>::type(); }

template<typename X, size_t I = 0, typename ...Args, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I < tuple_size<X>::value, typename to_mutable<X>::type>::type read_tuple(Args... args) {
	auto tmp = read<typename tuple_element<I, typename to_mutable<X>::type>::type>(args...);
	typename to_mutable<X>::type value = read_tuple<X, I + 1>(args...);
	get<I>(value) = tmp;
	return value;
}

template<typename T, typename ...Args> typename enable_if<is_tuple<T>, T>::type read(Args... args) { return read_tuple<T>(args...); }

template<typename T, typename ...Args> typename enable_if<is_container<T>, T>::type read(size_t N, Args... args) { 
	T container;
	for(size_t i = 0;i < N;i++) { 
		*inserter(container, container.end()) = read<typename T::value_type>(args...);
	}
	return container;
}


void flush() { cout << flush; }

void writesp() { cout << " "; }
void writeln() { cout << "\n"; }

template<typename T> void writesp(const T& value);
template<typename T> void writeln(const T& value);

template<typename T, typename enable_if<!is_container<T> && !is_tuple<T>, T>::type* = nullptr> 
void write(const T& value) { cout << value; }
void write(const string& value) { cout << value; }
void write(const char* value) { cout << value; }

template<typename T, typename enable_if<is_container<T>, T>::type* = nullptr> void writerow(const T& value) { 
	typedef typename T::const_iterator It; 
	for(It it = value.begin();it != value.end();it++) { writesp(*it); }
}

template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I == tuple_size<X>::value, void>::type writerow(const X& t) {}
template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I < tuple_size<X>::value, void>::type writerow(const X& t) { writesp(get<I>(t)); writerow<I + 1>(t); }

template<typename T, typename enable_if<is_container<T>, T>::type* = nullptr> void writecol(const T& value) { 
	typedef typename T::const_iterator It; 
	for(It it = value.begin();it != value.end();it++) { writeln(*it); }
}

template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I == tuple_size<X>::value, void>::type writecol(const X& t) {}
template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I < tuple_size<X>::value, void>::type writecol(const X& t) { writesp(get<I>(t)); writerow<I + 1>(t); }

template<typename T, typename enable_if<!is_container<typename T::value_type> && !is_tuple<typename T::value_type>, T>::type* = nullptr> void write(const T& value) { writerow(value); }
template<typename T, typename enable_if<is_tuple<T>, T>::type* = nullptr> void write(const T& value) { writerow(value); }

template<typename T> void write2d(const T& value) {
	typedef typename T::const_iterator It; 
	for(It it = value.begin();it != value.end();it++) { writeln(*it); }
}

template<typename T, typename enable_if<is_container<typename T::value_type>, T>::type* = nullptr> void write(const T& value) { write2d(value); }
template<typename T, typename enable_if<is_tuple<typename T::value_type>, T>::type* = nullptr> void write(const T& value) { write2d(value); }

template<typename T> void writesp(const T& value) { write(value); writesp(); }
template<typename T> void writeln(const T& value) { write(value); writeln(); }


void fast_io() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }


int main() {
	fast_io();

	int nbRows = read<int>(), nbCols = read<int>();
	auto grid = read<vector<vector<int>>>(nbRows, nbCols);

	write(grid);
	return 0;
}

The final goal is to write the minimum amount of code to describe an algorithm to the machine, by having a big library of algorithms I can use. I have a little tool that selects in the final code only the parts I need.

To use write, it is sufficient to call it with your variable. If you want to print a newline, or a space at the end, use writeln or writesp.

To use read, give the type you want to read between < and >. If you want to read a container (a STL-structure with begin() and end()), you can give sizes to the function, otherwise it'll read the size from the standard input.

This code works with many types, for examples, map<string, vector<pair<int, double>>>, but be aware that some structures (like priority_queue) aren't supported because they don't have begin() or end(). Keep also in mind that if you give sizes as arguments to your functions, they will be interpreted by order of depth in the template definition, but things like pair<vector<int>, vector<int>> will not work with given (different) sizes.

If enough people are interested in such implementations, I'll continue to publish them on my blog. If you find any bug, or if you think another structure should be able to be read/written, please leave a comment.

Thank you for reading.

  • Проголосовать: нравится
  • +108
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Auto comment: topic has been updated by Arturgo (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

It is a très beautiful header.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Arturgo (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Arturgo (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

I mainly use this for reading and writing

The Thing

BTW, this is from Benq's template.

»
4 года назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

I’m not trying to hate here, I’m just wondering how exactly does this template help with competitive programming? To me, it seems that reading input is the easiest part of solving a problem, and I hardly feel like some generic code would make one perform better in programming contests. What’s the actual point of this in programming contests, apart from being an implementation with a pretty-looking API and a very cumbersome header?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится -28 Проголосовать: не нравится

    Haters gonna hate. With that, you don't have to type

    for(int i = 0; i < (int)vec.size(); i++) {
        cin >> vec[i];
    }
    

    when inputting vectors, instead all you have to type is

    re(vec);
    

    For people who aren't fast at typing(me around 20 WPM :P) this could be a real time saver. Another example:

    Instead of writing for inputting vector of vectors

    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            cin >> VecOfVec[i][j];
        }
    }
    

    you can write:

    re(VecOfVec);
    
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Saner input than your given examples:

      First: for(auto& i: vec) cin >> i;

      Second: for(auto& vec: VecOfVec) for(auto& i: vec) cin >> i;

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        That's basically what my reader is doing... NVM, I didn't understand you the first time. :D

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    The goal, at the end (here is just input/output), is to write the minimum amount of code to describe an algorithm, in order to be faster.

    Imagine, you could write :

    #require graph
    
    int main() {
       auto g = read<Graph>();
       write(diameter(g));
    }
    

    It does take you a lot of time to write a complete set of templates, but in a contest, it's really easy to write/debug, because you only have to think about the core concept of the algorithm and not the implementation. I don't really have that template in the code I write, it's added at compile-time and when I submit.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    To avoid cumbersome header you could put all your code in some debug.hpp, and include it in your main code, using only locally using some flag, and if u actually need it in real contest, you could just use the snippet call so all the code will be copy pasted.this way your original code will be clean looking.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      I guess you could write a small preprocessor that would prepend all your local #includes into a big file. I think Petr has something similar to that. However, I’m usually the kind of person that doesn’t enjoy looking at hundreds of lines on the Online Judge neither when trying to troubleshoot my submissions during a contest nor when I try to understand other people’s submissions. In a lot of cases, having snippets to help you with implementations is really useful, but bloating your submissions with hundreds of lines of boilerplate code just to read input seems like a lot of pain for little gain. Especially when reading the input is one of the most straightforward things in a solution. Debugging might be a whole different issue, though.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        So true, I also prefer macro only for, for loop, and some important stuff, I also like clean code.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for read and write in c++17 can simply use this, it's pretty cool than cin, cout

template <typename... T>
void read(T &... args)
{
    ((cin >> args), ...);
}

template <typename... T>
void write(T &&... args) //rvalue references
{
    ((cout << args), ...);
}

Source