1
\$\begingroup\$

I have two lists: L stores some values and P holds values that are indices in the first list that should be printed. Lists are sorted in ascending order. Error-checking can be ignored, and both lists are valid and values are valid.

Do I understand correctly, that since I always continue from the place I ended at, and since the values in both lists only increase, the cost of this operation is \$O(n)\$, since I only iterate over the list once?

I'd like to clean up the code. For example, is there a way to get the current index from the iterator, that would remove two additional int variables?

#include <stdio.h>
#include <iostream>
#include <list>

using std::list;

void printLots(const list<int> &l, const list<int> &p);

int main(int argc, const char * argv[]) {

    list<int> listL;
    listL.push_back(2);
    listL.push_back(4);
    listL.push_back(6);
    listL.push_back(8);
    listL.push_back(10);
    listL.push_back(12);
    listL.push_back(14);
    listL.push_back(16);
    listL.push_back(18);
    listL.push_back(20);

    list<int> listP;
    listP.push_back(0);
    listP.push_back(9);

    printLots(listL, listP);
}

void printLots(const list<int> &l, const list<int> &p) {

    auto lIterator = l.begin();
    auto pIterator = p.begin();

    int lIndex = 0;
    int pIndex = 0;

    bool finished = false;

    while (!finished) {
        int indexToPrint = *pIterator;

        while (lIndex != indexToPrint) {
            lIndex++;
            lIterator++;
        }

        std::cout << *lIterator << std::endl;
        pIndex++;
        pIterator++;

        if (pIterator == p.end()) {
            finished = true;
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

There are a few simplifications you can make:

Unused variables

The value of pIndex isn't used anywhere, so you can just get rid of it it.

Simplifying outer loop:

  1. There is no need for finish, just put the (inverted) check into the loop condition (this will then also enable you to process empty lists).
  2. You can write your outer loop as a simpler (semantically equivalent) for loop:

    for (auto pIterator = p.begin(); pIterator != p.end(); ++pIterator) {
        int indexToPrint = *pIterator;
    
        while (lIndex != indexToPrint) {
            lIndex++;
            lIterator++;
        }
        std::cout << *lIterator << std::endl;       
    }
    

Using STL algorithms

If you want to advance an iterator by a certain number, you can use std::advance instead of a loop:

std::advance(lIterator, indexToPrint - lIndex);
lIndex = indexToPrint;

Alternative Implementation (using range based for loop)

void printLots(const list<int> &l, const list<int> &p) {
    auto it = l.begin();
    int itIdx = 0;
    for (auto idx : p) {
        std::advance(it, idx - itIdx);
        itIdx = idx;
        std::cout << *it << std::endl;
    }   
}

A final remark: although, you said error checking is not necessary, I'd probably at least put an assert into place, that checks that the indices in p don't exceed the size of the list you want to print elements from.

\$\endgroup\$
2
\$\begingroup\$
  • It doesn't look like you're using <stdio.h>, so you can just remove it.

  • If you won't ever need to provide command line arguments, then you can remove main()'s parameters.

  • If you'll just be iterating though these lists forward, then it may be more beneficial to use an std::forward_list instead. Or maybe you can just use an std::vector if there's no special need for a linked list.

  • Your list assignments is still pre-C++11. Instead, use its initializer list:

    list<int> listL { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
    
    list<int> listP { 0, 9 };
    

    This will also allow you to make them const right away.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.