Как заменить std :: vector на связанный список?

Question

Я использовал std::vector для создания моего алгоритма. Я хотел бы заменить векторы связанными списками.

Для того, чтобы сделать это, я имел в виду, используя std::list, но я понятия не имею, как сделать это, например, я попробовал следующий пример для нахождения значения в пределах вектора/списка:

void find_values_in_vector(const std::vector<int>& input_vector, int value, int &rv1, int &rv2) 
{ 
    if (input_vector[0] >= value) { // too small 
    rv1 = 0; rv2 = 0; return; 
    } 
    int index = (int)input_vector.size() - 1; 
    if (input_vector[index] <= value) { // too big 
    rv1 = index; rv2 = index; return; 
    } 
    // somewhere inside 
    index = 0; 
    while (input_vector[index] <= value) { 
    index++; 
    } 
    rv1 = index - 1; rv2 = index; return; 
} 

void find_values_in_list(const std::list<int>& input_list, int value, int &rv1, int &rv2) 
{ 
    if (*input_list.begin() >= value) { // too small 
    rv1 = 0; rv2 = 0; return; 
    } 
    if (*input_list.end() <= value) { // too big 
    rv1 = (int)input_list.size() - 1; rv2 = (int)input_list.size() - 1; return; 
    } 
    // somewhere inside 
    int index = 0; int temp = *input_list.begin(); 
    while (temp <= value) { 
    temp = *input_list.next(); index++; 
    } 
    rv1 = index - 1; rv2 = index; return; 
} 

Это кажется неработоспособным, поскольку функция-член next() не существует. Однако я помню, что просмотр связанного списка осуществляется путем перехода к началу и перехода к следующему элементу до тех пор, пока не будет достигнута определенная точка. Я видел, что есть способ сделать это, используя interator в for-loop, но мне интересно, что случилось с моим подходом? У меня создалось впечатление, что std::list является стандартной реализацией двунаправленного связанного списка, или я ошибаюсь, и в этом случае класс std является реализацией связанного списка (ему не нужно быть двунаправленным связанный список)?

Answer 1

Стандартный способ перебрать контейнеры, как это:

for(std::list<int>::iterator it = input_list.begin(); 
    it != input_list.end(); 
    it++) 
{ 
    .... 
} 

Это также работает для векторов, карты, и т.д. деки. Концепция Iterator последовательно внедряется в STL, поэтому лучше всего привыкнуть к этим концепциям.

Там также итератор операции, такая как std::distance и std::advance и т.д. для различных типов итераторов (я предлагаю вам прочитать о них и их преимуществе/ограничении)

Если у вас есть C++ 11 доступен вы также можете использовать эту синтаксис (может быть не полезен для вашей проблемы.)

for(const auto& value : input_list) 
{ 
    ... 
} 

Это также работает в контейнере STL.

Answer 2

Это должно работать для вектора, списка, deque и set (при условии сортировки содержимого).

template <class T> 
void find_values_in_container(const T& container, int value, int &rv1, int &rv2) 
{ 
    rv1 = rv2 = 0; // Initialize 
    if (container.empty() || container.front() >= value) 
    { 
    return; 
    } 
    for (const auto& v : container) 
    { 
    rv2++; 
    if (v > value) 
    { 
     break; 
    } 
    rv1++; 
    } 
    return; 
}