Re: [問題] Reverse String with recursively

[poyenc (髮箍)]

※ 引述《IhateOGC (我討厭)》之銘言：
: 開發平台(Platform): (Ex: Win10, Linux, ...)
: 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
: 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
: http://tinyurl.com/y4hq4vfg
: 錯誤結果(Wrong Output)：i
: Stdout:
: runtime error: reference binding to null pointer of type 'struct value_type'
: (stl_vector.h) - leet code spiral
: 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
:      void reverseString(vector<char>& s) {
:         static int i = 0 ;
:         static char *p = nullptr;
:         if( &s[0] != p )
:         {
:             p = &s[0];
:             i = 0;
:             cout << "init i " << endl;
:         }
:         cout << "i1 = " << i <<  endl;
:         if(  i >= (s.size()/2) )
:             return;
:         cout << "i2 = " << i <<  endl;
:         swap( s[i] , s[s.size()-1-i]);
:         i++;
:         reverseString(s);
:     }
: 補充說明(Supplement)：
: 我的i怎不會跑...
你的程式碼雖然有遞迴呼叫但不像經過遞迴思考寫出來的 xD

遞迴呼叫不只可以幫助縮小操作範圍, 也可以重新定義問題大小.
如果問題大小拆分得好, 函式裡就不會有和原輸入資料相關的邏輯
, 像是 &s[0], s.size() 等..

剛好標準函式庫裡的 std::span 可以幫我們改善這個問題, 因為是
很小的類別, 你可以自己實作或把 span-lite 源碼直接複製來用

    cppreference https://bit.ly/2Hrjlro
    span-lite    https://bit.ly/2TGRABr

這題用到的成員函式為:

    front(), back(), subspan(), size()

實作需要的工不多, 卻可以大幅提升可讀性. 而且 base case 處理
好的話連除錯都不需要, 這也是遞迴帶來的好處

    example https://bit.ly/2XNNRRU

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.76.141
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1552333599.A.342.html
推 IhateOGC: :) 感謝
推 ilikekotomi: 感謝分享 之前沒注意過span
推 LPH66: cppreference 裡可以看到 span 是 C++20 的新東西
推 TitanEric: 感謝大大分享 原來有span可以用
推 mmmmei: 請問一下span跟其他container比起來有什麼特點嗎
std::span 不是容器喔! 它是做為連續記憶體的存取介面.

std::vector 和 std::span 的關係, 與 std::string 和
std::string_view 的關係很像, 只不過 std::string_view 是唯讀
的介面, 都有 non-owning 語意 (記憶體不是由他們管理, 是做為
附屬品而存在).

std::span 原本的名字是 std::array_view 不過委員會想將 view
後綴用來專指唯讀存取, 所以才將名稱改成現在這樣. 一般的情況
下, 類別如果想將私有 std::vector 資料成員分享出來, 在還沒有
std::span 的時代會這樣寫:

    class Foo {
    public:
      // return data member 'values_'
      std::vector<int>& values();
      const std::vector<int>& values() const;

    private:
      std::vector<int> values_;
    };

    Foo foo;
    foo.values().clear(); // surprise!

為了沿用 std::vector 本身的 range 特性, 幾乎把實作暴露出來
, 允許呼叫端直接變更狀態. 換成 std::span 不僅可達成相同效果
, 甚至還可以限制存取:

    class Foo {
    public:
      std::span<int> values();
      std::span<const int> values() const; // read only

    private:
      std::vector<int> values_;
    };

    Foo foo;
    std::as_const(foo).values().front() = 99; // compile error

std::span 也可以用來作為和 C function 溝通的轉接器

參考資料

   P0122: span: bounds-safe views for sequences of objects 
   https://bit.ly/2UBhVOO

   N3851: Multidimensional bounds, index and array_view
   https://bit.ly/2XT1DTi
※ 編輯: poyenc (150.116.41.131), 03/13/2019 23:44:44
推 mmmmei: 謝謝解釋 非常清楚
→ IhateOGC: 太神了!!