Some appropriate ways to read a line in C/C++

Most of the ways that doesn’t require string size checking would possibly cause buffer overflow error

Using scanf

Code
char line[100]; // this string can contain maximum 99 characters
scanf("%[^\n]", line); // read every character until meet '\n'
scanf("%*c"); // = cin.ignore(1), ignore '\n' character for the next input statement

Using std::getline (string)

Systax: istream& getline(istream & is, string & str, char delim = ‘\n’);
“Extracts characters from is and stores them into str until the delim character is found“.
“The delim character is extracted and discarded (it is not stored)” .

So we don’t have to ignore newline character after this function.
And since string is essentially a vector ( built in data type), we also don’t have to specify its size (length). Thus, although this function does not care about the size of string, it’s safe to use.

Code C++

string s;
getline(cin, s);

Using std::istream::getline( char *)

Syntax: istream& getline(char * s, streamsize n, char delim = ‘\n’);
Extracts characters from istream object and stores them into s until the delim character is found or “n characters have been written to s (including the terminal null character)”.
The delim character is extracted and discarded.

So basically this function is the same as std::getline(string) function. Except we have to specify the maximum size of string because char is a primitive data type of C++.

Code C++

char line[100];
cin.getline(line, 100);

Using gets

Systax: char * gets( char * s);
“Reads characters from stdin and stores them as a C string into s until a newline character or the end-of-file is reached”
The newline character is not copied to s.

This function is unsafe because it does not have size checking, when the size of input string is equal or greater than the size we declare, it causes buffer overflow.

Code C

char line[100]; // contains maximum 99 characters
gets(line); // the size of input string should <= 99

Using fgets

Syntax: char * fgets(char * str, int num, FILE * stream);
“Reads characters from stream and stores them as a C string into str until (num-1) characters have been read or either a newline or the end-of-file is reached”.
The newline character is copied to str. So this function is quite not comfortable to use when the actual size of the string has 1 more character than you expect.
But it’s safer than gets because it has size cheking.

Code C

char line[100]; 
fgets(line, 100, stdin); 

Conclusion: should use getline

Happy coding

Advertisements

Read some tricky input format in C/C++

Problem 1

Format
Input:
+ 2 integer numbers on each line
+ end of input when 2 numbers are both equal to 0
Output:
+ sum of 2 numbers on each line

Code C

int a, b;
while( scanf("%d %d", &a, &b), (a || b) ) {
    printf("%d\n", a + b);
}

 

Code C++

int a, b;
while( cin >> a >> b, (a || b) ) {
    cout << a + b << '\n';
}

Problem 2

Format
Input:
+ 2 integer numbers on each line
Output:
+ sum of 2 numbers on each line

E.x 
Input:
1 2
3 4
Output:
3
7

Code C

int a, b;
while( scanf("%d %d", &a, &b) == 2 ) {
// while ( scanf("%d %d", &a, &b) != EOF ) {
    printf("%d\n", a + b);
}

Code C++

int a, b;
while( cin >> a >> b ) {
    cout << a + b << '\n';
}

Problem 3

Format
Input:
+ some integers on each line
Output:
+ sum of 2 numbers on each line

E.x 
Input:
1 2 3
4 5
6 7 8 9
Output:
6
9
30

Code C++

string s;
while( getline(cin, s) ) {
    istringstream iss(s);
    int sum = 0;
    int v;
    while( iss > v ) sum += v;
    cout << sum << '\n';
}

Happy coding

Ngen – tiện ích tự động tạo và so sánh test case

Sau một thời gian quá ức chế khi giải bài trên SPOJ mà không xem được test case để biết mình sai chỗ nào ( không giống như codeforces ), mình quyết định viết một tool nho nhỏ để bớt đau đầu về việc mò test thủ công bằng tay.

Ngen là một tool tự động tạo input và so sánh output file thuật toán của bạn, với output file thuật toán đúng. Và điều kiện là bạn phải tự viết file tạo input, và có file thuật toán đã AC. ( code bằng C++ )

Mình đã test và thấy nó khá là tiện + hiệu quả khi giúp mình AC một số bài trước đó mình chưa AC.

Platform: based Unix
GitHub: https://goo.gl/Rw84QM , kèm hướng dẫn

ngen

Happy coding 😀

Forward declaration và Header file inclusion trong C++, khi nào nên dùng cái nào ?

Forward declaration

Là việc khai báo trước ( xét trong phạm vi của bài viết ) tên của một class khác ( class B ) trong ( và trước phần khai báo ) của class hiện tại ( class A ).

class B;

class A
{
public:
    void method();

private:
    int data;
};

Header file inclusion

Include thư viện có lẽ là không ai không biết, trong bài này chúng ta chỉ nói đến trường hợp include một header file của class khác ( chẳng hạn class B ), vào header file của class hiện tại ( chẳng hạn class A ).

#include "B.h"

class A
{
public:
    void method();

private:
    int data;
};

Đặt vấn đề

Có thể thấy, việc include hay khai báo trước class B trong class A đều phục vụ chung một mục đích đó là để có thể sử dụng class B trong class A. Hai cách làm này chắc chắn không tương đương nhau, vậy chúng khác nhau như thế nào và trong trường hợp nào thì nên dùng Header file inclusion/ Forward declaration.

Khi nào dùng Forward declaration ?

Khi sử dụng Forward declaration class B trong class A, chúng ta làm cho class A biết đến sự tồn tại của class B, tức là chỉ quan tâm đến phần khai báo của class B, mà không cần biết định nghĩa của nó. Điều này làm hạn chế những thứ mà chúng ta có thể làm với class B ở trong class A, và dẫn đến những trường hợp chúng ta nên dùng Forward declaration sau đây:

  •  Trong phần định nghĩa của A chỉ có dữ liệu kiểu con trỏ B thay vì một dữ liệu kiểu B ( B * b, thay vì B b ). Bởi vì khi ta khai báo một kiễu dữ liệu của B ( B b ), compiler cần phải biết toàn bộ class B, nghĩa là cả phần khai báo và phần định nghĩa; điều này là không cần thiết khi chỉ khai báo con trỏ đến B.
  •  Không có bất cứ sự sử dụng định nghĩa của B ( như gọi hàm của B, truy cập dữ liệu của B… ) trong phần định nghĩa của A.
  •  Nếu class B rất lớn và phức tạp, bạn có thể tránh include nó càng ít càng tốt, thay bằng Forward declaration, nhằm giảm thời gian compile
  •  Nếu B thay đổi thường xuyên: trong trường hợp này nếu dùng forward declaration, thì B phải được recompiled, A.cpp nếu có sử dụng phần định nghĩa của B ( như gọi hàm của B… ) thì cũng phải được recompiled, tuy nhiên A.h và bất cứ file nào include A.h đều không phải recompiled. Vì như đã đề cập ở trên, A.h chỉ quan tâm đến sự tồn tại của B, nên những thay đổi ở B cũng không làm thay đổi sự tồn tại đó, do đó A.h không cần recompiled, điều này giúp giảm thời gian biên dịch. ( * )

( * ): So sánh với cách Header file inclusion trong trường hợp này thì nếu B thay đổi, thì cả A, và bất cứ file nào include A.h ( hay B.h ) cũng phải được recompiled, thậm chí nếu chúng không hề sử dụng phần định nghĩa của B. Điều này là dễ hiểu khi mà toàn bộ nội dung của file include ( B.h ) được sao chép và thế chỗ dòng include này ( sau quá trình tiền xử lí – preprocessor )

class B;
class A
{
private:
    B * b_1;    // ok, it's a pointer of type B
    B & b_2;    // ok, it's a reference to type B
    B b;        // WRONG !

public:
    void method()
    {
        b_1->data;   // WRONG, can't access B's data
        *b_1.data;   // WRONG, can't de-reference
        b_1->doSomething();    // WRONG, can't use B's function
    }
};
  • Khi hai class cần include lẫn nhau: ta xem xét trường hợp sau đây:
// A.h
#include "B.h"    // WRONG here
class B;          // This will work
class A
{
    B * b;
};

// B.h
#include "A.h"
class B
{
    A a;
};

Khi biên dịch chương trình sẽ báo lỗi, vì sự include qua về lẫn nhau dẫn đến việc class này sẽ không bao giờ biết được sự tồn tại của class kia ( ngay cả khi đã có include guard hay #pragma once ). Ta giải quyết vấn đề này bằng cách sử dụng Forward declaration cho class A vì class A chỉ chứa con trỏ đến B

Khi nào dùng Header file inclusion ?

Từ những trường hợp của Forward declaration, chúng ta có thể dễ dàng suy ra những trường hợp dùng Header file inclusion:

  • Sử dụng định nghĩa của B ( truy cập dữ liệu, sử dụng hàm của B .. )
  • Sử dụng sizeof ( B ) ( nếu chỉ biết sự tồn tại của B thì không thể dùng được size of đối với trường hợp Forward declaration )
  • Sử dụng RTTI
  • Sử dụng new/delete, copy… cho B
  • Nếu class A kế thừa từ B
  • Có dữ liệu kiểu B ( B b )

Happy coding 🙂

Nested function và vấn đề khai báo hàm bên trong một hàm khác

Nested function

Nested function là hàm được định nghĩa bên trong một hàm khác.
Nested function được hỗ trợ như là một mở rộng của GNU C, và không được hỗ trợ bởi GNU C++. Mặc dù đã có đề xuất đưa tính năng này lên C++ nhưng nó đã bị từ chối vì nhiều lí do khác nhau ( không có sự hữu dụng nào cho generic programming…. ).
C++ 11 ra đời với tính năng Lambda Expression, như một sự thay thế cho Nested function.
Tuy nhiên chúng ta vẫn có thể khai báo ( declare ) một hàm bên trong một hàm khác ở C++, như là một yếu tố cần cho sự tương thích khi phát triển từ C lên C++

Khai báo hàm bên trong hàm khác ở C++

Việc này giúp tránh được vấn đề làm “pollute global namespace” – có thể hiểu là tránh sự trùng lặp ( về tên ) của một hàm được định nghĩa bên ngoài với một hàm đang có ở global namespace ( hoặc là từ thư viện được include vào chương trình ). Bản chất là dùng tính chất phạm vi của các hàm, biến khi được khai báo, biến/ hàm nào được khai báo gần nhất thì sẽ được ưu tiên sử dụng.

Cá nhân mình không gặp nhiều cách viết khai báo hàm bên trong hàm khác như thế này, cũng có thể là một bad pratice, nhưng vì tò mò muốn biết nên mới tìm hiểu. Thực sự thì mình tin là cũng sẽ không implement cái này nhiều trong code của mình.

Xem xét đoạn code sau:

#include <iostream>
namespace ns
{
void func() {};
}
using namespace std;
int main()
{
void func();
func();
}void func()
{
std::cout << "External function\n";
}

Kết quả sẽ là dòng External function. Việc khai báo hàm func() trong hàm main cho compiler biết rằng kể từ sau việc khai báo, hàm func được sử dụng sẽ là hàm func ở bên ngoài namespace ns.

Cần chú ý ở đây rằng nếu bạn khai báo hàm func ở ngoài ( ngay bên trên) hàm main, trình biên dịch sẽ báo lỗi vì nó không biết ta sẽ sử dụng hàm func nào ( ambiguous ). Việc khai báo ở trong hay ngoài hàm giống nhau ở chỗ compiler sẽ đều đi tìm phần định nghĩa ( definition ) ở tất cả các file khác trong cùng project ( *.h, *.cpp ), từ khoá “extern” là thừa vì nó là mặc định khi declare hàm

Khi bạn include các thư viện ( stl, các thư viện bên thứ 3… ), để sử dụng hàm của riêng bạn, tránh xung đột với các hàm trong các thư viện đó, các bạn cũng có thể sử dụng kĩ thuật này.

Happy codding 🙂

Lỗi khi định nghĩa cho class template trong file .cpp và cách khắc phục

Lỗi gặp khi làm bài tập xây dựng stack, mình có file header như sau:

// stack.h 

template <typename T>
class NStack
{
private:
    T * elem;
    int sz;
public:
    NStack();

    // declaring other methods
};

Và file .cpp:

// stack.cpp
#include "stack.h"
#define MAX_STACK_SIZE 100
template <typename T>
NStack<T>::NStack() 
: elem { new T[ MAX_STACK_SIZE ] },
  sz { 0 }
{}

// defining other methods

Ở chương trình chính, khi bạn khai báo NStack<int> s chẳng hạn, và build thì chương trình sẽ báo lỗi:

Undefined symbols for architecture x86_64:”NStack<int>::NStack()”, referenced from:
_main in exe3.o
ld: symbol(s) not found for architecture x86_64

Đây là một lỗi gặp khi link, compiler không tìm được phần define của constructor NStack<int>::NStack()

Nguyên nhân là do: Một template class, không phải là một class, mà nó chính xác là một “khuôn mẫu” dùng để tạo ra class. Khi ta khai báo NStack<int> s; ta phải chỉ rõ tất cả các template member functions để compiler có thể tạo ra các member functions thuộc kiểu int. Nhưng vì phần define function( ở đây chỉ nêu mẫu constructor ) lại ở file .cpp ( ở file .h ta chỉ declare nó ), compiler không tìm thấy khi “link” các nguyên mẫu hàm ở file .h, vậy nên gây ra lỗi LNK như trên.

Có 3 cách khắc phục cho vấn đề này:
Cách 1: Định nghĩa tất cả các hàm ở trong file header:

// stack.h 

#define MAX_STACK_SIZE 100
template <typename T>;
class NStack
{
private:
    T * elem;
    int sz;
public:
    NStack()
    {
        elem = new T [MAX_STACK_SIZE];
        sz = 0;
    }
    // declaring & defining other methods
}

Làm như cách một sẽ gộp phần khai báo và định nghĩa lại làm một, không hay cho lắm, ta đi đến cách 2 và cách 3 như sau.

Cách 2: Thông báo trước cho compiler biết những kiểu dữ liệu trừu tượng nào ta muốn dùng ở cuối file cpp ( trường hợp ở đây là int )

// stack.cpp
#include "stack.h"
#define MAX_STACK_SIZE 100
template<typename T>
NStack<T>::NStack()
: elem { new T[ MAX_STACK_SIZE ] },
  sz { 0 }
{}

// defining other methods

//...

// Dùng 1 trong 2
template class NStack<int>;
NStack<int> __temp;

Phương án này cũng chưa tốt ghi mà chúng ta phải khai báo trước những kiểu dữ liệu cụ thể trước khi sử dụng, mà điều này nó lại không hợp logic lắm với ý nghĩa của template. Ta đến với cách 3 như sau.

Cách 3: Bỏ toàn bộ phần code định nghĩa hàm vào một file tạm là .tpp ( để compiler bỏ qua file này, không biên dịch, tránh xung đột khi include qua về với file header ). Sau đó include file .tpp này vào cuối file header

// stack.h 

template <typename T>
class NStack
{
private:
    T * elem;
    int sz;
public:
    NStack();

    // declaring other methods
}

#include "stack.tpp"

Happy coding 🙂

Giải đáp những câu phỏng vấn C/C++ của John Sonmez


Đây là những câu hỏi rất hay tớ đọc được trong bài viết Tại sao C/C++ không còn là sự lựa chọn cho bạn nữa ? của John Sonmez, do vinacode dịch. Để giải đáp được những câu hỏi này cần có kiến thức khá vững về C/C++ và nó luôn thôi thúc tớ đi tìm câu trả lời, nhưng không phải trả lời theo kiểu search google và chép đáp án vào, mà tớ muốn bản thân tớ ( và các bạn cũng vậy) phải tiếp xúc với kiến thức trong câu hỏi đó đủ nhiều và có một sự mạch lạc trong tư duy khi giải thích lại nó.

Ok, ko dài dòng nữa, đây là danh sách:

1. Có bao nhiêu cách để khởi tạo một kiểu dữ liệu nguyên thủy trong C++ và đó là những cách nào?

Hiện tại mình có thể nêu ra 3 cách:
int var_1; <- Khởi tạo biến var_1 với giá trị mặc định do môi trường quyết định
int var_1(4); <- Khởi tạo biến var_1 với giá trị được truyền vào
int var_1(var_2); <- Khởi tạo biến var_1 với giá trị của var_2 (copy constructor)
Update:
int var_1 = 4; <- implicit cast
int var_1{4}; <- inintializer list

2. Tại sao bạn nên khai báo một hàm hủy là ảo (virtual) ?

Giả sử có class Parent và class Child kế thừa từ Parent. Ta định nghĩa con trỏ:
Parent * p = new Child();
Lúc này để tạo ra Child(), thì Parent() phải được tạo ra trước. Khi chúng ta delete p, thì cả 2 đối tượng này cũng phải được gọi Destructor.
Vậy nếu không khai báo virtual cho hàm Destructor của Parent, thì chỉ Destructor của Parent được gọi, đối tượng Child() vẫn còn đó
3. Nó có nghĩa gì khi nói rằng C++ hỗ trợ overloading (nạp chồng)?
4. Nêu ra một số ví dụ về overloading trong C++?
5. Khái niệm name mangling trong C++ có nghĩa là gì và tại sao nó lại được sử dụng?
6. Một lớp trừu tượng cơ sở (abstract base) có nghĩa là gì?
7. RTTI có nghĩa là gì?
8. Làm thế nào để bạn có thể truy cập một biến mà nó bị “che khuất” bởi một biến khác có cùng tên?

Có thể sử dụng namespace: đưa 2 biến cùng tên đó vào 2 namespace khác nhau, bạn có 2 biến cùng tên var:
namespace ns1 { int var;}
namespace ns2 { int var;}
Cách truy cập:
ns1::var = 6;
ns2::var = 9;

Cũng có thể dùng class và struct nhưng cách đó khá thô thiển vì phải tạo nên thể hiện của class và struct

Update: Trường hợp biến local bị che khuất bởi biến global có cùng tên, có thể sử dụng toán tử truy cập phạm vi :: để gọi biến global

int x;
int func()
{
int x;
x = 3;    // local
::x = 3; // global
}

9. Khái niệm namespace có nghĩa là gì và làm thế nào để sử dụng nó?

Mới gặp ngay ở câu 8 :))
namespace theo như cách dịch thì là “không gian tên”, tớ cũng chẳng biết dịch như thế nào cho đúng, chỉ biết là nó được dùng để phân loại, gom các đối tượng vào thành một nhóm. Cách dùng như sau:
namespace <name> { // declare or define }
Ví dụ: Tớ có một namespace tên nsmath, và trong namespace này tớ sẽ khai báo một biến distance, một hàm Add và một class Point chẳng hạn

namespace nsmath
</span><span class="text_exposed_show">{
float distance;
float Add(float a, float b);
class Point;
}


Bạn có thể chỉ khai báo propotype như thế, và định nghĩa các hàm và class bên ngoài (như class):

float nsmath::Add(float a, float b) { // add a to b }
class nsmath::Point { // construct };


10. Điểm khác nhau giữa một lớp và một cấu trúc (struct) trong C++ là gì, và so sánh với ngôn ngữ C thì như thế nào?

Điểm khác nhau duy nhất giữa class và struct trong C++ đó là, những thuộc tính của class nếu để mặc định thì nó là private, của struct là public.
So sánh với ngôn ngữ C: ?

11. Khái niệm template là gì? Làm thế nào để sử dụng chúng ?
12. Một hàm tạo sao chép (copy constructor) có nghĩa là gì và khi nào thì nó được sử dụng, đặc biệt là khi so sánh với toán tử =
13. Điểm khác nhau giữa một sao chép “shallow” và “deep” là gì?

14. Hằng toán tử (const operator) nghĩa là gì và nó được sử dụng như thế nào?
15. Điểm khác nhau giữa truyền tham chiếu, truyền tham trị, và truyền bởi con trỏ trong C++ là gì?
16. Khi nào thì nên và khi nào thì không nên trả về một giá trị bởi tham chiếu trong C++?
17. Điểm khác nhau giữa một biến tạo ra trên ngăn xếp (stack) và một biến tạo ra trên heap là gì?

Biến trên stack tự giải phóng khi ra khỏi khối lệnh ( block )
Biến trên heap phải dùng free() ( C ) hoặc delete ( C++ ) để giải phóng


18. Làm thế nào để bạn giải phóng bộ nhớ đã cấp phát động cho một mảng?
19. Đa kế thừa là gì? Khi nào thì nó nên được sử dụng?
20. Một hàm ảo thuần túy (pure virtual) là gì?
21. Từ khóa mutable có ý nghĩa gì?
22. Từ khóa volatile có ý nghĩa gì?
23. Khái niệm STL có nghĩa là gì?
24. Khái niệm Vector có nghĩa là gì?

Vector là một cấu trúc dữ liệu được xây dựng sẵn trong C++

25. Cái gì được chứa strong phần header <algorithms>?
26. Điểm khác nhau giữa ‪#‎include‬ <iostream.h> và #include <iostream> là gì?

iostream.h là thư viện cũ, được thay thế bởi iostream từ C++ 98.
iostream.h được khai báo toàn cục, còn iostream được khai báo cục bộ
Thêm cái nữa đó là nếu #include <iostream.h> thì không cần phải thông báo sử dụng namespace std, nhưng #include <iostream> thì cần

27. Điểm khác nhau giữa “++i” and “i++” là gì?

++i: cộng i lên 1 trước rồi thực hiện phép toán
i++: thực hiện phép toán trước rồi cộng i lên 1
28. Ước lượng short circuit có nghĩa là gì? Nó được sử dụng như thế nào? Tại sao việc sử dụng nó có thể gây nguy hiểm?
29. Toán tử ‘,’ có ý nghĩa gì?
30. Toán tử tam nguyên có nghĩa là gì? Cách sử dụng nó như thế nào?
31. Hàm hằng thành viên (const member) có nghĩa là gì và nó được sử dụng như thế nào?
32. Làm thế nào để sử dụng try/catch trong C++?
33. Tại sao bạn đừng bao giờ ném ra một ngoại lệ trong một hàm hủy?
34. Từ khóa explicit có ý nghĩa gì?

Từ khoá explicit đặt trước Constructor một tham số của một class, thì đối tượng của class này không thể tạo ra bằng implicit cast

class A {
public:
explicit A ( int data ) { // ... }
}
int main() {
A a ( 3 );    // RIGHT
A a = 3;     // WRONG

35. Đâu là cách đúng để thực thi một ép kiểu trong C++?
36. Khái niệm inline có nghĩa là gì?