23.07.11 백준 문제로부터

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

백준 10816 문제다. 대충 std::map으로 뚝딱뚝딱하면 되는 문제.

내가 문제를 풀고 다른 사람들의 코드와 비교하던 중에

std::end() 함수에 대해 알게되었다.

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m, temp;
    unordered_map<int, int> card;
    cin >> n;

    while (n--)
    {
        cin >> temp;
        if (card.find(temp) == /*card.end()*/)
            card[temp] = 1;
        else
            card[temp]++;
    }

    cin >> m;
    while (m--)
    {
        cin >> temp;
        if (card.find(temp) != /*card.end()*/)
            cout << card[temp] << ' ';
        else
            cout << "0 ";
    }
        

    return 0;
}

위 코드에서 주석친 부분을 end(card)로 바꾸게 되면 코드 실행 속도가 조금 더 빨라져서 의문을 가지고 찾아보았다.

https://en.cppreference.com/w/cpp/iterator/end

std::end, std::cend - cppreference.com

문서를 보면 처음에 이렇게 되어있다.

STL 관련된 헤더가 많이 보이는데 여기도 타고 들어가보았다.

뭐가 나와야 알지, 원하는 정보가 안 나온다.

이것저것 타고 들어가다가 initializer_list나 valarray 라는 것도 알고 좋은 탐구가 되었다.

 

어딘가에 헤더같은 거 까놓은 사이트가 있을 것 같긴한데 그냥 궁금해서 컴퓨터에 저장되어있는 헤더를 까보았다.

C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.36.32532\include

C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.36.32532\crt\src\stl

위는 각각 헤더 파일과 소스 파일이 저장된 곳이다.

 

먼저, std 이름공간 사용을 iostream 헤더 포함 후 쓰니까 iostream부터 찾아본다.

// iostream standard header

// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#pragma once
#ifndef _IOSTREAM_
#define _IOSTREAM_
#include <yvals_core.h>
#if _STL_COMPILER_PREPROCESSOR
#include <istream>

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new
_STD_BEGIN
#ifdef _M_CEE_PURE
__PURE_APPDOMAIN_GLOBAL extern istream cin;
__PURE_APPDOMAIN_GLOBAL extern ostream cout;
__PURE_APPDOMAIN_GLOBAL extern ostream cerr;
__PURE_APPDOMAIN_GLOBAL extern ostream clog;
__PURE_APPDOMAIN_GLOBAL extern istream* _Ptr_cin;
__PURE_APPDOMAIN_GLOBAL extern ostream* _Ptr_cout;
__PURE_APPDOMAIN_GLOBAL extern ostream* _Ptr_cerr;
__PURE_APPDOMAIN_GLOBAL extern ostream* _Ptr_clog;

__PURE_APPDOMAIN_GLOBAL extern wistream wcin;
__PURE_APPDOMAIN_GLOBAL extern wostream wcout;
__PURE_APPDOMAIN_GLOBAL extern wostream wcerr;
__PURE_APPDOMAIN_GLOBAL extern wostream wclog;
__PURE_APPDOMAIN_GLOBAL extern wistream* _Ptr_wcin;
__PURE_APPDOMAIN_GLOBAL extern wostream* _Ptr_wcout;
__PURE_APPDOMAIN_GLOBAL extern wostream* _Ptr_wcerr;
__PURE_APPDOMAIN_GLOBAL extern wostream* _Ptr_wclog;
#else // _M_CEE_PURE
_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT istream cin;
_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT ostream cout;
_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT ostream cerr;
_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT ostream clog;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT istream* _Ptr_cin;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT ostream* _Ptr_cout;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT ostream* _Ptr_cerr;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT ostream* _Ptr_clog;

_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wistream wcin;
_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wostream wcout;
_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wostream wcerr;
_EXPORT_STD extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wostream wclog;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wistream* _Ptr_wcin;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wostream* _Ptr_wcout;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wostream* _Ptr_wcerr;
extern "C++" __PURE_APPDOMAIN_GLOBAL _CRTDATA2_IMPORT wostream* _Ptr_wclog;

#ifdef _CRTBLD // TRANSITION, ABI: _Winit appears to be unused
class _CRTIMP2_PURE_IMPORT _Winit {
public:
    __thiscall _Winit();
    __thiscall ~_Winit() noexcept;

private:
    __PURE_APPDOMAIN_GLOBAL static int _Init_cnt;
};
#endif // _CRTBLD

#endif // _M_CEE_PURE
_STD_END
#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // _STL_COMPILER_PREPROCESSOR
#endif // _IOSTREAM_

이게 뭐지

대충 봤는데 std 이름공간은 안 보인다.

yvals_core.h가 가장 상단에 있으니까 들어가봤는데 죄다 전처리문이라 넘겼다.

다음, istream.

 . . .

class basic_istream : virtual public basic_ios<_Elem, _Traits> { // control extractions from a stream buffer
public:
    using _Myios = basic_ios<_Elem, _Traits>;
    using _Mysb  = basic_streambuf<_Elem, _Traits>;
    using _Iter  = istreambuf_iterator<_Elem, _Traits>;
    using _Ctype = ctype<_Elem>;
    using _Nget  = num_get<_Elem, _Iter>;

#if defined(__FORCE_INSTANCE)
    explicit __CLR_OR_THIS_CALL basic_istream(_Mysb* _Strbuf, bool _Isstd, bool _Skip_init) : _Chcount(0) {
        if (!_Skip_init) {
            _Myios::init(_Strbuf, _Isstd);
        }
    }
#endif // defined(__FORCE_INSTANCE)

 . . .
 
 private:
    template <class _Ty>
    basic_istream& _Common_extract_with_num_get(_Ty& _Val) { // formatted extract with num_get
        ios_base::iostate _Err = ios_base::goodbit;
        const sentry _Ok(*this);

        if (_Ok) { // state okay, use facet to extract
            _TRY_IO_BEGIN
            _STD use_facet<_Nget>(this->getloc()).get(*this, {}, *this, _Err, _Val);
            _CATCH_IO_END
        }

        _Myios::setstate(_Err);
        return *this;
    }
    
 . . .
 
public:
    basic_istream& __CLR_OR_THIS_CALL operator>>(bool& _Val) { // extract a boolean
        return _Common_extract_with_num_get(_Val);
    }

    basic_istream& __CLR_OR_THIS_CALL operator>>(short& _Val) { // extract a short
        ios_base::iostate _Err = ios_base::goodbit;
        const sentry _Ok(*this);

        if (_Ok) { // state okay, use facet to extract
            _TRY_IO_BEGIN
            long _Lval;
            _STD use_facet<_Nget>(this->getloc()).get(*this, {}, *this, _Err, _Lval);
            if (_Lval < SHRT_MIN) {
                _Err |= ios_base::failbit;
                _Val = SHRT_MIN;
            } else if (_Lval > SHRT_MAX) {
                _Err |= ios_base::failbit;
                _Val = SHRT_MAX;
            } else {
                _Val = static_cast<short>(_Lval);
            }
            _CATCH_IO_END
        }

        _Myios::setstate(_Err);
        return *this;
    }

    // NOTE:
    // If you are not using native wchar_t, the unsigned short extractor
    // is masked by an explicit specialization that treats an unsigned
    // short as a wide character.

    // To read or write unsigned shorts as integers with wchar_t streams,
    // make wchar_t a native type with the command line option /Zc:wchar_t.

    basic_istream& __CLR_OR_THIS_CALL operator>>(unsigned short& _Val) { // extract an unsigned short
        return _Common_extract_with_num_get(_Val);
    }

    basic_istream& __CLR_OR_THIS_CALL operator>>(int& _Val) { // extract an int
        static_assert(sizeof(int) == sizeof(long), "Bad overflow assumptions due to sizeof(int) != sizeof(long)");
        long _Result = _Val;
        _Common_extract_with_num_get(_Result);
        _Val = _Result;
        return *this;
    }

    basic_istream& __CLR_OR_THIS_CALL operator>>(unsigned int& _Val) { // extract an unsigned int
        return _Common_extract_with_num_get(_Val);
    }

    basic_istream& __CLR_OR_THIS_CALL operator>>(long& _Val) { // extract a long
        return _Common_extract_with_num_get(_Val);
    }

 . . .

빙고!

이제 뭔가 보인다. basic_istream 클래스가 보이고 밑에 멤버 함수를 보니 익숙한 연산자 오버로딩이 보인다.

int, short 같은 자요형의 입력이 1차적으로 어떻게 이루어지는지 확인할 수 있다.

각 자료형들이 모두 _Common_extract_with_num_get과 연결되는 것을 확인할 수 있다.

template <class _Ty>
    basic_istream& _Common_extract_with_num_get(_Ty& _Val) { // formatted extract with num_get
        ios_base::iostate _Err = ios_base::goodbit;
        const sentry _Ok(*this);

        if (_Ok) { // state okay, use facet to extract
            _TRY_IO_BEGIN
            _STD use_facet<_Nget>(this->getloc()).get(*this, {}, *this, _Err, _Val);
            _CATCH_IO_END
        }

        _Myios::setstate(_Err);
        return *this;
    }

 

ios_base가 보이는데 이걸 찾아보자.

istream ⊃ ostream ⊃ ios, ios 헤더 파일을 보면

 . . .

class basic_ios : public ios_base { // base class for basic_istream/basic_ostream
public:

 . . .

드디어 base_istream 클래스와 base_ostream 클래스에 상속되어있던 base_ios 클래스를 찾을 수 있었다.

그리고 드디어 이것이 상속하는 ios_base를 확인할 수 있었다.

ios ⊃ xlocnum ⊃ streambuf ⊃ xiosbase, xiosbase 파일을 보면

 . . .
 
 class _Iosb { // define templatized bitmask/enumerated types, instantiate on demand
public:
    enum _Dummy_enum { _Dummy_enum_val = 1 }; // don't ask, TRANSITION, ABI
    enum _Fmtflags { // constants for formatting options
        _Fmtmask = 0xffff,
        _Fmtzero = 0
    };
    
 . . .
 
    static constexpr _Iostate goodbit = static_cast<_Iostate>(0x0);
    
 . . .
 
 };

_EXPORT_STD extern "C++" class _CRTIMP2_PURE_IMPORT ios_base : public _Iosb<int> { // base class for ios
public:
    using fmtflags = int;
    using iostate  = int;
    using openmode = int;
    using seekdir  = int;
    
 . . .

내가 원하는 ios_base 클래스를 볼 수가 있는데 extern이랑 class를 같이 쓰고 재정의할 수 있는지 모르겠다.

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ruvendix&logNo=220943232379 

C++언어 정리하기 - 함수 재정의 오버로딩

윗 글에서는 extern "C"를 지원하여 오버로딩을 막기 위해 extern "C"를 사용할 수 있단다.

C++에서는 오버로딩된 함수의 작명이 다 다르게 되지만 C는 오버로딩을 지원하지 않으므로 만약 C++파일에 있는 함수를 C가 쓰려면 C++에 있는 선언부 앞에 extern "C" 를 붙이란다.

C를 C++에서 쓸 때에도 extern "C" {} 를 이용하여 {}안에 함수의 원형을 넣어주면된다.

 

_EXPORT_STD는 yvals_core.h에서

#define _EXPORT_STD export

로 정의되어있는 것으로 보인다.

_CRTIMP2_PURE_IMPORT는

#define _CRTIMP2_PURE_IMPORT _CRTIMP2_IMPORT

(위 코드는 F12로 타고 들어가서 본 정의 구문)

#if defined(CRTDLL2) && defined(_CRTBLD)

#define _CRTIMP2_IMPORT __declspec(dllexport)

#elif defined(_DLL) && !defined(_STATIC_CPPLIB)

#define _CRTIMP2_IMPORT __declspec(dllimport)

결과적으로 __declspec()가 되는데 dllexport랑 dllimport로 나뉘는 것을 볼 수가 있다.

https://m.blog.naver.com/hayandoud/221963429174

[C++] __declspec DLL import & export API 원리

#ifdef DLL_EXPORTS
#define DLL_API __declspec(dllexport) 
#else
#define DLL_API __declspec(dllimport) 
#endif

파일 연결이 어떻게 되어있냐에따라 export/import로 갈리는 것 같다.

대충 기능은 알았는데 문법적으로 class 키워드랑 ios_base라는 이름 사이에 __declspec이 들어가도 되는지 모르겠다.

찾아보니 MS 확장 문법이라고는 하는데..

 

sentry는 basic_istream에 중첩된 클래스이고 _Ok라는 bool 변수를 하나 가지고 있다.

sentry를 타고 가면 Sentry_base라는 바탕 클래스의 base_istream&형 변수에 *this를 할당한다. (나머지의 의미는 모르겠다)

이후는 try와 catch 구문으로 정의된 _TRY_TO_BEGIN과 _CATCH_IO_END로 싸여있는 부분인데...

_EXPORT_STD template <class _Facet>
const _Facet& __CRTDECL use_facet(const locale& _Loc) { // get facet reference from locale
    _BEGIN_LOCK(_LOCK_LOCALE) // the thread lock, make get atomic
    const locale::facet* _Psave = _Facetptr<_Facet>::_Psave; // static pointer to lazy facet

    const size_t _Id         = _Facet::id;
    const locale::facet* _Pf = _Loc._Getfacet(_Id);

    if (!_Pf) {
        if (_Psave) {
            _Pf = _Psave; // lazy facet already allocated
        } else if (_Facet::_Getcat(&_Psave, &_Loc) == static_cast<size_t>(-1)) {
#if _HAS_EXCEPTIONS
            _Throw_bad_cast(); // lazy disallowed
#else // _HAS_EXCEPTIONS
            _CSTD abort(); // lazy disallowed
#endif // _HAS_EXCEPTIONS
        } else { // queue up lazy facet for destruction
            auto _Pfmod = const_cast<locale::facet*>(_Psave);
            unique_ptr<_Facet_base> _Psave_guard(static_cast<_Facet_base*>(_Pfmod));

#if defined(_M_CEE)
            _Facet_Register_m(_Pfmod);
#else // defined(_M_CEE)
            _Facet_Register(_Pfmod);
#endif // defined(_M_CEE)

            _Pfmod->_Incref();
            _Facetptr<_Facet>::_Psave = _Psave;
            _Pf                       = _Psave;

            (void) _Psave_guard.release();
        }
    }

    return static_cast<const _Facet&>(*_Pf); // should be dynamic_cast
    _END_LOCK()
} // end of use_facet body

이거까지는 할 엄두가 안나서 포기했다.

 

_STD 키워드를 타고 들어가다가 _STD_BEGIN이 드이어 namespace std{로 정의되는걸 보았다.

많은 파일이 std 이름공간을 공유한다는 것을 발견했다.

일단 map으로 들어가봤다.

근데 이런! end의 정의가 눈을 씻고 찾아봐도 보이지 않는다.

 

오픈톡방에 질문을 드리고나니, 어라?

https://en.cppreference.com/w/cpp/header/map

Standard library header <map> - cppreference.com

밑에 원형이 있다.

분명 iterator를 반환해주는 end라는 함수가 선언되어있는데 정작 노트북 내의 map 문서에는 위 함수들이 선언되지 않았다;;

 

std::end()를 찾으려면 _STD_BEGIN이 써진 헤더와 cpp파일들을 모두 살펴봐야할 것 같다.

map.end()도 비슷한 맥락으로 찾기 어려울 것 같다...