Is there a better way to keep ids in a vector sequential in C++?

Question

I have a simple C++ program that manages as a todo list. The Todo, class contains a vector of Item to track each todo action and their id. The key constraint is that the ids must be kept strictly sequential and correspond to the order in the list.

My current solution uses a fix() member function in Todo that iterates across the vector of items to enforce the id constraint. Is there a more efficient way to make sure that the IDs in list are sequential, even after removing an element?

I'm looking for an answer that is objectively more efficient while still complying with the constraints of being based on vector, using class Item, and keeping track of IDs. Note that this isn't about using the IDs in the first place.

Example to illustrate the question

Imagine we have initialized an instance of Todo and have populated it with some items:

Todo todos = Todo();

todos.add("Take out the trash.");
todos.add("Do the laundry.");
todos.add("Read a book.");
todos.add("Make dinner.");

Our todo list has sequential IDs 0, 1, 2, 3, which we can check when we display it with list():

{Todo[{Item(id=0, desc="Take out the trash.")}, {Item(id=1, desc="Do the laundry.")}, {Item(id=2, desc="Read a book.")}, {Item(id=3, desc="Make dinner.")}]}

Let's remove the element at ID 2:

todos.remove(2);

The result are:

{Todo[{Item(id=0, desc="Take out the trash.")}, {Item(id=1, desc="Do the laundry.")}, {Item(id=3, desc="Make dinner.")}]}

The IDs are still ordered but there is a gap in the sequence: 0, 1, 3. I want them to be strictly sequential, i.e. 0, 1, 2.

If I call my fix() function, it will iterate through each index of our todos, check if the elements ID matches the expected next ID, if it doesn't, set the elements ID to the current iteration index (i)

void Todo::fix() {
    for (int i = 0; i < static_cast<int>(todos.size()); i++) {
        if (todos[i].getId() != i) {
            todos[i].setId(i);
        }
    }
}

If we run it after the remove(), our todos will now appear clean again, with the strictly sequential IDs 0, 1, 2:

{Todo[{Item(id=0, desc="Take out the trash.")}, {Item(id=1, desc="Do the laundry.")}, {Item(id=2, desc="Make dinner.")}]}

I got the result I wanted, but here is the question:

Is this the most efficient way to do this task in C++? It seems that if this were a bigger list, it could become resource-intensive and slow. Is there any faster/more efficient way to do this?

Full code including example:

#include <iostream>
#include <vector>

class Item {
    private:
        int id;
        std::string description;
    public:
        Item() : id(0), description("") {}
        Item(int id, std::string description) : id(id), description(description) {}
        int getId() const { return id; }
        void setId(int value) { id = value; }
        std::string getDescription() const { return description; }
        void setDescription(std::string value) { description = value; }
};

class Todo {
    private:
        std::vector<Item> todos;
    public:
        Todo() = default;
        Todo(std::vector<Item> todos) : todos(todos) {};
        bool add(std::string description);
        bool remove(int id);
        bool edit(int id, std::string description);
        void list();
        void fix();
};

bool Todo::add(std::string description) {
    if (description.empty()) {
        return false;
    }

    todos.emplace_back(todos.size(), description);
    return true;
}

bool Todo::remove(int id) {
    if (id < 0 || id >= static_cast<int>(todos.size())) {
        return false;
    }

    todos.erase(todos.begin() + id);
    return true;
}

bool Todo::edit(int id, std::string description) {
    if (id < 0 || id >= static_cast<int>(todos.size()) || description.empty()) {
        return false;
    }

    todos[id].setDescription(description);
    return true;
}

void Todo::list() {
    std::cout << "{Todo[";
    for (size_t i = 0; i < todos.size(); ++i) {
        const auto& item = todos[i];
        std::cout << "{Item(id=" << item.getId() << ", desc=\"" << item.getDescription() << "\")}";
        if (i != todos.size() - 1) std::cout << ", ";
    }
    std::cout << "]}" << std::endl;
}

void Todo::fix() {
    for (int i = 0; i < static_cast<int>(todos.size()); i++) {
        if (todos[i].getId() != i) {
            todos[i].setId(i);
        }
    }
}

int main() {
    Todo todos = Todo();
    todos.add("Take out the trash.");
    todos.add("Do the laundry.");
    todos.add("Read a book.");
    todos.add("Make dinner.");

    todos.remove(2);

    todos.fix();

    todos.list();
    return 0;
}

Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Meta Stack Overflow, or in Stack Overflow Chat. Comments continuing discussion may be removed. — mickmackusa
– mickmackusa ♦, Commented Aug 19 at 9:07

Ted Lyngmo · Accepted Answer · 2025-08-18 20:44:14Z

I agree with Christophe that you are using the wrong container for what it seems you want to do - but - since you're asking about how to keep using a std::vector<Item> but make it more efficient, here are some ways:

Don't copy when you can move:

Item(int id, std::string description)
    : id(id), description(std::move(description)) {}

Todo(std::vector<Item> todos) : todos(std::move(todos)) {};

Don't make fix public - It invites misuse.
Make fix take an iterator where to start renumbering to not have to iterate over those that don't need renumbering.

Remove the if in fix. All, starting with the supplied iterator, will need renumbering:

class Todo {
private:
    //...
    void fix(std::vector<Item>::iterator it) {
        for (std::size_t idx = std::distance(todos.begin(), it);
            idx != todos.size();
            ++idx)
        {
            todos[idx].setId(idx); // no need for an `if`
        }
    }
public:
    //...
    bool remove(int id) {
        if (id < 0 || id >= static_cast<int>(todos.size())) {
            return false;
        }
        // pass the iterator of the first `Item` to renumber to `fix`:
        fix(todos.erase(todos.begin() + id));
        return true;
    }
};

Make list const-qualified.
Use range-based for loops when you can.

Don't stream directly to std::cout in list and don't use std::endl. Both are inefficient to a certain degree. It's usually more efficient to build a std::string and use \n.

class Todo {
public:
    void list(std::ostream& os = std::cout) const {
        auto& empty = "";
        auto& comma = ", ";
        auto* sep = empty;
        std::string out = "{Todo[";
        for (auto& item : todos) { // range-based for loop
            out += sep;
            sep = comma;
            out += "{Item(id=" + std::to_string(item.getId()) +
                   ", desc=\"" + item.getDescription() + "\")}";
        }
        out += "]}\n";
        os << out;     // only one "expensive" write
    }
};

Remove the check for empty() in the edit condition. It will most probably be optimized away (since it can never be evaluated) and removing it will therefore not make it more efficient - but it confuses readers of your code, thereby making understanding your code less efficient.
Don't use int for id since size(), that you use to populate id, is usually of a larger unsigned type, std::size_t. If you stick with int, before adding a new Item, check if size() > std::numeric_limits<int>::max() first. Changing the id type to std::size_t or checking if size() is larger than an int can hold will not make it more efficient, but may prevent bugs on platforms where the size of an int is as small as 2 octets.

Christophe · Accepted Answer · 2025-08-18 23:11:08Z

If the id is an independent property of the item, use a std::map. Maps are ordered, offer a fast access to an item, and offer iteration over all the items in an ordered fashion. An (ordered) std::set is also an alternative.

If however you change all the time the ids, because ids are not a property of the elements but a consequence of the order in your todo list, you should consider:

either a std::vector (what you use as id would be the index, but inserting a new item in the middle requires to move/copy all the items after, which may be time consuming).
or a std::list. Lists require sequential access, which is in the spirit of an ordered sequence. You can easily insert delete items, and it seems quite a good fit for to do lists. The iteration to increment ids of subsequent position is the only drawback here, but you could as well use the distance to the beginning of the list as implicit id (same principle as index of vectors, except it's a sequential access, so better iterate through the list instead of accessing it using these pseudo-ids).

In both cases, if you really want you could manage a redundant item id at the extra expense of keeping it in sync, either with fix() or by ensuring the invariants as part of add() and remove(). A middle way could be to maintain at the level of the todo list the smallest id where an insertion or a deletion took place, so that fix() only updates items after this position (see demo here, but more debugging might be needed); for short todo lists based on vectors or lists, it's unlikely to make a noticeable difference.

Collectives™ on Stack Overflow

Is there a better way to keep ids in a vector sequential in C++?

Example to illustrate the question

Full code including example:

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example to illustrate the question

Full code including example:

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related