Merge Sort - Vector not sorting

Question

Я пытаюсь выполнить сортировку слияния на std::vector<int>. Каждый int в векторе соответствует индексу в другом векторе std::vector<Node>. Каждый узел имеет глубину. Я стараюсь сортировать по глубине.

Я использую некоторый код сортировки слияния, который я нашел. Он отлично работает, используя массив целых чисел, поэтому я решил, что это будет хорошо работать в моем коде. Вот сокращенный вариант моего кода:

.h файл:

class Log{ 
public: 
    static std::vector<int> a; 
}; 

.cpp файл:

std::vector<int> Log::a; 

int getNodeDepth (int index, std::vector<cv::ml::DTrees::Node::Node> nodeList, std::vector<int> treeList) { 
    //returns the node's depth 
} 

void exchange(int i, int j) { 
    int t = Log::a[i]; 
    Log::a[i] = Log::a[j]; 
    Log::a[j] = t; 
} 

void compare(int i, int j, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    if (getNodeDepth(nodeList[Log::a[i]], nodeList) > (getNodeDepth(nodeList[Log::a[j]], nodeList))) 
    exchange(i, j); 
} 

/** 
* lo is the starting position and 
* n is the length of the piece to be merged, 
* r is the distance of the elements to be compared 
*/ 
void oddEvenMerge(int lo, int n, int r, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    int m = r * 2; 
    if (m < n) { 
     oddEvenMerge(lo, n, m, nodeList); // even subsequence 
     oddEvenMerge(lo + r, n, m, nodeList); // odd subsequence 
     for (int i = lo + r; i + r < lo + n; i += m) 
      compare(i, i + r, nodeList); 
    } else 
     compare(lo, lo + r, nodeList); 
} 

/** 
* sorts a piece of length n of the array 
* starting at position lo 
*/ 
void oddEvenMergeSort(int lo, int n, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    if (n > 1) { 
     int m = n/2; 
     oddEvenMergeSort(lo, m, nodeList); 
     oddEvenMergeSort(lo + m, m, nodeList); 
     oddEvenMerge(lo, n, 1, nodeList); 
    } 
} 

int mergeSort(std::vector<int> treeList, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    Log::a = treeList; 
    int i, n = sizeof(Log::a)/sizeof(Log::a[0]); 
    for (i = 0; i < n; i++) 
     std::cout << std::setw(3) << Log::a[i]; 
    std::cout << std::endl; 
    oddEvenMergeSort(0, n, nodeList); 
    //print sorted list 
    for (i = 0; i < Log::a.size(); i++) 
     std::cout << Log::a[i] << " * "; 
    std::cout << std::endl; 

    return(0); 
} 

Обратите внимание, что переменная nodeList только там, потому что метод глубины нуждается. Вывод выглядит так, как только затрагивается первая половина вектора. Во второй половине вектора элементы не меняются местами. Я дважды проверял, чтобы убедиться, что глубины правильные, и что правильные вещи меняются местами. Это просто не завершает работу. Любые идеи почему?

Answer 1

sizeof(Log::a)/sizeof(Log::a[0]);

Это не получить количество элементов в Log::a! Он получает размер (в байтах) типа std::vector, который не имеет ничего общего с количеством содержащихся элементов, а затем делит на размер элемента. Это дает вам мусор.

Эта идиома для массивов и std::size лучше, но не стандарт еще - вы можете легко написать его самостоятельно, как это:

template <typename T, std::size_t N> 
std::size_t arraySize(T (&)[N]) 
{ 
    return N; 
} 

(Есть более запутанные версии, если вам это нужно, как константа времени компиляции.)

Используйте Log::a.size();, чтобы получить размер std::vector.

(Возможно, у меня не хватает других проблем, но этот вариант выделяется.)