C++ Insertion Sort Median Calculation Error

Question

I'm encountering an error I've not seen before, that states that reference to things are ambiguous.

I'm writing a small test program that calculates a running median. As the list grows, it recalculates the median. In this case, median means the middle number in the list, (or upper middle). Thus, the median of 7 is 7, the median of 7 and 9 is 9, and the median of 7 3 and 9 is 7.

I'm accomplishing this (I hope) with two dynamic arrays. Initially, the first value is set as the median, and then each number entered is compared to the current median. The median is obtained for calculating the middle element, between two arrays.

The left array is for all values less than the median, and the right array is for all greater. I use insertion sort to order the numbers in each array (it's great at almost sorted lists).

I just don't understand the errors I'm getting and or where I've gone wrong. I'm fairly new to C++, so I've opted for a more simple approach to the issue.

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> left;
vector<int> right;
int leftCount = 0;
int rightCount = 0;
void leftInsertionSort(int);
void rightInsertionSort(int);
void inputNumber(int, int);

int main(int argc, char** argv) {

    int length = 0;
    int value;
    int median;
    string input;

    while (cin >> input) {
        value = atoi(input.c_str());

        inputNumber(value, median);

        if (leftCount > rightCount) {
            median = (((leftCount + rightCount) / 2) + 1);
            cout << left[median];
        } else {
            median = (((leftCount + rightCount) / 2) + 1) - leftCount;
            cout << right[median];
        }
    }

    return 0;
}

void inputNumber(int value, int median) {
    if (leftCount == 0 && rightCount == 0) {
        left[0] = value;
        median = value;
        leftCount++;
    } else
    if (leftCount == 1 && rightCount == 0) {
        right[0] = value;
        if (left[0] > right[0]) {
            right[0] = left[0];
            left[0] = value;
        }
        median = right[0];
        rightCount++;
    } else
    if (value < median) {
        left[leftCount] = value;
    } else {
        right[rightCount] = value;
    }
}

void leftInsertionSort(int lLength)
{
    leftCount++;
    int key, i;
    for(int j = 1; j < lLength; j++)
    {
        key = left[j];
        i = j - 1;
        while (left[i] > key && i >= 0) {
            left[i+1] = left[i];
            i--;
        }
        left[i+1] = key;
    }
}

void rightInsertionSort(int rLength)
{
    rightCount++;
    int key, i;
    for(int j = 1; j < rLength; j++)
    {
        key = right[j];
        i = j - 1;
        while (right[i] > key && i >= 0) {
            right[i+1] = right[i];
            i--;
        }
        right[i+1] = key;
    }
}

The error I seem to be getting is 'error: reference to ‘left’ is ambiguous'

Answer 1

Judging from the compiler error I get when trying to compile that, it seems that the namespace std defines names left and right, which you're also using as variable names. The compiler can't decide which definition to use, so you get the error. It's for reasons like these that importing everything from a namespace is frowned upon - you'd be better off either explicitly importing the names you need or using namespace qualifiers.

In any case, your algorithm seems needlessly complicated. Why not just keep a single vector, push_back into it when you get a new number, place the number at the right index using an insertion algorithm, and then just return the upper middle element of the vector?