將數組轉換爲向量的邊界

我正試圖在C++中學習矢量類。要做到這一點，我試着從數組轉換爲矢量形式。將數組轉換爲向量的邊界

在

陣列形式

int find_recursively(int *a, int low, int high) { 
    int mid = (low+high)/2; 

    if(....) 
     return find_recursively(a,low,mid+1); 
    else if(...) 
     return find_recursively(a,mid+1,high); 
}

我皈依到矢量形式是這樣的：

int find_recursively(vector<int> a) { 
    int low = 0; 
    int high = a.size() - 1; 
    int mid = (low + high)/2; 

    if(....) { 

     vector<int> temp (a.begin(), a.begin() + mid-2); 
     return find_recursively(temp); 
    } 

    else if(...) { 
     vector<int> temp (a.begin()+mid+1, a.begin()+high); 
     return find_recursively(temp); 
    } 
}

我測試它，並接近直接給出力。我認爲問題是與邊界，我沒有得到向量的邊界的邏輯。在此先感謝

來源

2013-03-07 Mustafa

你能解釋「給力直接關閉嗎？」爲什麼「中期2」？這應該作爲一個函數來實現，需要兩個隨機訪問迭代器，而不是任何特定類型的集合。 – 2013-03-07 20:41:33

考慮'vector temp（a.begin（），a.begin（）+ mid-2）; '對於a.size（）<4的情況。＃ – 2013-03-07 20:43:30

仔細閱讀代碼，它將不起作用。 – 2013-03-07 20:44:10

矢量支持索引運算符，因此不要使用矢量切片作爲函數參數。傳遞向量和索引的引用。與陣列相同，但帶有矢量：

int find_recursively(const vector <int> &a, int low, int high)

並且您可以使用[index]（例如[low]）來訪問您的值。但是如果「高」== a.size，嘗試使用[high]會使你的SW崩潰。永遠記得檢查指標是否在向量內。

當你調用遞歸，只是通過相同的 '一'：

find_recursively(a, low, mid+1);

例如。

來源

2013-03-07 20:46:21 user2116939

您的代碼如書面所示，一旦您的遞歸鑽取到大小爲2或更小的向量，將會有問題。此時，您的「中等」值爲1，而第一個「if」塊中的上限爲「中等2」計算結果爲-1。另外，你的函數會打開一個沒有返回語句的代碼路徑（如果「if」條件都計算爲false）。

不管怎樣，你不應該像這樣遞歸克隆載體。您應該使用迭代器，像這樣：

template< class Iter > 
int find_recursively(Iter low, Iter high) { 
    Iter mid = low + distance(low, high)/2; 

    if (...some test of *mid...) { 
     return find_recursively(low, mid); 
    } 
    else if (...some other test of *mid...) { 
     return find_recursively(++ mid, high); 
    } 
    else { 
     return (something); 
    } 
} 

// call site: 
find_recursively(my_vector.begin(), my_vector.end());

來源

2013-03-07 20:58:02 Jollymorphic

'+'只適用於隨機訪問迭代器。另外，'++ mid'？你正在跳過下半場的第一個元素。 – Zeta 2013-03-07 21:00:43

我假設你的「如果」條件與「中」的價值有關（正如你可以從我寫的內容中看到的那樣）。由於我錯了，那麼你可以省略增量。向量的迭代器的確是隨機訪問，並且你最初編寫的函數明確依賴於向量。如果你想進一步概括這個函數，你可以使用像Boost概念檢查庫這樣的東西來檢查你得到的迭代器的種類，或者編寫一些額外的（令人厭煩的）代碼來使它更簡單的迭代器類型。 – Jollymorphic 2013-03-07 21:07:04

有了這個結論'++ mid'是合理的。但是，您不需要Boost概念，只要迭代器從'iterator'派生，就可以簡單地使用['std :: advance']（http://en.cppreference.com/w/cpp/iterator/advance ）。 – Zeta 2013-03-07 21:11:17

.begin()和.end()是迭代器，它提供了一種簡單的通過一個容器迭代：

for(auto it = vec.begin(); it != vec.end(); ++vec) 
    cout << *it << " "; // print the contents of vec

注意end()不是實際的一部分容器。爲什麼這很重要？因爲它可以用來創建算法的更一般版本：

template <class ForwardIt> 
int find_recursively(ForwardIt first, ForwardIt last) { 
    const size_t length = std::distance(first,last); 
    if(length == 0) { 
     /* do something accordinlgy */ 
    } else if (length == 1) { 
     /* do something accordingly */ 
    } 
    auto mid = first; 
    std::advance(mid,length/2); 

    if(....) { 
     return find_recursively(first, mid); 
    } 

    else if(...) { 
     return find_recursively(mid, first); 
    } 
} 

/* example calls: */ 
std::vector<int> vec = {....}; 
int result1 = find_recursively(vec.begin(), vec.end()); 
int array[] = {....}; 
int result2 = find_recursively(std::begin(array), std::end(array));

來源

2013-03-07 20:58:51 Zeta

將數組轉換爲向量的邊界

回答

相關問題