Position of elements in vector

Question

I have several elements in a vector type that are read from cin and then i perfrom some calculations on the vector and it's order of elements gets changed. The problem is that I need to print the positions of the vector elements after the calculations. I don't know how to explain this well that's why i'll give an example:

10 1 100 1000

and 10 is 1st element, 1 is 2nd, 100 is 3rd etc. After the calculations the vector changes in :

100 10 1 1000

so I should print

3 1 2 4 

because 100 is the 3rd element of the input, 10 is the 1st etc. etc.

I tried with an array[1000] (because there aren't numbers larger than 1000 in the input), but it won't work because there can be multiple numbers with the same value, like:

10 10 10 100

and the output can be 1 2 3 4 or 2 3 1 4 or 3 1 2 4 etc. but here i need to output 1 2 3 4 because it's the 'smallest'.

I tried with array f[1001] and f[10] = 1, f[100] = 2, f[1] = 3 - if the numbers from the input are 10 100 1. But in case there are multiple numbers with the same value like 10 10 100, then my idea's not working. Please help me in any possible way.

Answer 1

Sounds like you need to store both the value and the initial position. You should be able to do this with an array of structs:

struct UserInput
{
    unsigned int initialPosition;
    int userInputValue;
};

int main()
{
    userInput theUserInput[100];
    // increment a counter, starting at 1, and place it in 
    // "initialPosition" in the struct as user input is read
}

I'll leave the rest up to you... as it is after all homework :) good luck.

Answer 2

• Use an associative array if you know what it is.
• Use linear search to determine the index if the number of input is limited.
• Consider using log₁₀ (or strlen) to transform the 1, 10, 100, 1000, etc. into 0, 1, 2, 3, etc.

Answer 3

From your description of such example: 10(3) 10(2) 10(1) 100(4)

What we have to output is 1 2 3 4, instead of 3 2 1 4.

So I don't think your requirement is just print the initial position directly. You've to make the position sequences as small as possible.

Following is my solution:

Use a direct-mapping hash table to store all the initial positions for specified element. All the initial positions for the same element is sorted. So if you want output the smallest position sequence, you only need to read the initial positions for this specified element from first to last.

The detailed implementation is left to you, since it's a homework.